判断一个图是否为半连通的

Question

一个有向图 G = (V, E) 如果所有顶点对 u, v 属于 V 都满足 u -> v 或 v -> u 路径，则称 G 是半连通的。 给出一个有效的算法来确定 G 是否是半连通的。

- Dan

Answer 1

简单的 O(V^3) 解法是使用 floyd warshal 的全源最短路径，但这是过度杀伤力（从时间复杂度的角度来看）。

可以使用 O(V+E) 的方法解决。

断言：

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

证明：

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

如果对于某个 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. 在图中找到最大强连通分量。
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 分别为它们的强连通分量。从 V1 到 V2 存在一条路径，因此从 v1 到 v2 也存在一条路径，因为 V1 和 V2 中的所有节点都是强连通的。

如果算法返回 true，则对于任意给定的两个节点 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）的极大性矛盾，因此存在根。

- amit

---

谢谢您的回答。 - Piyush

正如答案所说，您首先需要获取SCCs（强连通分量）。SCC的图形（如2中所述）保证是一个DAG。 - amit

这个有可视化吗？最大SCC是什么意思？ - mLstudent33

最大值是最高的数字？那么我猜它应该是一个下沉SCC。 - mLstudent33

https://en.wikipedia.org/wiki/Strongly_connected_component - amit

Answer 2

Amit的解决方案完全描述了最有效的方法。我只想补充一点，可以通过检查G'是否存在多个拓扑排序来替换步骤4。如果是，则图形不是半连通的。否则，图形是半连通的。这可以很容易地并入Kahn's algorithm以找到图形的拓扑顺序。

另一个效率较低的解决方案是以下内容。

首先，构建另一个图G*，它是原始图的反向图。然后对于G的每个顶点v，在G中从v运行DFS，并将可达节点集合视为R_v。如果R_v != V(G)，则在G*中从v再次运行DFS，并将可达节点集合命名为R_v。如果R_v和R_v的并集不是V(G)，则图形不是半连通的。

- Hassan AbouEisha

Answer 3

Amit算法中第3步和第4步的主要思想是检查你的深度优先森林是否由多个深度优先树组成。只有一个树的存在是半连通性的必要条件，因为多个树代表着未连接的节点。

类似的思想：哈密顿路径、最长路径长度。

- Suraj Mishra