使用BFS或DFS，以确定在非连通图的连通性？ [英] Using BFS or DFS to determine the connectivity in a non connected graph?

问题描述

如何才能使用的 BFS或DFS 算法，我可以设计一个算法，确定非连通图连接组件，该算法必须能够为表示组中的每个连接元件的顶点

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each connected component.

这是我的aproach：

1）初始化所有顶点未访问。

1) Initialize all vertices as not visited.

2）做图的从任意顶点v启动DFS遍历。   如果DFS遍历没有访问所有顶点，然后返回false。

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）反转所有弧（或发现转或逆转图形）

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

4）标记所有顶点未访问的反转图形。

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

5）不要颠倒图来自同一个顶点v启动DFS遍历   （与步骤2相同）。如果DFS遍历没有访问所有顶点，然后   返回false。否则返回true。

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.

我们的想法是，如果每个节点可以从一个顶点v被达到，并且每   节点可以达到V，然后，图形是强连接。在步骤2中，我们   检查是否所有顶点从V可达。在步骤4中，我们检查是否所有   顶点可达到V（在相反的图形，如果所有的顶点可达   从V，那么所有的顶点可达到V IN原图）。

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).

如何提高该解决方案的任何想法？

Any idea of how to improve this solution?.

推荐答案

既然你似乎有向图的工作，你想找到连接的组件（非强连接），你有你的图形转换为无向图先。因此，对于每一个顶点，在相反的方向添加临时顶点。然后，你可以使用从没有被访问过，找到连接组件的每个顶点开始简单的DFS。最后，你可以删除临时顶点。

Since you seem to be working with a directed graph, and you want to find the connected components (not strongly connected), you have to convert your graph to an undirected graph first. So for each vertex, add a temporary vertex in the opposite direction. Then you can use a simple DFS starting from each vertex which hasn't been visited yet to find the connected components. Finally, you can remove the temporary vertices.

这篇关于使用BFS或DFS，以确定在非连通图的连通性？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！