【图论】Kosaraju算法详解-蒲公英云

【图论】Kosaraju算法详解

桃扇骨 2023-07-24 09:29 89阅读 0赞

讲 Kosaraju 算法之前要先知道什么是强连通分量（SCC）

强连通分量

对于一个有向图顶点的子集 S ，如果在 S 内取两个顶点 u 和 v ，都能找到一条从 u 到 v 的路径，那么就称 S 是强连通的。
如果在强连通的顶点集合 S 中加入其他任意顶点集合后，它都不再是强连通的，那么就称 S 是原图的一个强连通分量（SCC:strongly connected component）。
任意有向图都可以分解成若不相干的强连通分量，这就是强连通分量分解。
把分解后的强连通分量缩成一个顶点，就得到了一个DAG（有向无环图）。

如图，图中有 3 个强连通分量（SCC），将三个强连通分量缩成一个顶点，就得到了有向无环图（DAG）。
在这里插入图片描述

Kosaraju 算法

Kosaraju 算法可以计算出一个有向图的强连通分量（SCC）。
Kosaraju 算法基于两个原理：

（1）一个有向图 G，把 G 的所有的边反向，建立反图 rG，反图 rG 不会改变原图 G 的强连通性。也就是说，图 G 的 SCC 数量与 rG 的 SCC 数量相同。

（2）对原图 G 和反图 rG 各做一次 DFS，可以确定 SCC 数量。
对原图 G 做一次 DFS 是为了确定点的先后顺序，用到了拓扑排序。在DFS过程中，把递归到最底层的那个点标记为最小，然后回退过程中，其他点的标记逐个递增。即优先级小的点先存，优先级大的点后存。
对反图 rG 做一次 DFS ，顺序从标记最大的点开始到最小的点。为什么顺序要相反？因为在反图中，方向相对于原图都相反了，优先级大的点由出度多，变成了入度多，那么 DFS 过程中就会被反边堵住，也就是说，此时能搜索到的点都是同个强连通分量的点。按照这个顺序依次搜索下去。

步骤：

（1）先记录原图 G 和反图 rG
（2）对原图所有的点 DFS 一遍，标记点的先后顺序
（3）根据点的逆序 DFS 一遍，能搜到的点就是在同一个强连通分量。

例题： HDU - 1269 迷宫城堡

题意： 一个有向图，有 n 个点（n <= 10000）和 m 条边（m <= 100000）。判断整个图是否强连通，如果是，输出 “Yes”，否则，输出“No”。

思路： Kosaraju 算法模板题，直接求整个图是否为强连通分量。

Code：

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 100010;
vector<int> G[N],rG[N];
vector<int> S;  // 存第一次dfs1()的结果，即标记点的先后顺序，优先级小的点先进
int vis[N];    // vis[i]标记第一次dfs1()点i是否访问过
int sccno[N];  // sccno[i]标记点i属于第几个强连通分量，同时记录dfs2()过程中点i是否访问过
int cnt;    //cnt表示强连通分量的个数
void dfs1(int u){ 
    if(vis[u])  return;
    vis[u] = 1;
    for(int i=0; i<G[u].size(); i++)
        dfs1(G[u][i]);
    S.push_back(u); //记录点的先后顺序，按照拓扑排序，优先级大的放在S的后面
}
void dfs2(int u){ 
    if(sccno[u])    return;
    sccno[u] = cnt;
    for(int i=0; i<rG[u].size(); i++)
        dfs2(rG[u][i]);
}
void Kosaraju(int n) { 
    cnt = 0;
    S.clear();
    memset(vis,0,sizeof(vis));
    memset(sccno,0,sizeof(sccno));
    for(int i=1; i<=n; i++) //搜索所有点
        dfs1(i);
    for(int i=n-1; i>=0; i--){ 
        if(!sccno[S[i]]){ 
            cnt++;
            dfs2(S[i]);
        }
    }
}
int main() { 
    int n,m,u,v;
    //坑点，这里 n 或者 m 都不能为 0 
    while(cin >> n >> m && (n || m)) { 
        for(int i=0; i<n; i++) { 
            G[i].clear();
            rG[i].clear();
        }
        for(int i=0; i<m; i++) { 
            cin >> u >> v;
            G[u].push_back(v);  // 原图
            rG[v].push_back(u); // 反图
        }
        Kosaraju(n);
        cnt==1? cout<<"Yes"<<endl:cout<<"No"<<endl;
    }
    return 0;
}