确定图形是否是半连接的

平凡的

O(V^3)

解决办法是使用弗洛伊德warshal所有到所有的最短路径，但是这是一个矫枉过正（以时间复杂度）。

可以在中完成

O(V+E)

。

要求：

DAG按拓扑结构半连接，每个

i

都有一个边缘

(vi,vi+1)

证明：

给定具有拓扑排序的DAG

v1,v2,...,vn

：

如果

(vi,vi+1)

某边没有边

i

，则也就没有路径

(vi+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) | there is v1 in V1 and v2 in V2 such that (v1,v2) is in E)

3. 对G’进行拓扑排序
4. 检查每个i是否有边Vi，Vi + 1。

正确性证明：

如果该图是半连接的，那么对于一对

(v1,v2)

，则存在一条路径

v1->...->v2

-假设V1，V2为它们的SCC。由于V1和V2中的所有节点均已牢固连接，因此存在从V1到V2的路径，因此也有从v1到v2的路径。

如果算法得出的结果为true，则对于任何两个给定的节点v1，v2-我们知道它们在SCC
V1和V2中。从V1到V2有一条路径（不失一般性），因此也有从v1到v2的路径。

---

附带说明一下，每个半连接图也有一个根（

r

通向所有顶点的顶点）：

证明：
假设没有根。定义

#(v) = |{u | there is a path from v to u}|

（具有

v

到它们的路径的节点数）。
选择

a

这样

#(a) = max{#(v) | for all v}

。

a

不是根，因此有些节点

u

没有

a

到它的路径。由于图形是半连接的，因此意味着存在一条路径

u->...->a

。但这意味着

#(u) >= #(a)+ 1

（所有节点均可从

a

和访问

u

）。
与的最大值矛盾

#(a)

，因此有一个根。