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

Question

我已经阅读了有关BFS和DFS算法的页面和信息页面.他们没有说什么,首先选择哪个顶点？

例如,在此图像中,箭头是否表示您不能从c遍历到b,但可以从b遍历到c？

朋友,非常感谢您的帮助.

Answer 1

可以使用任何源Vertex S启动 Breadth-first_search和 Depth-first_search.

选择哪个顶点作为源顶点？- Depends upon your requirement.

示例:

1. 如果你想使用BFS找到从Source S到所有其他顶点的最短路径(对于所有边具有相同成本或未加权图的图).然后你应该选择S作为源顶点.

2. 如果你想要找到顶点K是否可以从顶点S到达,在这种情况下你也必须从源顶点S开始你的BFS/DFS.

3. 如果你想在一个迷宫问题中解决Rat,其中一只老鼠从源S开始并且必须使用DFS到达目的地,那么你必须再次从Source S启动DFS算法.

In some Cases, We are free to choose any vertex as a source vertex.

示例:

1. 在查找有向图的强连通分量(SCC)时,我们通过选择任何顶点作为源顶点来启动DFS.

2. 在使用DFS执行有向非循环图的拓扑排序时,我们可以自由选择任何顶点作为源顶点.

因此,首先选择哪个顶点并不固定,并且取决于问题的性质,我们正在使用DFS和BFS进行求解.

Answer 2

如果不是有向图，那也没关系。您发布的图是有向图，其含义与您所说的完全一样。你可以从a到b，但不能从b到a。

关于在有向图中选择哪个节点，您选择的每个节点都会产生不同的结果。通常在这些情况下，最好从根节点（如果给定）开始。