-1

前向边缘导致非子后代

  • 如果一个顶点通向另一个顶点，根据定义，第二个顶点是第一个顶点的子顶点。因此，顶点如何导致非子节点？根据定义，顶点的孩子是由它导致的。

交叉边既不通向祖先也不通向后代

  • 如果一个顶点通向另一个顶点，则第二个顶点是第一个顶点的孩子。因此，如果根据定义一个顶点导致的任何东西都是它的孩子，那么交叉边怎么会导致非后代呢？

  • 来源是如何挑选的？DFS 算法如何知道从哪里开始？

  • 边的类型是否取决于算法从哪里开始？例如，如果算法从顶点 A 开始并在顶点 Z 结束，则从 Z 到 A 的边将是后边。但是，如果算法从 Z 开始并在 A 结束，它将是一个前沿。我的推理正确吗？每次运行时边缘的类型都会改变吗？

4

1 回答 1

2

如果一个顶点通向另一个顶点，根据定义，第二个顶点是第一个顶点的子顶点。

不; 这里的“子”是指表示搜索空间的树，而不是“叠加”在其上以显示搜索顺序的图。请参阅Wikipedia中的有用插图。

您的其他问题也有类似的困惑。

选择源以反映问题。它会一直持续到您找到可接受的解决方案。

假设您想了解如何从浴室到卧室。那么你的起始节点必须是一间浴室——你真正迷路的地方。你在房子里四处走动，倒退并尝试其他门，当你找到卧室（解决方案）时，你停下来。有两张图：一张是搜索树；另一个是搜索顺序的线性路径。实际上是三个，如果你包括问题空间本身。

问题空间，具有<>表示双向边缘（大多数人的房子里的所有门都可以允许任何方向的人进入）：

            BATHROOM
              <> 
ENTRANCE <> HALLWAY  <>  DINING ROOM
              <>
            STAIRWAY <>  KIDS ROOM
              <>
            BEDROOM

搜索图 - 树（->表示母女关系；在树中，它们通常被认为是单向的）

Bathroom -> Hallway -> Entrance
                    -> Stairway -> Kids Room
                                -> Bedroom                            
                    -> Dining Room

搜索顺序 - 显示您如何遍历树的线性图。

Bathroom -> Hallway -> Entrance -> Stairway -> Kids Room -> Bedroom

在 BFS 中，给定相同的图表，它将是：

Bathroom -> Hallway -> Entrance -> Stairway -> Dining Room -> Kids Room -> Bedroom

开始节点由问题设置：“我在浴室”。目标节点也是由问题设定的：“我想去卧室”。

在另一个问题中：“我在奥赛罗的特定位置。（开始）我想赢。（目标）”

另请注意，如果我在走廊里迷路了，我仍然可以使用 DFS；您只需将图形转换为树，并将任何边固定为远离起点：

Hallway -> Entrance
        -> Dining Room
        -> Stairway -> Kids Room
                    -> Bedroom
        -> Bathroom
于 2012-06-17T19:39:10.787 回答