图论算法——有向图的强连通分支

在有向图G中，如果任意两个不同的顶点相互可达，则称该有向图是强连通的。有向图G的极大强连通子图称为G的强连通分支。 把有向图分解为强连通分支是深度优先搜索的一个经典应用实例。下面介绍如何使用两个深度优先搜索过程来进行这种分解，很多有关有向图的算法都从分解步骤 开始，这种分解可把原始的问题分成数个子问题，其中每个子子问题对应一个强连通分支。构造强连通分支之间的联系也就把子问题的解决方法联系在一起，我们可 以用一种称之为分支图的图来表示这种构造。 定义有向图G=(V,E)的分支图为GSCC=(VSCC,ESCC),其中VSCC包含的每一个结点对应于G的每个强连通分支。如果图G的对应于节点u的强连通分支中，某个结点和对应于v的强连通分支中的某个结点之间存在一条有向边，则边(u,v)∈ESCC。图1给出了一个实例。显而易见对于分支图有以下定理： 定理1 有向图G的分支图GSCC是一个有向无回路图。 图1展示了一个有向图的强连通分支的实例。(a)为有向图G，其中的阴影部分是G的强连通分支，对每个顶点都标出了其发现时刻与完成时刻，黑色边为树 枝；(b)G的转置图GT。图中说明了算法Strongly_Connected_Components第3行计算出的深度优先树，其中黑色边是树枝。 每个强连通子图对应于一棵深度优先树。图中黑色顶点b,c,g和h是强连通子图中每个顶点的祖先，这些顶点也是对GT进行深度优先搜索所产生的深度优先树的树根。(c)把G的每个强连通子图缩减为单个顶点后所得到的有向无回路子图（即G的分支图）。 寻找图G=(V,E)的强连通分支的算法中使用了G的转置，其定义为：GT=(V,ET)，其中ET={(v,u)∈V×V:(u,v)∈E}，即ET由G中的边改变方向后组成。若已知图G的邻接表，则建立GT所需时间为O(V+E)。注意到下面的结论是很有趣的：G和GT有着完全相同的强连通支，即在G中u和v互为可达当且仅当在GT中它们互为可达。图1(b)即为图1(a)所示图的转置，其强连通支上涂了阴影。 下列运行时间为θ(V+E)的算法可得出有向图G=(V,E)的强连通分支，该算法使用了两次深度优先搜索，一次在图G上进行，另一次在图GT上进行。 procedure Strongly_Connected_Components(G); begin  1.调用DFS(G)以计算出每个结点u的完成时刻f[u];  2.计算出GT;  3.调用DFS（GT），但在DFS的主循环里按针f[u]递减的顺序考虑各结点（和第一行中一样计算）;  4.输出第3步中产生的深度优先森林中每棵树的结点，作为各自独立的强连通支。 end; 这一貌似简单的算法似乎和强连通支无关。下面我们将揭开这一设计思想的秘密并证明算法的证确性。我们将从两个有用的观察资料入手。 引理1 如果两个结点处于同一强连通支中，那么在它们之间不存在离开该连通支的通路。 证明： 设u和v是处于同一强连通支的两个结点，根据强连通支的定义，从u到v和从v到u皆有通路，设结点w在某一通路u→w→v上，所以从u可达w、又因为存 在通路 v→u，所以可知从w通过路径w→v→u可达u，因此u和w在同一强连通支中。因为w是任意选定的，所以引理得证。（证毕） 定理2 在任何深度优先搜索中，同一强连通支内的所有顶点均在同一棵深度优先树中。 证明： 在强连通支内的所有结点中，设r第一个被发现。因为r是第一个被发现，所以发现r时强连通支内的其他结点都为白色。在强连通支内从r到每一其他结点均有 通路，因为这些通路都没有离开该强连通支（据引理1），所以其上所有结点均为白色。因此根据白色路径定理，在深度优先树中，强连通支内的每一个结点都是结 点r的后裔。（证毕） 在下文中，记号d[u]和f[u]分别指由算法Strongly_Connected_Components第1行的深度优先搜索计算出的发现和完成时刻。类似地，符号u→v是指G中而不是GT中存在的一条通路。 为了证明算法Strongly_Connected_Components的正确性，我们引进符号Φ(u)表示结点u的祖宗w，它是根据算法第1行的深 度优先搜索中最后完成的从u可达的结点（注意，与深度优先树中祖先的概念不同）。换句话说，Φ(u)是满足u→w且f[w]有最大值的结点w。 注意有可能Φ(u)=u，因为u对其自身当然可达，所以有 f[u]≤f[Φ[u]]                      (1) 我们同样可以通过以下推理证明Φ(Φ(u))=Φ(u)，对任意结点u,v∈V， u→v说明f[Φ(v)]≤f[Φ(u)]          (2) 因为{w|v→w}包含于{w|u→w}，且祖宗结点是所有可达结点中具有最大完成时刻的结点。又因为从u可达结点Φ(u)，所以(2)式表明订 f[Φ(Φ(u))]≤f[Φ(u)]，用Φ(u)代入(1)式中的u同样有f[Φ(u)]≤f[Φ(Φ(u))]，这样 f[Φ(Φ(u))]=f[Φ(u)]成立。所以有Φ(Φ(u))=Φ(u)，因为若两结点有同样的完成时刻，则实际上两结点为同一结点。 我们将发现每个强连通分支中都有一结点是其中每一结点的祖宗，该结点称为相应强连通分支的“代表性结点”。在对图G进行的深度优先搜索中，它是强连通支中最先发现且最后完成的结点。在对GT的深度优先搜索中，它是深度优先树的树根，我们现在来证明这一性质。 第一个定理中称Φ(u)是u的祖先结点。 定理3 已知有向图G=(V,E)，在对G的深度优先搜索中，对任意结点u∈V,其祖宗Φ(u)是u的祖先。 证明： 如果Φ(u)=u，定理自然成立。如果Φ(u)≠u，我们来考虑在时刻d[u]各结点的颜色，若Φ(u)是黑色，则f[Φ(u)] 1. 若每一中间结点均为白色，那么由白色路径定理知Φ(u)是u的后裔，则有f[Φ(u)] 2. 若有某个中间结点不是白色，设t是从u到Φ(u)的通路上最后一个非非白节点，则由于不可能有从黑色结点到白色结点的边存在，所以t必是灰色。这 样就存在一条从t到Φ(u)且由白色结点组成的通路，因此根据白色路径定理可推知Φ(u)是t的后裔，这表明f[t]>f[Φ(u)]成立，但从u 到t有通路，这巧我们对Φ(u)的选择相矛盾。（证毕） 推论1 在对有向图G=(V,E)的任何深度优先搜索中，对所有u∈V，结点u和Φ(u)处于同一个强连通分支内。 证明： 由对祖宗的定义有u→Φ(u)，同时因为Φ(u)是u的祖先，所以又有Φ(u)→u。（证毕） 下面的定理给出了一个关于祖宗和强连通分支之间联系的更强有力的结论。 定理4 在有向图G=(V,E)中，两个结点u,v∈V处于同一强连通分支当且仅当对G进行深度优先搜索时两结点具有同一祖宗。 证明： →：假设u和v处于同一强连通分支内，从u可达的每个结点也满足从v可达，反之亦然。这是由于在 u和 v之间存在双向通路，由祖宗的定义我们可以推知Φ(u)=Φ(v)。 ←：假设Φ(u)=Φ(v)成立，根据推论1，u和Φ(u)在同一强连通分支内且v和Φ(v)也处于同一强连通分支内，因此u和v也在同一强连通支中。（证毕） 有了定理4，算法Strongly_Connected_Components的结构就容易掌握了。强连通分支就是有着同一组总的节点的集合。再根据定理3和括号定理可知，在算法第1行所述的深度优先搜索中，祖宗是其所在强连通分支中第一个发现最后一个完成的结点。 为了弄清楚为什么在算法Strongly_Connected_Components的第3行要对GT进行深度优先搜索，我们考察算法的第1行的深度优 先搜索所计算出的具有最大完成时刻的结点r。根据祖宗的定义可知结点r必为一祖宗结点，这是因为它是自身的祖宗：它可以到达自身且图中其他结点的完成时刻 均小于它。在r的强连通分支中还有其他哪些节点？它们是那些以F为祖宗的结点——指可达r但不可达任何完成时刻大于f[r]的结点的那些结点。 但由于在G中r是完成时刻最大的结点，所以r的强连通分支仅由那些可达r的结点组成。换句话说，r的强连通支由那些在GT中从r可达的顶点组成。在算法第3行的深度优先搜索识别出所有属于r强连通支的结点，并把它们置为黑色（宽度优先搜索或任何对可达结点的搜索可以同样容易地做到这一点）。 在执行完第3行的深度优先搜索并识别出r的强连通分支以后，算法又从不属于r强连通分支且有着最大完成时刻的任何结点r'重新开始搜索。结点，r'必为其自身的祖宗，因为由它不可能达到任何完成时刻大于它的其他结点（否则r'将包含于r的强连通分支中）。 根据类似的推理，可达r'且不为黑色的任何结点必属于r'的强连通分支，因而在第3行的深度优先搜索继续进行时，通过在GT中从r'开始搜索可以识别出属于r'的强连通分支的每个结点并将其置为黑色。 因此通过第3行的深度优先搜索可以对图“层层剥皮”，逐个取得图的强连通分支。把每个强连通分支的祖宗作为自变量调用DFS_Visit过程，我们就可 在过程DFS的第7行识别出每一支。DFS_Visit过程中的递归调用最终使支内每个结点都成为黑色。当DFS_Visit返回到DFS中时，整个支的 结点都变成黑色且被“剥离”，接着DFS在那些非黑色结点中寻找具有最大完成时刻的结点并把该结点作为另一支的祖宗继续上述过程。 下面的定理形式化了以上的论证。 定理5 过程Strongly_Connected_Components(G)可正确计算出有向图G的强连通分支。 证明： 通过对在GT上 进行深度优先搜索中发现的深度优先树的数目进行归纳，可以证明每棵树中的结点都形成一强连通分支。归纳论证的每一步骤都证明对GT进行深度优先搜索形成的 树是一强连通分支，假定所有在先生成的树都是强连通分支。归纳的基础是显而易见的，这是因为产生第一棵树之前无其他树，因而假设自然成立。 考察对GT进行深度优先搜索所产生的根为r的一棵深度优先树T，设C(r)表示r为祖宗的所有结点的集合： C(r)={v∈V|Φ(v)=r} 现往我们来证明结点u被放在树T中当且仅当u∈C(r)。 →：由定理2可知C(r)中的每一个结点都终止于同一棵深度优先树。因为r∈C(r)且r是T的根，所以C(r)中的每个元素皆终止于T。 ←：通过对两种情形f[Φ(w)]>f[r]或f[Φ(w)]f[r]的任何结点w不在树T中，这是由于在选择到r时，w已经被放在根为Φ(w)的树中。 满足f[Φ(w)]<f[r]的任意结点w也不可能在树T中，这是因为若w被放入T中，则有w→r：因此根据式(2)和性质r=Φ(r)，可得 f[Φ(w)]≥f[Φ(r)]=f[r]，这和f[Φ(w)]<f[r]相矛盾。这样树T仅包含那些满足Φ(u)=r的结点u，即T实际上就是强 连通支C(r)，这样就完成了归纳证明。（证毕）