Kosaraju算法：求有向图的强连通分量

算法思路：

找到一个合理顺序，使得我们只需要按照这个顺序进行DFS遍历，那么每一次的DFS就可以使我们得到一个强连通分量（SCC）

如图

若遍历顺序由B中顶点开始，则需经过两个DFS遍历，可顺利找到A和B两个SCC，

若从A中顶点开始，则只经过一次DFS遍历，无法找到两个SCC

因此关键是如何让DFS以正确的顺序开始遍历（即由B开始）

由图可知：

不管从A开始DFS，还是从B开始DFS，因为A到B有一条边，所以最后退出DFS的点一定在A上，若选最后退出DFS的点为始点（位于A中）并对上图的 反图 进行一次DFS，则可以得到图中的两个SCC。

由此得到以下算法步骤：

1. 对有向图G做DFS（第一次），按退出DFS函数的顺序（B先退出，A后退出）将顶点加入数组finished[]中（此时深度大的顶点（B）在前，深度小的顶点（A）在后）

2. 求G的反图Gr

3. 对反图Gr按finished数组中从后到前的顺序做DFS（第二次），遍历结束便可得到有向图中的所有SCC

算法如下（C版，以十字链表为例）

主函数

void Kosaraju(OLGraph G)
{
    int i, j;

    //第一次DFS
    DFS_Traverse_SCC(G);

    //逆置有向图
    InverseGraph(&G);

    //第二次DFS遍历
    for (i = 0; i < G.vexnum; i++)
        visited[i] = FALSE;

    printf("\n强连通分量为： \n");

    for (i = G.vexnum - 1; i >= 0; i--)     //按finished数组的倒序DFS遍历反图
    {
        if (!visited[finished[i]])
        {
            DFS_SCC_2(G, finished[i]);
            printf("\n");
        }
    }
}

第一次DFS：

void DFS_Traverse_SCC(OLGraph G)
{
    int i;

    for (i = 0; i < G.vexnum; i++)      //初始化访问标记数组
        visited[i] = FALSE;

    count = 0;

    for (i = 2; i < G.vexnum; i++)      //顶点可随机选择，若是连通图，则只执行一次
        if (!visited[i])
            DFS_SCC_1(G, i);
}

//第一次DFS
void DFS_SCC_1(OLGraph G, int i)
{
    ArcBox *p;
    visited[i] = TRUE;                  //标记该顶点已访问

    while (p)
    {
        if (!visited[p->headvex])
            DFS_SCC_1(G, p->headvex);
        p = p->taillink;
    }

    finished[count++] = i;              //若退出DFS则将该顶点加入finished数组中
}

逆置有向图：

//逆置有向图
void InverseGraph(OLGraph *G)
{
    int i, t;
    ArcBox *tmp, *q;
    ArcBox *p = NULL;
    VertexNode *h;

    for (i = 0; i < (*G).vexnum; i++)
    {
        h = &((*G).xlist[i]);           //对顶点表的顶点依次操作
        if (h->firstout)                
            p = h->firstout;

            tmp = h->firstout;          //将顶点的firstout 与 firstin互换
            h->firstout = h->firstin;
            h->firstin = tmp;

            while (p)                   //对顶点指向的出边表操作（出边表与入边表操作一个就行,因为都包含在边表中）
            {
                q = p;
                p = p->taillink;        //p指向下个顶点

                t = q->headvex;         //vex值互换
                q->headvex = q->tailvex;
                q->tailvex = t;

                tmp = q->headlink;      //link值互换
                q->headlink = q->taillink;
                q->taillink = tmp;
            }

    }
}

运行结果

A点开始遍历 C点开始遍历