使用BFS或DFS确定非连接图中的连接？

Question

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

这是我的方法:

1)将所有顶点初始化为未访问.

2)从任意顶点开始对图进行DFS遍历v.如果DFS遍历不访问所有顶点,则返回false.

3)反转所有弧(或找到图的转置或反转)

4)在反转图中将所有顶点标记为未访问.

5)从相同的顶点v开始执行反向图的DFS遍历(与步骤2相同).如果DFS遍历不访问所有顶点,则返回false.否则返回true.

这个想法是,如果每个节点都可以从顶点v到达,并且每个节点都可以到达v,那么图形就是强连接的.在步骤2中,我们检查是否可以从v到达所有顶点.在步骤4中,我们检查所有顶点是否都可以到达v(在反向图中,如果所有顶点都可以从v到达,那么所有顶点都可以到达原始图中的v).

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

Answer 1

怎么样

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

完成后，您将获得一个顶点集列表​​，其中每个集合都是通过从某个顶点进行图形搜索而组成的（使每个集合中的顶点相互连接）。假设一个无向图，这应该可以正常工作（在我的脑海中）。