利用Gabow算法求有向图的强连通分量

返回首页

Gabow算法是用于求有向图的强连通分量

Gabow算法的用途之一是，求一个有向图G=(V,E)里极大强连通分量。强连通分量是指有向图G里顶点间能互相到达的子图。而如果一个强连通分量已经没有被其它强通分量完全包含的话，那么这个强连通分量就是极大强连通分量。

时间复杂度：O（M+N） 注：M代表边数，N代表顶点数。

步骤概要：

步骤1: 找一个没有被遍历过的顶点v，进行步骤2（v）（遍历时间由1开始累加，若是非连通图，则须重复进行步骤1）。否则，算法结束。

步骤2 将v压入堆栈stk1[]和stk2[]；

对于v所有的邻接顶点u：
（1） 如果u没有被遍历过，则进行步骤2（u），同时维护stk2[]
（2） 如果u已经被遍历过，如果访问过，但没有删除，维护stk2[](处理环的过程，在stk2 中删除构成环的节点)
如果stk2[]的顶元素==v，那么输出相应的强连通分量

简要说明:

　　这个算法其实就是Tarjan算法的变异体，我们观察一下，只是它用第二个堆栈来辅助求出强连通分量的根，而不是Tarjan算法里面的DFN[]和Low[]数组。那么，我们说一下如何使用第二个堆栈来辅助求出强连通分量的根。
　　我们使用类比方法，在Tarjan算法中，每次Low[i]的修改都是由于环的出现(不然，Low[i]的值不可能变小)，每次出现环，在这个环里面只剩下一个Low[i]没有被改变(深度最低的那个)，或者全部被改变，因为那个深度最低的节点在另一个环内。那么Gabow算 法中的第二堆栈变化就是删除构成环的节点，只剩深度最低的节点，或者全部删除，这个过程是通过出栈来实现，因为深度最低的那个顶点一定比前面的先访问，那 么只要出栈一直到栈顶那个顶点的访问时间不大于深度最低的那个顶点。其中每个被弹出的节点属于同一个强连通分量。那有人会问：为什么弹出的都是同一个强连 通分量？因为在这个节点访问之前，能够构成强连通分量的那些节点已经被弹出了，这个对Tarjan算法有了解的都应该清楚，那么Tarjan算法中的判断根我们用什么来代替呢？想想，其实就是看看第二个堆栈的顶元素是不是当前顶点就可以了。
　　现在，你应该明白其实Tarjan算法和Gabow算法其实是同一个思想的不同实现，但是，Gabow算法更精妙，时间更少(不用频繁更新Low[])。

显示的是一个随机 12 * 12 的方阵

计算出来后的