算法，以检查是否有向图是强连通 [英] Algorithm to check if directed graph is strongly connected

问题描述

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

I need to check if a directed graph is strongly connected, or, in other words, if all nodes can be reached by any other node (not necessarily through direct edge).

这样做是运行DFS和BFS在每个节点上，看到所有的人依旧可达的一种方式。

One way of doing this is running a DFS and BFS on every node and see all others are still reachable.

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

Is there a better approach to do that?

推荐答案

<一个href="http://en.wikipedia.org/wiki/Tarjan%27s%5Fstrongly%5Fconnected%5Fcomponents%5Falgorithm">Tarjan's强连通分量算法（或 Gabow 的变化），当然就足够了;如果只有一个强连通分量，那么，图形是强连接。

Tarjan's strongly connected components algorithm (or Gabow's variation) will of course suffice; if there's only one strongly connected component, then the graph is strongly connected.

两者都是线性的时间。

对于一个正常的深度优先搜索，跟踪每个节点的状态：新，观察，但仍处于打开状态（它在调用堆栈），并看到和成品。此外，您存储深度，当你第一次到达一个节点，最低等的深度，它是从节点的访问（你知道这一点后，你完成一个节点）。节点是一个强连接组件的根如果最低可达深度等于其自身的深度。这适用即使要使用从根到达一个节点的深度不可能的最小值。

As with a normal depth first search, you track the status of each node: new, seen but still open (it's in the call stack), and seen and finished. In addition, you store the depth when you first reached a node, and the lowest such depth that is reachable from the node (you know this after you finish a node). A node is the root of a strongly connected component if the lowest reachable depth is equal to its own depth. This works even if the depth by which you reach a node from the root isn't the minimum possible.

要检查只是整个图形无论是单SCC，启动DFS，从任何一个节点，而当你完成，如果最低可达深度为0，而每一个节点进行访问，那么整个图形强连接。

To check just for whether the whole graph is a single SCC, initiate the dfs from any single node, and when you've finished, if the lowest reachable depth is 0, and every node was visited, then the whole graph is strongly connected.

这篇关于算法，以检查是否有向图是强连通的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！