检查算法，如果向图强连通(Algorithm to check if directed graph

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

这样做的一种方式运行的每一个节点上的DFS和BFS和看到所有其他国家仍然可达。

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

Answer 1:

的Tarjan的强连通分量算法（或Gabow的过程的变化）就足够了; 如果只有一个强连通分量，则该图形是强烈地连接。

两者都是线性时间。

与通常的深度优先搜索，你跟踪每个节点的状态：新的，看到的却依然开放（它在调用堆栈），并看到和完成。此外，您存储深度，当你第一次到达一个节点，而最低的这样的深度是从节点到达（你知道这你完成一个节点之后）。节点是一个强连接组件的根如果最低可达深度等于其自身的深度。这个工程即使通过其到达从根节点的深度是不是最小的可能。

要检查只是整个图形无论是单SCC，启动从任何一个节点的DFS，当你完成，如果最低可达深度为0，并参观了每一个节点，那么整个图是强连通的。

Answer 2:

考虑下面的算法。

开始在随机顶点v的曲线图的G ，并运行DFS(G, v)
- 如果DFS(G, v)未达到图中的每个其它顶点G ，则存在一些顶点u ，使得没有来自向路径v到u ，因此G 不是强连接 。
- 如果是这样达到的每个顶点，那么有从引导路径v到图中的每个其它顶点G 。
扭转在所述有向图的所有边的方向G 。
再次运行DFS开始v 。
- 如果DFS无法到达的每个顶点，再有就是一些顶点u ，从使得原始图有没有向路u到v 。
- 在另一方面，如果它确实达到每个顶点，然后在原来的曲线有一个从每个顶点的有向路径u到v 。

因此，如果G“通过”既DFSS，强烈连接。此外，由于运行DFS在O(n + m)时，该算法在运行O(2(n + m)) = O(n + m)的时间，因为它需要2个DFS遍历。

Answer 3:

要检查是否每一个节点具有到和从在一个给定的图形每一个其他节点的两条路径：

1. DFS / BFS从所有节点：

的Tarjan的算法假设每个节点具有一深度d[i] 最初，根具有最小深度。而我们做的后序DFS更新d[i] = min(d[j])对于任何邻居j的i 。实际上BFS也能正常工作与减速规则d[i] = min(d[j])在这里。

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

如果存在从一个转发路径u到v ，然后d[u] <= d[v] 在SCC， d[v] <= d[u] <= d[v]因此，在SCC所有节点将具有相同的深度。判断一个图是一个SCC，我们检查所有节点是否有相同的d[i]

2.两个DFS / BFS从单个节点：

这是一个简化版本kosaraju算法。从根开始，我们检查，如果每个节点可以通过DFS / BFS到达。然后，反向每边缘的方向。我们检查，如果每个节点可以是同根再次达到。见C ++代码。

Answer 4:

你可以计算出所有点对最短路径，看看有没有是无限的。

Answer 5:

的Tarjan的算法已经被提及。但我经常发现kosaraju算法更容易，即使它需要的图形两次遍历跟随。 IIRC，它也很好的解释CLRS。

Answer 6:

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
}