有向图的强连通分支
在有向图G中，如果任意两个不同的顶点相互可达，则称该有向图是强连通的。有向图G的极大强连通子图称为G的强连通分支。
把有向图分解为强连通分支是深度优先搜索的一个经典应用实例。下面介绍如何使用两个深度优先搜索过程来进行这种分解，很多有关有向图的算法都从分解步骤开始，这种分解可把原始的问题分成数个子问题，其中每个子子问题对应一个强连通分支。构造强连通分支之间的联系也就把子问题的解决方法联系在一起，我们可以用一种称之为分支图的图来表示这种构造。
定义有向图G=(V,E)的分支图为GSCC=(VSCC,ESCC),其中VSCC包含的每一个结点对应于G的每个强连通分支。如果图G的对应于节点u的强连通分支中，某个结点和对应于v的强连通分支中的某个结点之间存在一条有向边，则边(u,v)∈ESCC。图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)所示图的转置，其强连通支上涂了阴影。
图1 强连通子图的实例
下列运行时间为θ(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;这一貌似简单的算法似乎和强连通支无关。下面我们将揭开这一设计思想的秘密并证明算法的证确性。我们将从两个有用的观察资料入手。
如果两个结点处于同一强连通支中，那么在它们之间不存在离开该连通支的通路。
证明：
设u和v是处于同一强连通支的两个结点，根据强连通支的定义，从u到v和从v到u皆有通路，设结点w在某一通路u→w→v上，所以从u可达w、又因为存在通路 v→u，所以可知从w通过路径w→v→u可达u，因此u和w在同一强连通支中。因为w是任意选定的，所以引理得证。
(证毕)
在任何深度优先搜索中，同一强连通支内的所有顶点均在同一棵深度优先树中。
证明：
在强连通支内的所有结点中，设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对其自身当然可达，所以有
我们同样可以通过以下推理证明Φ(Φ(u))=Φ(u)，对任意结点u,v∈V，
因为{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的祖先结点。
已知有向图G=(V,E)，在对G的深度优先搜索中，对任意结点u∈V,其祖宗Φ(u)是u的祖先。
证明：
如果Φ(u)=u，定理自然成立。如果Φ(u)≠u，我们来考虑在时刻d[u]各结点的颜色，若Φ(u)是黑色，则f[Φ(u)]<f[u]，这与不等式(1)矛盾；若Φ(u)为灰色，则它是结点u的祖先，从而定理可以得证。
现在只要证明Φ(u)不是白色即可，在从u到Φ(u)的通路中若存在中间结点，则根据其颜色可分两种情况：
- 若每一中间结点均为白色，那么由白色路径定理知Φ(u)是u的后裔，则有f[Φ(u)]<f[u]，这与不等式(1)相矛盾。
- 若有某个中间结点不是白色，设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。
(证毕)
下面的定理给出了一个关于祖宗和强连通分支之间联系的更强有力的结论。
在有向图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在那些非黑色结点中寻找具有最大完成时刻的结点并把该结点作为另一支的祖宗继续上述过程。
下面的定理形式化了以上的论证。
过程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中。通过对已发现树的数目进行归纳可知满足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)，这样就完成了归纳证明。
一、 Kosaraju算法
1. 算法思路
2. 伪代码
3. 实现代码
编辑本段二、
Tarjan算法
1. 算法思路
2. 伪代码
3. 实现代码
编辑本段三、
Gabow算法
1. 思路分析
2. 伪代码
3. 实现代码
编辑本段四、
总结
本节内容将详细讨论有向图的强连通分支算法(strongly connected component)，该算法是图深度优先搜索算法的另一重要应用。强分支算法可以将一个大图分解成多个连通分支，某些有向图算法可以分别在各个联通分支上独立运行，最后再根据分支之间的关系将所有的解组合起来。
在无向图中，如果顶点s到t有一条路径，则可以知道从t到s也有一条路径；在有向无环图中个，如果顶点s到t有一条有向路径，则可以知道从t到s必定没有一条有向路径；对于一般有向图，如果顶点s到t有一条有向路径，但是无法确定从t到s是否有一条有向路径。可以借助强连通分支来研究一般有向图中顶点之间的互达性。
有向图G=(V, E)的一个强连通分支就是一个最大的顶点子集C，对于C中每对顶点(s, t)，有s和t是强连通的，并且t和 s也是强连通的，即顶点s和t是互达的。图中给出了强连通分支的例子。我们将分别讨论3种有向图中寻找强连通分支的算法。
3种算法分别为Kosaraju算法、Tarjan算法和Gabow算法，它们都可以在线性时间内找到图的强连通分支。
Kosaraju算法
Kosaraju算法的解释和实现都比较简单，为了找到强连通分支，首先对图G运行DFS，计算出各顶点完成搜索的时间f；然后计算图的逆图GT，对逆图也进行DFS搜索，但是这里搜索时顶点的访问次序不是按照顶点标号的大小，而是按照各顶点f值由大到小的顺序；逆图DFS所得到的森林即对应连通区域。具体流程如图(1~4)。
上面我们提及原图G的逆图GT，其定义为GT=(V, ET)，ET={(u, v):(v, u)∈E}}。也就是说GT是由G中的边反向所组成的，通常也称之为图G的转置。在这里值得一提的是，逆图GT和原图G有着完全相同的连通分支，也就说，如果顶点s和t在G中是互达的，当且仅当s和t在GT中也是互达的。
根据上面对Kosaraju算法的讨论，其实现如下：
* 算法1：Kosaraju,算法步骤：
* 1. 对原始图G进行DFS，获得各节点的遍历次序ord[]；
* 2. 创建原始图的反向图GT；
* 3. 按照ord[]相反的顺序访问GT中每个节点；
* @param G 原图
* @return 函数最终返回一个二维单链表slk，单链表
* 每个节点又是一个单链表， 每个节点处的单链表表示
* 一个联通区域；slk的长度代表了图中联通区域的个数。
*/
public static SingleLink2 Kosaraju(GraphLnk G){
SingleLink2 slk = new SingleLink2();
int ord[] = new int[G.get_nv()];
// 对原图进行深度优先搜索
GraphSearch.DFS(G);
// 拷贝图G的深度优先遍历时每个节点的离开时间
for(int i = 0; i < GraphSearch.f.length; i++){
ord[i] = GraphSearch.f[i];
System.out.print(GraphSearch.parent[i] + " || ");
}
System.out.println();
// 构造G的反向图GT
GraphLnk GT = Utilities.reverseGraph(G);
/* 用针对Kosaraju算法而设计DFS算法KosarajuDFS函数
* 该函数按照ord的逆向顺序访问每个节点，
* 并向slk中添加新的链表元素；*/
GraphSearch.KosarajuDFS(GT, ord, slk);
//打印所有的联通区域
for(slk.goFirst(); slk.getCurrVal()!= null; slk.next()){
//获取一个链表元素项，即一个联通区域
GNodeSingleLink comp_i =
(GNodeSingleLink)(slk.getCurrVal().elem);
//打印这个联通区域的每个图节点
for(comp_i.goFirst();
comp_i.getCurrVal() != null; comp_i.next()){
System.out.print(comp_i.getCurrVal().elem + "\t");
}
System.out.println();
}
//返回联通区域链表
return slk;
}
算法首先对原图进行DFS搜索，并记录每个顶点的搜索离开时间ord；然后调用Utilities类中的求逆图函数reverseGraph，求得原图的逆图GT；最后调用GraphSearch类的递归函数KosarajuDFS，该函数按照各顶点的ord时间对图进行深度优先搜索。函数最终返回一个二维单链表slk，单链表每个节点的元素项也是一个单链表，每个节点处的单链表表示一个联通区域，如图，slk的长度代表了图中联通区域的个数。之所以使用这样的数据结构作为函数的结果，其原因是在函数返回之前无法知道图中共有多少个强连通分支，也不知道每个分支的顶点的个数，二维链表自然成为最优的选择。其余两个算法的返回结果也采用这种形式的链表输出结果。
图 Kosaraju算法返回的二维链表形式结果
reverseGraph函数返回的逆图是新创建的图，其每条边都与原图边的方向相反。原图中一个顶点对应的链表中的相邻顶点是按照标号由小到大的顺序排列的，这样做能提高相关算法的效率(例如isEdge(int, int)函数)。这里在计算逆图时这个条件也必须满足。该静态函数的实现如下：
* 创建一个与入参G每条边方向相反的图，即逆图。
* @param G 原始图
* @return 逆图
*/
public static GraphLnk reverseGraph(GraphLnk G){
GraphLnk GT = new GraphLnk(G.get_nv());
for(int i = 0; i < G.get_nv(); i++){
//GT每条边的方向与G的方向相反
for(Edge w = G.firstEdge(i); G.isEdge(w);
w = G.nextEdge(w)) {
GT.setEdgeWt(w.get_v2(), w.get_v1(),
G.getEdgeWt(w));
}
}
return GT;
}
函数中对顶点按照标号由小到大进行遍历，对顶点i，再遍历其对应链表中的顶点i0, …, in，并向逆图中添加边(i0, i), …, (in, i)，最终得到原图的逆图GT。可以发现，函数中调用setEdgeWt函数来向GT中添加边。细心的读者可能还记得，若待修改权值的边不存在时，函数setEdgeWt充当添加边的功能，并且能保证相邻的所有顶点的标号在链表中按由小到大的顺序排列。
Kosaraju实现中关键的一步是调用KosarajuDFS函数对逆图GT进行递归深度优先搜索。函数的另外两个形参为原图DFS所得的各顶点搜索结束时间ord，和保存连通分支结果的链表slk。KosarajuDFS的实现如下：
* 将根据逆图GT和每个节点在原图G深度遍历时的离开时间数组，
* 生成链表slk表示的连通分支
* 本函数不改变图的连接关系，只是节点的访问次序有所调整.
* @param GT 逆图
* @param ord 原图DFS各顶点遍历离开时间数组
* @param slk 连通分支存放在链表中
*/
public static void KosarajuDFS(GraphLnk GT, int ord[],
SingleLink2 slk){
/* 根据ord数组计算new_order数组，新的访问顺序为：
* 第i次访问的节点为原图上的第new_order[i]个节点 */
int new_order[] = new int[ord.length];
//调用函数newordermap改变数组的次序
newordermap(ord, new_order);
int n = GT.get_nv();
// 这里只需要记录颜色，其它信息不重要了
color = new COLOR[n];
// 颜色初始化为白色
for(int i = 0; i < n; i++)
color[i] = COLOR.WHITE;
// 为找到图中所有的联通区域，循环迭代：
for(int i = 0; i < new_order.length; i++){
// 第i次访问的节点为原图上的第new_order[i]个节点
int j= new_order[i];
if(color[j] != COLOR.WHITE)
continue;
// 创建一个图节点链表，表示一个联通区域
GNodeSingleLink gnsk = new GNodeSingleLink();
//调用递归函数，以j为起点深度搜索该图
KosarajuDFSVISIT(GT, ord, j, gnsk);
/* 将联通区的节点形成的链表添加到联通区域链表中，
* 这里使用的实际上是二维链表*/
slk.append(new ElemItem<GNodeSingleLink>(gnsk));
}
}
函数首先根据ord数组确定GT中各顶点的访问次序，方法是创建大小与ord相等的数组new_ord，并调用newordermap函数给new_ord各元素赋值。new_ord[i]的意义是：原图上第i个节点在逆图的访问次序为new_ord[i]。
例如顶点在原图中DFS遍历离开时间ord为：
|
11 |
0)16 |
1)10 |
2)15 |
3)9 |
4)14 |
5)8 |
6)13 |
7)7 |
8)20 |
9)19 |
则各顶点在逆图中访问先后次序为：
8, 9, 0, 2, 4, 6, 1, 3, 5, 7,
newordermap函数实现如下：
* 根据原图各顶点DFS得到的遍历结束时间，获取节点新
* 的访问次序.在函数返回时，new_ord[i]的意义是：
* 原图上第i个节点在逆图的访问次序为new_ord[i]；
* 其效果是：后访问的节点在新的访问次序中先访问.
* @param ord 原图各顶点DFS遍历结束时间
* @param new_ord 节点在逆图的访问次序
*/
public static void newordermap(int[] ord, int[] new_ord){
// 为防止原ord数组被破坏，对其深拷贝
int ord_temp[] = new int[ord.length];
for(int i = 0; i < ord.length; i++)
ord_temp[i] = ord[i];
int max, max_idx;
// 在ord_temp中寻找n次最大的值，并将其数组下标放
// 置到new_ord中；然后将最大值赋值为-1
for(int i = 0; i < ord.length; i++){
max_idx = 0;
max = ord_temp[max_idx];
for(int j = 0; j < ord.length; j++){
if(ord_temp[j] == -1)
continue;
if(ord_temp[j] > max){
max = ord_temp[j];
max_idx = j;
}
}
new_ord[i] = max_idx;
ord_temp[max_idx] = -1;
}
}
确定各顶点的访问次序后，按照new_ord中顶点的顺序调用递归函数KosarajuDFSVISIT对逆图进行深度优先搜索。每次调用前都创建一个新的链表作为slk链表的节点，对应一个新的强连通分支。
* 递归函数，起点为u深度搜索图G，节点递归地调用该函数时，节点的访问顺序
* 由ord决定，对节点u与之相连且标记为白色的的节点v1,v2,...
* 先访问ord[vi]最大的节点vi.当没有与节点u相连的节点或者与u相连的所有
* 节点都不是白色的了，此时获得一个联通区域，函数返回
*/
public static void KosarajuDFSVISIT(GraphLnk G, int ord[],
int u, GNodeSingleLink slk){
//访问该节点，将其颜色标记为灰色
color[u] = COLOR.GRAY;
//将该节点u添加到当前的联通区域中
slk.append(new ElemItem<Integer>(u));
//首先统计与该节点相连的、颜色为白色的节点的个数
int cnt = 0;
for(Edge w = G.firstEdge(u);
G.isEdge(w); w = G.nextEdge(w)){
if(color[w.get_v2()] == COLOR.WHITE)
cnt++;
}
//如果此时没有与该节点相连并且颜色为白色的节点，函数返回
if(cnt == 0)
return;
//否则，将与该节点相连的、白色节点暂存至数组e中
Edge e[] = new Edge[cnt];
cnt = 0;
for(Edge w = G.firstEdge(u); G.isEdge(w); w = G.nextEdge(w)){
if(color[w.get_v2()] == COLOR.WHITE)
e[cnt++] = w;
}
/*对数组e按照边的终点的访问次序ord[..]进行排序
* 这里采用选择排序来完成这一过程 */
int max_idx;
for(int i = 0; i < e.length - 1; i++){
//第i轮找第i大的元素
max_idx = i;
for(int j = i + 1; j < e.length; j++){
if(ord[e[j].get_v2()] > ord[e[max_idx].get_v2()]){
max_idx = j;
}
}
//如果原先第i位置上不是最大的，则交换操作
if(max_idx != i){
Edge t = e[i];
e[i] = e[max_idx];
e[max_idx] = t;
}
}
//对排序后的边逐个进行递归调用
for(int i = 0; i < e.length; i++)
KosarajuDFSVISIT(G, ord, e[i].get_v2(), slk);
}
函数中递归搜索顶点u的相邻顶点时，首相将u的所有尚未访问的相邻顶点(边)保存至一个边数组e中。然后再对这个数组中的边进行重排序，排序的规则依然是在原图中顶点DFS搜索离开时间。图(a)的运行结果如图所示。
这里不对Kosaraju算法进行详细证明，感兴趣的读者可以参阅相关的图算法书籍。
Tarjan算法
Kosaraju算法的流程简单，但是需要对图(和逆图)进行两次DFS搜索，而且读逆图的DFS搜索中顶点的访问顺序有特定的限制。下面将介绍的两个算法的过程比Kosaraju算法更为简洁，只需要执行一次DFS，并且不需要计算逆图。
Tarjan基于递归实现的深度优先搜索，在搜索过程中将顶点不断压入堆栈中，并在回溯时判断堆栈中顶点是否在同一联通分支。函数借助两个辅助数组pre和low，其中pre[u]为顶点u搜索的次序编号，low[u]为顶点u能回溯到的最早的顶点的次序编号。当pre[u]=low[u]时，则弹出栈中顶点并构成一个连通分支。以一个简单的例子来解释这一过程，如图所示，
|
|
递归 |
|
回溯 |
||||
|
栈 |
0 |
2 |
1 |
|
|
|
|
|
顶点 |
0 |
2 |
1 |
0 |
1 |
2 |
0 |
|
pre |
0 |
1 |
2 |
|
2 |
1 |
0 |
|
low |
0 |
1 |
2 |
|
0 |
0 |
0 |
寻找图中连通分支的过程
对图中的简单联通图，首先递归地对图进行深度优先搜索，并记录每个顶点的搜索次序pre。搜索起点为0，当对顶点1进行递归时将再次达到顶点0；在回溯过程中依次将顶点1和顶点2的low值修改为low[0]。当回溯到顶点0时将栈中low值为low[0]的顶点弹出并组成一个连通分支。
Tarjan算法实现如下：
* Trajan 算法实现图的强连通区域求解；
* 算法步骤：
* @param G 待求解的图
* @return
* 一个二维单链表slk，单链表每个节点也是一个单链表，
* 每个节点处的单链表表示一个联通区域；
* slk的长度代表了图中联通区域的个数。
*/
public static SingleLink2 Tarjan(GraphLnk G){
SingleLink2 slk = new SingleLink2();
// 算法需借助于栈结构
LinkStack ls = new LinkStack();
int pre[] = new int[G.get_nv()];
int low[] = new int[G.get_nv()];
int cnt[] = new int[1];
// 初始化
for(int i = 0; i < G.get_nv(); i++){
pre[i] = -1;
low[i] = -1;
}
// 对顶点运行递归函数TrajanDFS
for(int i = 0; i < G.get_nv(); i++){
if(pre[i] == -1) {
GraphSearch.TarjanDFS(G,
i, pre, low, cnt,
ls, slk);
}
}
// 打印所有的联通区域
for(slk.goFirst(); slk.getCurrVal() != null; slk.next()){
// 获取一个链表元素项，即一个联通区域
GNodeSingleLink comp_i =
(GNodeSingleLink)(slk.getCurrVal().elem);
// 打印这个联通区域的每个图节点
for(comp_i.goFirst();
comp_i.getCurrVal() != null; comp_i.next()){
System.out.print(comp_i.getCurrVal().elem + "\t");
}
System.out.println();
}
return slk;
}
函数首先申明数组变量pre, low和cnt，并对初始化。pre 和low的意义前面已经解释过，cnt是长度为1的数组。因为在函数TarjanDFS中cnt的值需要不断变化，如果直接用变量作为形参，函数并不会改变cnt的值，所以需要使用数组。除了数组变量之外，还有一个栈ls，其作用是在对图进行深度优先搜索时记录遍历顶点，并在回溯时弹出部分顶点形成连通分支。
函数关键的步骤是对图中各顶点调用递归函数TarjanDFS，该函数以深度优先搜索算法为基础，在递归和回溯时不断对pre, low以及栈ls进行操作。实现如下：
* Tarjan算法的递归DFS函数
*/
public static void TarjanDFS(GraphLnk G, int w,
int pre[], int low[], int cnt[],
LinkStack ls, SingleLink2 slk){
int t , min = low[w] = pre[w] = cnt[0]++;
// 将当前顶点号压栈
ls.push(new ElemItem<Integer>(w));
// 对当前顶点的每个邻点循环
for(Edge e = G.firstEdge(w);
G.isEdge(e);
e = G.nextEdge(e)){
// 如果邻点没有遍历过，则对其递归调用
if(pre[e.get_v2()] == -1){
TarjanDFS(G, e.get_v2(),
pre, low, cnt,
ls, slk);
}
/* 如果邻点已经被遍历过了，比较其编号与min,
* 如果编号较小，则更新min的大小*/
if(low[e.get_v2()] < min)
min = low[e.get_v2()];
}
// 如果此时min小于low[w]，则返回
if(min < low[w]){
low[w] = min;
return;
}
// 否则，弹出栈中元素，并将元素添加到链表中
GNodeSingleLink gnslk = new GNodeSingleLink();
do{
//弹出栈顶元素
t = ((Integer)(ls.pop().elem)).intValue();
low[t] = G.get_nv();
//添加到链表中
gnslk.append(new ElemItem<Integer>(t));
}while(t != w);
// 将该链表添加到slk链表中
slk.append(new ElemItem<GNodeSingleLink>(gnslk));
}
下面以图中有向图为例，分析Tarjan算法求解较为复杂的有向图的过程。各顶点的搜索访问次序以及low值的变化如图。
|
顶点 |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
次序 |
0 |
2 |
1 |
3 |
6 |
4 |
7 |
5 |
8 |
9 |
|
low |
0 |
2/0 |
1/0 |
3 |
6 |
4/3 |
7/6 |
5 |
8 |
9/8 |
|
min |
0 |
2/0 |
1/0 |
3 |
6 |
4/3 |
7/6 |
5 |
8 |
9/8 |
深度优先搜索各顶点的访问次序以及堆栈中顶点的变化过程如图。其中框出来的步骤表示遍历到达已访问过的顶点，此时需要对low做修改，堆栈中黑体加粗的顶点表示弹出的顶点。
图 Tarjan算法详细过程图
算法详细过程分析如下：
搜索起点为顶点0，递归搜索顶点2、顶点1，这三个顶点被压入栈中。在顶点1处首先递归搜索顶点0，由于顶点0已经访问过，所以不再递归搜索顶点0，而是作如下处理：
如果low[0] < 顶点1的min（记为min1），则min1 ← low[0]，
此时(0=low[0])<(min1=1)，所以min1←0。
接着到达顶点3，顶点3尚未被访问，则递归搜索顶点3，并继续搜索顶点5。此时，顶点5第一个相邻点为顶点3，则不再递归搜索顶点3，更新min5值，min5←3。
接着递归搜索顶点7，顶点7只有一个相邻顶点，即为顶点自身，则顶点7的递归结束。回溯到顶点7，此时min7=low[7]=5，弹出栈中顶点7，并作为第一个联通分支。
函数继续回溯到顶点5，此时顶点5的相邻顶点的递归搜索已经全部结束，由于(3=min5)<(low[5]=5)，则low[5]←(min5=3)，并返回；函数回溯到顶点3，此时与顶点3相邻的顶点的递归搜索也已全部完成，由于min3=low[3]=3，所以弹出栈中顶点5和顶点3，作为第二个连通分支。
函数回溯至顶点1，此时与顶点1相邻的顶点的递归调用已结束，此时(0=min1)<(low[1]=2)，则low[1]←(min1=0)，并返回；函数回溯顶点2，更新min2←(low[1]=0)；此时顶点2还有两个相邻顶点，即顶点3和顶点4，顶点3已经判定属于第二个连通分支，所以对顶点4递归搜索。
首先将顶点4压入栈中，对相邻顶点5递归搜索，顶点5已经判定属于第二个连通分支，所以转而对顶点6递归搜索。顶点6的第一个相邻顶点为4，则不再递归搜索顶点4，更新顶点6的min6←(low[4]=6)。顶点6的第二个相邻顶点为7，但顶点7已经判定属于第一个连通分支。此时顶点6的所有相邻顶点递归搜索结束，此时(6=min6)<(low[6]=7)，则low[6]←(min6=6)，并返回；函数回溯到顶点4，与顶点4相邻的顶点的递归搜索也已全部完成，由于min4=low[4]=6，所以弹出栈中顶点6和顶点4，作为第三个连通分支。
函数回溯至顶点2，此时顶点2的所有相邻顶点递归搜索结束，此时(0=min2)<(low[2]=1)，则low[2]←(min2=0)，并返回；
函数回溯至顶点0，此时顶点0的所有相邻顶点递归搜索结束，并且顶点min0=low[0]，则将栈中顶点1,2,0依次弹出，作为第四个连通分支。
最后函数继续递归搜索顶点8和顶点9(略)。
从算法的流程可以清楚的发现Tarjan算法可以在线性时间内找出一个有向图的强分量，并且对原图进行一次DFS即可。
.Gabow算法
Gabow算法是Tarjan算法的提升版本，该算法类似于Tarjan算法。算法维护了一个顶点栈，但是还是用了第二个栈来确定何时从第一个栈中弹出各个强分支中的顶点，它的功能类似于Tarjan算法中的数组low。从起始顶点w处开始进行DFS过程中，当一条回路显示这组顶点都属于同一个强连通分支时，就会弹出栈二中顶点，只留下回边的目的顶点，也即搜索的起点w。
当回溯到递归起始顶点w时，如果此时该顶点在栈二顶部，则说明该顶点是一个强联通分量的起始顶点，那么在该顶点之后搜索的顶点都属于同一个强连通分支。于是，从第一个栈中弹出这些点，形成一个强连通分支。
根据上面对算法的描述，实现如下：
* @param G 输入为图结构
* @return:
* 函数最终返回一个二维单链表slk，单链表每个节点又是一个单链表，
* 每个节点处的单链表表示一个联通区域；
* slk的长度代表了图中联通区域的个数。
*/
public static SingleLink2 Gabow(GraphLnk G){
SingleLink2 slk = new SingleLink2();
// 函数使用两个堆栈
LinkStack ls = new LinkStack();
LinkStack P = new LinkStack();
int pre[] = new int[G.get_nv()];
int cnt[] = new int[1];
// 标注各个顶点所在的连通分支的名称
int id[] = new int[G.get_nv()];
// 初始化
for(int i = 0; i < G.get_nv(); i++){
pre[i] = -1;
id[i] = -1;
}
for(int i = 0; i < G.get_nv(); i++){
if(pre[i] == -1) {
GraphSearch.GabowDFS(G,
i, pre, id, cnt,
ls, P, slk);
}
}
//打印所有的联通区域
for(slk.goFirst(); slk.getCurrVal() != null; slk.next()){
//获取一个链表元素项，即一个联通区域
GNodeSingleLink comp_i =
(GNodeSingleLink)(slk.getCurrVal().elem);
//打印这个联通区域的每个图节点
for(comp_i.goFirst();
comp_i.getCurrVal() != null; comp_i.next()){
System.out.print(comp_i.getCurrVal().elem + "\t");
}
System.out.println();
}
return slk;
}
函数调用递归实现的深度优先搜索GabowDFS，实现如下：
/**
* GabowDFS算法的递归DFS函数
* @param ls 栈1,
* @param P 栈2，决定何时弹出栈1中顶点
*/
public static void GabowDFS(GraphLnk G, int w,
int pre[], int[] id, int cnt[],
LinkStack ls, LinkStack P,
SingleLink2 slk){
int v;
pre[w] = cnt[0]++;
//将当前顶点号压栈
ls.push(new ElemItem<Integer>(w));
System.out.print("+0 stack1 ");ls.printStack();
P.push(new ElemItem<Integer>(w));
System.out.print("+0 stack2 ");P.printStack();
// 对当前顶点的每个邻点循环
for(Edge e = G.firstEdge(w); G.isEdge(e); e = G.nextEdge(e)){
//如果邻点没有遍历过，则对其递归调用
if(pre[e.get_v2()] == -1){
GabowDFS(G, e.get_v2(), pre, id, cnt, ls, P, slk);
}
// 否则，如果邻点被遍历过但又没有被之前的连通域包含，则循环弹出
else if(id[e.get_v2()] == -1){
int ptop = ((Integer)(P.getTop().elem)).intValue();
// 循环弹出，直到栈顶顶点的序号不小于邻点的序号
while(pre[ptop] > pre[e.get_v2()]) {
P.pop();
System.out.print("-1 stack2 ");P.printStack();
ptop = ((Integer)(P.getTop().elem)).intValue();
}
}
}
// 遍历完顶点的所有相邻顶点后，如果栈2顶部顶点与w相同则弹出；
if(P.getTop() != null
&& ((Integer)(P.getTop().elem)).intValue() == w){
P.pop();
System.out.print("-2 stack2 ");P.printStack();
}
// 否则函数返回
else return;
// 如果栈2顶部顶点与w相同，则弹出栈1中顶点，形成连通分支
GNodeSingleLink gnslk = new GNodeSingleLink();
do{
v = ((Integer)(ls.pop().elem)).intValue();
id[v] = 1;
gnslk.append(new ElemItem<Integer>(v));
}while(v != w);
System.out.print("-3 stack1 ");ls.printStack();
slk.append(new ElemItem<GNodeSingleLink>(gnslk));
}
以图中有向图为例，并在深度优先搜索过程中跟踪记录两个栈中元素的变化如下：
0.
+0 stack2 当前栈从栈顶至栈底元素为：
0.
+0 stack1 当前栈从栈顶至栈底元素为：
2, 0.
+0 stack2 当前栈从栈顶至栈底元素为：
2, 0.
+0 stack1 当前栈从栈顶至栈底元素为：
1, 2, 0.
+0 stack2 当前栈从栈顶至栈底元素为：
1, 2, 0.
-1 stack2 当前栈从栈顶至栈底元素为：
2, 0.
-1 stack2 当前栈从栈顶至栈底元素为：
0.
+0 stack1 当前栈从栈顶至栈底元素为：
3, 1, 2, 0.
+0 stack2 当前栈从栈顶至栈底元素为：
3, 0.
+0 stack1 当前栈从栈顶至栈底元素为：
5, 3, 1, 2, 0.
+0 stack2 当前栈从栈顶至栈底元素为：
5, 3, 0.
-1 stack2 当前栈从栈顶至栈底元素为：
3, 0.
+0 stack1 当前栈从栈顶至栈底元素为：
7, 5, 3, 1, 2, 0.
+0 stack2 当前栈从栈顶至栈底元素为：
7, 3, 0.
-2 stack2 当前栈从栈顶至栈底元素为：
3, 0.
-3 stack1 当前栈从栈顶至栈底元素为：
5, 3, 1, 2, 0.
-2 stack2 当前栈从栈顶至栈底元素为：
0.
-3 stack1 当前栈从栈顶至栈底元素为：
1, 2, 0.
+0 stack1 当前栈从栈顶至栈底元素为：
4, 1, 2, 0.
+0 stack2 当前栈从栈顶至栈底元素为：
4, 0.
+0 stack1 当前栈从栈顶至栈底元素为：
6, 4, 1, 2, 0.
+0 stack2 当前栈从栈顶至栈底元素为：
6, 4, 0.
-1 stack2 当前栈从栈顶至栈底元素为：
4, 0.
-2 stack2 当前栈从栈顶至栈底元素为：
0.
-3 stack1 当前栈从栈顶至栈底元素为：
1, 2, 0.
-2 stack2 当前栈为空！
-3 stack1 当前栈为空！
+0 stack1 当前栈从栈顶至栈底元素为：
8.
+0 stack2 当前栈从栈顶至栈底元素为：
8.
+0 stack1 当前栈从栈顶至栈底元素为：
9, 8.
+0 stack2 当前栈从栈顶至栈底元素为：
9, 8.
-1 stack2 当前栈从栈顶至栈底元素为：
8.
-2 stack2 当前栈为空！
算法的流程这里不做详细分析，读者可以参见Tarjan算法的分析流程，并自行体会算法的思想。