16

我需要检查有向图是否是强连接的，或者换句话说，是否所有节点都可以被任何其他节点（不一定通过直接边）到达。

一种方法是在每个节点上运行 DFS 和 BFS，并查看所有其他节点仍然可以访问。

有没有更好的方法来做到这一点？

4

9 回答 9

32

考虑以下算法。

  1. v从图的一个随机顶点开始G，然后运行DFS(G, v)​​.

    • If DFS(G, v) fails to reach every other vertex in the graph G, then there is some vertex u, such that there is no directed path from v to u, and thus G is not strongly connected.

    • If it does reach every vertex, then there is a directed path from v to every other vertex in the graph G.

  2. Reverse the direction of all edges in the directed graph G.

  3. Again run a DFS starting at v.

    • If the DFS fails to reach every vertex, then there is some vertex u, such that in the original graph there is no directed path from u to v.

    • On the other hand, if it does reach every vertex, then in the original graph there is a directed path from every vertex u to v.

Thus, if G "passes" both DFSs, it is strongly connected. Furthermore, since a DFS runs in O(n + m) time, this algorithm runs in O(2(n + m)) = O(n + m) time, since it requires 2 DFS traversals.

于 2012-10-17T19:28:18.410 回答
18

Tarjan 的强连通分量算法（或Gabow 的变体）当然就足够了；如果只有一个强连通分量，则图是强连通的。

两者都是线性时间。

与正常的深度优先搜索一样，您跟踪每个节点的状态：新的、已看到但仍处于打开状态（它在调用堆栈中）以及已看到和已完成。此外，您存储第一次到达节点时的深度，以及从节点可到达的最低深度（您在完成节点后知道这一点）。如果最低可达深度等于它自己的深度，则节点是强连接组件的根。即使您从根到达节点的深度不是可能的最小值，这也有效。

要检查整个图是否是单个 SCC，请从任何单个节点启动 dfs，当您完成后，如果最低可达深度为 0，并且访问了每个节点，则整个图是强连接的。

于 2009-09-16T18:54:51.327 回答
3

To check if every node has both paths to and from every other node in a given graph:

1. DFS/BFS from all nodes:

Tarjan's algorithm supposes every node has a depth d[i]. Initially, the root has the smallest depth. And we do the post-order DFS updates d[i] = min(d[j]) for any neighbor j of i. Actually BFS also works fine with the reduction rule d[i] = min(d[j]) here.

function dfs(i)
    d[i] = i
    mark i as visited
    for each neighbor j of i: 
        if j is not visited then dfs(j)
        d[i] = min(d[i], d[j])

If there is a forwarding path from u to v, then d[u] <= d[v]. In the SCC, d[v] <= d[u] <= d[v], thus, all the nodes in SCC will have the same depth. To tell if a graph is a SCC, we check whether all nodes have the same d[i].

2. Two DFS/BFS from the single node:

It is a simplified version of the Kosaraju’s algorithm. Starting from the root, we check if every node can be reached by DFS/BFS. Then, reverse the direction of every edge. We check if every node can be reached from the same root again. See C++ code.

于 2018-09-22T01:48:35.723 回答
1

您可以计算所有对最短路径，看看是否有无限。

于 2009-09-16T18:55:08.877 回答
1

Tarjan 算法已经提到过。但我通常发现Kosaraju 的算法更容易理解，即使它需要对图进行两次遍历。IIRC，它在 CLRS 中也得到了很好的解释。

于 2009-09-16T19:33:19.347 回答
1 
test-connected(G)
{
    choose a vertex x
    make a list L of vertices reachable from x,
    and another list K of vertices to be explored.
    initially, L = K = x.

    while K is nonempty
    find and remove some vertex y in K
    for each edge (y, z)
    if (z is not in L)
    add z to both L and K

    if L has fewer than n items
    return disconnected
    else return connected
}
于 2010-09-18T05:19:42.573 回答
1

You can use Kosaraju’s DFS based simple algorithm that does two DFS traversals of graph:

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 of the algorithm, 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).

Algorithm : 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.

Time Complexity: Time complexity of above implementation is same as Depth First Search which is O(V+E) if the graph is represented using adjacency list representation.

于 2018-04-17T07:16:26.627 回答
0

一种方法是为图生成拉普拉斯矩阵，然后计算特征值，最后计算零的数量。如果仅存在一个零特征值，则该图是强连接的。

注意：注意为有向图创建拉普拉斯矩阵的方法略有不同。

于 2009-09-16T18:58:38.890 回答
0

The algorithm to check if a graph is strongly connected is quite straightforward. But why does the below algorithm work?

Algorithm: suppose there is a graph with vertices [A, B, C......Z]

  1. Choose any random node, say J, and perform DFS from it. If all the nodes are reachable then continue to step 2.

  2. Reverse the directions of the edges of the graph by doing transpose.

  3. Again run DFS from node J and check if all the nodes are visited. If yes then the graph is strongly connected and return true.

Performing step 1 makes sense because we have to check if we can reach all the nodes from that node. After this, next logical step could be

i) Now do this for all other nodes

ii) or try to reach node J from every other node. Because once you reach node J, you are sure that you can reach every other node because of step 1.

This is what we are trying to do in steps 2 & 3. If in a transposed graph node J is able to reach all other nodes then this implies that in original graph all other nodes can reach J.

于 2021-12-20T20:58:30.963 回答