本文共 2772 字，大约阅读时间需要 9 分钟。

基本介绍

网上看了很多关于求解一个有向图的强连通分支个数的算法，其中最著名的莫过于：

Kosaraju 算法

看的比较晕！

过程如下：

1。 创建一个空的栈 S，并做一次 DFS 遍历。在 DFS 遍历中，当在递归调用 DSF 访问邻接顶点时，将当前顶点压入栈中； 2。 置换图（Transpose Graph）； 3。 从栈 S 中逐个弹出顶点 v，以 v 为源点进行 DFS 遍历。从 v 开始的 DFS 遍历将输出 v 关联的强连通分支。直到S中元素全部弹出。

算法原理理解

先说一下强连通分支：

比如上图中1，0，2属于一个强连通分支。 讲述之前先说一个自己理解的重要基本知识点：

在一个有向图中，如果s和v连接（之间连着路，但并不表示s到v可达或者v到s可达，只是说连着）。将这个有向图的所有路径取反，在邻接矩阵中对应着矩阵转置，如果： s能够抵达v，那么：在原图中，一定是v能够抵达s。

这个结论很明显，明显的不需要证明。然而就是这么一个结论，是理解本算法的最关键的一点。

很明显在第一步DFS过程中，依次入栈的元素是：

1，2，4，3，0。 这个不解释！我之前一直调试不对的原因是把入栈元素代码放在最前面了。

int DFS_1(int *map, int v,bool *visited,int N, stack
   
     &S){    visited[v] = 1;//v被访问过    //S.push(v);//入栈操作错误！    for (int i = 0; i < N; i++)    {        if (!visited[i] && map[v*maxnum+i])//二维数组访问            DFS_1(map, i, visited, N,S);    }    S.push(v);//这个入栈操作要放到这，才是对的    return 0;}
   

那么在原图反转之后

第一个出栈的是0，然后对它DFS，只要0能够遍历到的，都属于0所代表的强连通分支。比如0能访问1，则在原图中1能到0，又因为0能到1，所以0，1属于 一个强连通分支中。

上述理解似乎简单了点，因为没说一个很重要的点，那就是在第一次DFS入栈操作中，如果一个顶点能够遍历的都遍历完了，包括其子顶点也遍历完了，那么该顶点入栈。此时该顶点以下的元素（栈底）都是该顶点能够访问到的，至于以后入栈的元素，不管他，至少该顶点不能访问到。所以在第二次DFS过程中，该顶点能够遍历到的，只在其底部的顶点中找，和它上面的没关系。这就保证了该顶点第二次DFS能够得到属于它的强连通分支。

上面的有点啰嗦，不过有助于理解。

算法调试起来一直被一个点困扰着，后来再次理解算法时才发现。果然理解很重要！

代码

#include
   
    #include
    
     #include
     
      #define maxnum 100using namespace std;int main(){    int kosaraju(int *map, int *nmap, int N);    int N, M;    int map[maxnum][maxnum];    int nmap[maxnum][maxnum];    bool visited[maxnum];//表示顶点i是否被访问过    ifstream in("input.txt");    in >> N >> M;//读取顶点数和边数    memset(map, 0, sizeof(map));    memset(nmap, 0, sizeof(nmap));    memset(visited, 0, sizeof(visited));    int a,b;    for (int i = 0; i < M; i++)    {        in >> a >> b;        map[a][b] = 1;        nmap[b][a] = 1;    }    int cnt=kosaraju((int *)map, (int *)nmap, N);    cout << endl;    cout << "强连通分支个数" <
      
       << endl;    return 0;}int DFS_1(int *map, int v,bool *visited,int N, stack
       
         &S){    visited[v] = 1;//v被访问过    for (int i = 0; i < N; i++)    {        if (!visited[i] && map[v*maxnum+i])//二维数组访问            DFS_1(map, i, visited, N,S);    }    S.push(v);    return 0;}int DFS_2(int *nmap, int v, bool *visited, int N){    visited[v] = 1;//v被访问过    for (int i = 0; i < N; i++)    {        if (!visited[i] && nmap[v*maxnum + i])            DFS_2(nmap, i, visited, N);    }    return 0;}int kosaraju(int *map, int *nmap,int N){    stack
        
          S; int cnt = 0; bool visited[501]; while (!S.empty()) S.pop(); memset(visited, 0, sizeof(visited)); for (int i = 0; i < N; i++) { if (!visited[i]) DFS_1(map, i, visited, N, S); } memset(visited, 0, sizeof(visited)); cout << "出栈顺序："; while (!S.empty()) { int top = S.top(); if (!visited[top]) { DFS_2(nmap, top, visited, N); cnt++; } cout << top ; S.pop(); } return cnt;}
        
       
      
     
    
   

参考