algorithm - 使用 BFS 或 DFS 确定非连通图中的连通性？

Question

我如何使用BFS 或 DFS 算法设计算法以确定非连通图的连通分量，该算法必须能够表示每个连通分量的顶点集。

这是我的方法:

1) Initialize all vertices as not visited.

2) Do a DFS traversal of graph starting from any arbitrary vertex v. If DFS traversal doesn’t visit all vertices, then return false.

3) Reverse all arcs (or find transpose or reverse of graph)

4) Mark all vertices as not-visited in reversed graph.

5) Do a DFS traversal of reversed graph starting from same vertex v (Same as step 2). If DFS traversal doesn’t visit all vertices, then return false. Otherwise return true.

The idea is, if every node can be reached from a vertex v, and every node can reach v, then the graph is strongly connected. In step 2, we check if all vertices are reachable from v. In step 4, we check if all vertices can reach v (In reversed graph, if all vertices are reachable from v, then all vertices can reach v in original graph).

知道如何改进这个解决方案吗？

Answer 1

怎么样

• 让顶点 = 输入
• 让 results = 空列表
• 当vertices中有顶点时:
  • 创建一个集合S
  • 选择任意一个未探索的顶点，并将其放入S。
  • 从该顶点运行 BFS/DFS，找到每个顶点后，将其从 vertices 中移除并将其添加到 S。
  • 将S添加到results
• 返回结果

完成后，您将获得一组顶点的列表，其中每组都是通过从某个顶点搜索图形(使每组中的顶点相连)制成的。假设有一个无向图，这应该可以正常工作(超出我的想象)。