《gabow算法》word版

《《gabow算法》word版》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、有向图强连通分量的定义：在有向图G中，如果两个顶点vi,vj间（vi!=vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(stronglyconnected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量(stronglyconnectedcomponents)。对于一幅无向图来说，只要2个顶点相连在同一路径上，那么这两个顶点就是连通的，从其中一个顶点可以到达另一顶点，求出哪些顶点是连通的也并不难。而对于有向图，受方向限制，两个连通的顶

2、点并不一定能互相到达。如果两个连通的顶点可以相互到达，那么这两个顶点是强连通的。如果将图中所有的互相强连通的顶点划为一组，那么这组顶点就是强连通分量。高效求出强连通分量的算法有Kosaraju算法，Tarjan算法，Gabow算法。我表示我只能看懂Gabow算法。据说Gabow算法和Tarjan算法的思想是一样的。每个强连通分量都有一个“根”，根是强连通分量中最先被检查的顶点。在一组强连通分量中，沿着根不断深度优先搜索，最终将会回到根，路上经过的顶点则属于这个强连通分量。准备工作：因为是演示，假定只有6个顶点，而且序号是连续的。#de

3、fineMAXVERTEX6首先需要一个数组，用来保存当前顶点被检测的顺序。intOrder[MAXVERTEX];在这里将-1定为初始值，即没有被检测。Order[v]表示顶点v是第几个被检测的。除了这个数组，还需要一个变量，用来表示当前的顺序。intOrderNum=0;初始化为0表示还没开始检测。结果也以数组的形式表示，为每个强连通分量分配一个不同的编号，而一个强连通分量中的所有顶点编号相同。intPart[MAXVERTEX];开始这个数组应该被初始化为-1，表示还不确定其中的顶点属于哪个强连通分量。同样还需要一个变量表示当前

4、处理到第几个强连通分量。intPartNum=0;表示还没开始处理。另外还需要2个辅助栈。第一个用来保存在一次深度优先搜索过程中遇到的顶点。stackPath;这些顶点还没有被确定属于哪个强连通分量，在确定顶点属于某个强连通分量之后，就记录结果，将顶点弹出堆栈。第二个用来保存在一次深度优先搜索过程中遇到的根。stackRoot;步骤1:在所有顶点中，找一个没有被访问过的节点v，以v为参数执行步骤2。否则完成。步骤2:记录v的访问顺序。将v压入堆栈Path和Root。如果v指向其它的邻接顶点，那么对于每个邻接顶点ne

5、xt：1)如果没有访问过，则以next为参数，递归执行步骤2。2)如果访问过，而且没有确定它属于哪个强连通分量，弹出Root栈中next之后所有的顶点。如果Root栈的顶元素等于v，那么在Part中记录顶点对应的的强连通分量。最后递归返回。代码：#include#include#includeusingnamespacestd;#defineMAXVERTEX6vectorEdge[MAXVERTEX];intOrder[MAXVERTEX];intOrderNum=0;i

6、ntPart[MAXVERTEX];intPartNum=0;stackPath;stackRoot;voidGabow(intv){Order[v]=++OrderNum;Path.push(v);Root.push(v);for(inte=0;eOrder[next])Root.

7、pop();}}if(v==Root.top()){Root.pop();PartNum++;intTop;do{Top=Path.top();Part[Top]=PartNum;Path.pop();}while(Top!=v);}}int_stdcallWinMain(HINSTANCEhInstance,HINSTANCEhPrevInstance,LPSTRlpCmdLine,intnShowCmd){Edge[0].push_back(1);Edge[0].push_back(2);Edge[1].push_back(3);

8、Edge[2].push_back(3);Edge[2].push_back(4);Edge[3].push_back(0);Edge[3].push_back(5);Edge[4].push_back(5);//-1的