algorithm - 有向图中彼此不可达的顶点对

Question

我被要求设计一种算法来确定在有向图中是否存在任何一对彼此不可达的顶点。该算法必须在 O(|V| + |E|) 时间内运行

含义:顶点i不能到达顶点j，顶点j不能到达顶点i。

我看过强连通分量的查找方法，我想知道我是否可以从那里开始设计一种在当前情况下可用的算法？

Answer 1

如果您能在要求的线性 O(V + E) 时间内找到所有强连通分量，那么您就完成了。这似乎有点矫枉过正，但它解决了问题。要找到所有强连接的组件，假设您的图形表示为邻接列表，也许最简单的 O(V + E) 线性时间算法是 Kosaraju 的，请参见例如http://en.wikipedia.org/wiki/Kosaraju%27s_algorithm

一旦找到所有强连通分量，那么通过考虑节点是强连通分量且存在边的压缩图，测试是否存在一对未通过任何路径连接的强连通分量就相当简单如果从两个连通分量中选择的任意两个节点之间存在边。