BFS和DFS - 从哪个顶点开始？

Question

我已经阅读了大量关于BFS和DFS算法的信息，但它们都没有说到首先选择哪个顶点？

例如，在这张图片中，箭头是否意味着不能从c到b遍历，但可以从b到c遍历？

非常感谢你们的帮助。

- I'LL BE BACK

---

起始顶点是搜索的一个参数。当您调用搜索时，您需要指定它，并且搜索仅访问从起始顶点可达的顶点。 - Daniel Fischer

实际上，他们并没有这样说，因为“广度优先”和“深度优先”只是指访问节点的顺序。起始节点取决于你想要实现什么目标。 - Oliver Charlesworth

Answer 1

广度优先搜索和深度优先搜索可以从任何源顶点S开始。

选择哪个顶点作为源顶点？-取决于您的需求。

例如:

1. 如果您想要使用BFS（对于所有边具有相同成本或无权图的图）找到从源S到所有其他顶点的最短路径。然后您应该选择S作为源顶点。

2. 如果您想要查找K顶点是否可达从顶点S开始，在这种情况下，您也必须从源顶点S开始启动BFS / DFS。

3. 如果您想要解决迷宫中的老鼠问题，其中老鼠从源S开始并且必须使用DFS到达目的地，则再次必须从源S开始启动DFS算法。

在某些情况下，我们可以自由选择任何一个顶点作为源顶点。

例子：

1. 在寻找有向图的强连通分量（SCC）时，我们通过选择任何一个顶点作为源顶点开始DFS。 2. 在使用DFS执行有向无环图的拓扑排序时，同样可以自由选择任何一个顶点作为源顶点。

因此，首先选择哪个顶点并不固定，而取决于我们用DFS和BFS解决的问题的性质。

- Ritesh Kumar Gupta

---

对于拓扑排序，我们实际上可以自由选择任何一个顶点作为源顶点吗？ 如果所选顶点只有入边，我不知道如何使用DFS完成它。 - cindy50633

@cindy50633 只有入边意味着该顶点没有未被访问的子节点，因此可以认为已完成。 - HappyFace

Answer 2

箭头表示您无法从c到b遍历，但可以从b到c遍历吗？

这是一个有向图，是的。

当您执行DFS时，不需要指定要从哪个节点开始，因为您将遍历所有节点。

DFS的过程是：

DFSmain(G):
     For v=1 to n: if v is not yet visited, do DFS(v).

DFS(v):
   mark v as visited. // entering node v
   for each unmarked out-neighbor w of v: do DFS(w).
   return. // exiting node v.

所以它最终会访问图中的每个节点。对于BFS也有类似的原理。

- taocp

Answer 3

如果它不是有向图，那就没关系了。 您发布的图是有向图，这意味着正如您所述，您可以从a到b，但不能从b到a。 关于在有向图中选择哪个节点，每个选择的节点都可能产生不同的结果。通常在这种情况下，最好从给定的根节点开始。

- stdcall