[图] 3.2.1 Kosaraju算法-有向图的强连通分量-图解
3.2 有向图的强连通分量-原理:https://blog.csdn.net/summer_dew/article/details/81666877
Kosaraju算法可以在线性时间和线性空间内找出一个图的强分量
举例
举个例子就很容易理解该算法了
【图G】求图G的强连通分量
【步骤】
- 求图G的逆图R
- 对逆图R进行DFS,得到DFS生成森林
- 求得生成森林的后序序列
- 以逆图R的DFS后序数组(第三步的结果)后面往前的顺序,对原图G进行DFS,DFS得到的好几个生成树即是强连通分量
伪代码
#define maxV 100 //最大的顶点数
int cnt0, cnt1;
// 对图进行DFS,将DFS生成森林的后序序列放在post中
int post[maxV]; //存放DFS生成森林的后序序列
void SCdfsR(Graph *G, int w) { //对G从顶点w进行DFS
link t; //邻边
G->sc[w] = cnt1; //DFS访问标记
for (t=G->adj[w]; t!=NULL; t=t->next) //G的邻边
if (G->sc[t->v]==-1) SCdfsR(G, t->v); //G的邻接点还没有进行DFS
post[cnt0++]=w; //记录后序序列
}
// Kosaraju算法:求图G的强连通分量,记录在sc数组中
int GraphSC(Graph *G) {
int v;
Graph R; //逆图G
int postR[maxV]; //逆图RDFS生成森林的后序序列
GraphReverse(*G, &R); //对G求逆图,存到R中
for (v=0; v<G->vernum; v++) R.sc[v]=-1; //逆图sc数组初始化
//对逆图R进行DFS
cnt0=0; cnt1=0;
for (v=0; v<G->vernum; v++)
if (R.sc[v]==-1) SCdfsR(&R, v);
//对图G进行DFS
cnt0=0; cnt1=0;
for (v=0; v<G->vernum; v++) G->sc[v]=-1; //sc数组初始化
for (v=0; v<G->vernum; v++) postR[v]=post[v]; //递归过程中post会被重新赋值-->将逆图R的后序序列拷贝到postR
//按照 逆图R的DFS生成树的后序序列 的逆序 顺序,来对图G进行DFS
for (v=G->vernum-1; v>=0; v--) {
if (G->sc[ postR[v] ]==-1) {
SCdfsR(G, postR[v]);
//第一次DFS退出
cnt1++; //进入下一个强连通分量
}
}
//销毁中间变量-逆图R
GraphDestory(&R);
return cnt1;
}
// 判断结点s,t是否为强连通
int GraphStrongGraph(Graph G, int s, int t) {
return G.sc[s]==G.sc[t];
}