学步园

这个算法网上很多介绍，但大多都很相似，着重介绍算法实现而没有证明或者容易理解的解释。我说下自己对kosaraju算法的理解思路。这个算法名字我不会读，搜了半天看到本尊，发现他长得像印度人，也就释然了。回正题。kosaraju算法用来求一个有向图的所有强连通分量，算法很简单，但是理解起来有点麻烦，我是这么觉得。但是跟无向图的连通分量求法结合起来，就非常容易理解了。所以理解这个Korasaju算法的前提是你理解无向图所有连通分量的算法，这个算法相当图森破。
先看无向图的连通分量求法，其实无向图的连通分量就都是强连通分量。无向图的强连通分量就是用DFS算法顺序遍历邻接表时顺道干点小动作，写下代码更直观一些：

#define maxN 1024
int marked[maxN];//用于记录某个点是否被访问过，0为没有被临幸过，1为被临幸过
int id[maxN];//记录每个点所属的连通分量
int count;//记录连通分量总数目
void cc(graph *g){
    int i;
    memset(marked,0,sizeof(marked));
    memset(id,0,sizeof(id));
    count=0;
    for(i=0;i<g->V;i++){//之所以这里用循环就是因为g指向的无向图可能不是一个连通图，而是由多个连同分量组成
        if(!marked[i]){dfs(g,i); count++;}
    }
}


void dfs(graph *g,int v){
    graphNode *t;
    marked[v]=1;
    id[v]=count;
    t=g->adjlist[v].next;//t指向v的邻接点
    while(t){
        if(!marked[t->key]){dfs(g,t->key);}//这里是重点，就是你发现v到t->key有路径就把它算到跟自己在一个连通分量里了，这里有一个隐性前提，就是你提前知道t->key一定可以到v，所以你发现v可以到t->key的时候，你毫不犹豫把它算为跟自己一伙儿的了。Korasaju算法不同书上有不同的表述，区别是先遍历图g还是先遍历图g的逆向图，这只是顺序的区别。我把我看得版本完整说一下：（1）先DFS遍历图g的逆向图，记录遍历的逆后序。（什么叫逆后序？逆后序就是DFS时后序的逆序，注意逆后序不一定为DFS的前序。DFS前序为，访问某个顶点前，把它push进队列。DFS后序为访问完某个顶点后才把它push进队列。而DFS逆后序为访问完某个顶点后把它push进一个栈中。当DFS遍历完整个图后，后序队列的输出与逆后序栈的输出正好相反。）（2）然后按着图g逆向图的DFS遍历的逆后序序列遍历图g求所有的强连通分量，这一步的过程跟无向图求所有连通分量的算法一模一样！按着这里说的遍历顺序重复无向图求所有连通分量的步骤求出来的就是有向图的所有强连通分量，为什么呢？因为我们完成第一步后，按着第一步得到的逆后序要对有向图g进行DFS遍历的前一刻，前面这段过程就相当于我们完成了对这幅有向图g一个加工，把它加工成了一个无向图！也就是说，这个加工实现了我注释开头提到的那个隐性前提。所以后面按着无向图求所有连通分量的步骤求出来的就是有向图g的所有强连通分量。举个例子，比如有向图3->5->4->3，它的逆向图为3->4->5->3（你最好在纸上画下，就是个三角循环图），从逆向图的顶点3开始DFS，得到的逆后续为3，4,5 。按着这个顺序对原图进行DFS，DFS(3)时遇到5，则5肯定跟3在一个强连通分量中（为什么？因为我们逆向图DFS(5)时肯定能到达3，这就是隐形前提。所以正向图DFS(3)遇到5时，我们毫不犹豫把它算到自己一个强连通分量中。）
        t=t->next;
    }
}