algorithm - BFS & DFS - 从哪个顶点开始？

Question

我已经阅读了关于 BFS 和 DFS 算法的页面和页面的信息。他们都没有说，首先选择哪个顶点？

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

朋友们，非常感谢您的帮助。

Answer 1

Breadth-first_search和Depth-first_search可以从任何源 Vertex S开始。

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

示例：

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

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

3. 如果你想解决老鼠从源S开始并必须使用 DFS 到达目的地的迷宫问题，那么你必须再次从源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

do the arrows mean you cannot traverse from c to b, but can traverse from b to 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 的类似原理。

Answer 3

如果它不是有向图，那没关系。您发布的图表是有向图，这正是您所说的。你可以从a到b，但不能从b到a。

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