algorithm - 判断一个图是否是半连通的

Question

有向图 G = (V, E) 被称为半连通图，如果对于 V 中的所有顶点对 u, v 我们有 u -> v 或 v-> u 路径。给出判断G是否半连通的高效算法

Answer 1

简单的 O(V^3) 解决方案可能是使用 floyd warshal最短路径，但这是一种矫枉过正(就时间复杂度而言)。

可以在 O(V+E) 中完成。

声明:

一个DAG是半连通的拓扑排序，对于每个i，都有一条边(vi,vi+1)

证明:

给定一个具有拓扑排序的 DAG v1,v2,...,vn:

如果对于某些i没有边(vi,v(i+1))，那么也就没有路径(v(i+ 1),vi)(因为是拓扑排序的DAG)，图不是半连通的。

如果对于每个 i 都有一条边 (vi,vi+1)，那么对于每个 i,j (i < j ) 存在路径vi->vi+1->...->vj-1->vj，图是半连通的。

由此我们可以得到算法:

1. 找出图中的最大 SCC。
2. 构建 SCC 图 G'=(U,E') 使得 U 是一组 SCC。 E'= { (V1,V2) | V1 中有 v1，V2 中有 v2，使得 (v1,v2) 在 E 中 。
3. 对 G' 进行拓扑排序。
4. 检查是否对于每个 i，都有边 Vi,V(i+1)。

正确性证明:

如果图是半连通的，对于一对 (v1,v2)，这样就有一条路径 v1->...->v2 - 让V1、V2 是它们的 SCC。存在从 V1 到 V2 的路径，因此也存在从 v1 到 v2 的路径，因为 V1 和 V2 中的所有节点都是强连接的。

如果算法结果为真，那么对于任意两个给定节点 v1、v2 - 我们知道它们位于 SCC V1 和 V2 中。存在从 V1 到 V2 的路径(不失一般性)，因此也存在从 v1 到 v2 的路径。

---

作为旁注，每个半连通图都有一个根(顶点 r 通向所有顶点):

证明:
假设没有根。定义 #(v) = |{u |有一条从 v 到 u}| 的路径(有一条从 v 到它们的路径的节点数)。
选择a使得#(a) = max{#(v) |对于所有 v}。
a 不是根，所以有一些节点 u 没有从 a 到它的路径。由于图是半连通的，这意味着存在路径u->...->a。但这意味着 #(u) >= #(a) + 1(所有节点都可以从 a 和 u 到达)。
#(a)的极大矛盾，故有根。