2

为什么我们要创建图形的转置，然后在第二遍中在转置上运行 dfs。我尝试在线阅读正确性证明http://www.jeffreykarres.com/blog/kosaraju/但无法理解是有一些替代方法可以做到这一点，这很容易理解

这是我的算法实现，它将顶点和边的数量作为输入，然后将有向边作为输入（顶点编号为 0 到 n-1）

#include <bits/stdc++.h>
using namespace std;
void dfsForward(int src , vector<vector<int>> g , vector<bool> &vis, stack<int> &s ){
    vis[src]=true;
    for(int i=0;i<g[src].size();i++){
        if(!vis[g[src][i]])
         dfsForward(g[src][i],g,vis,s);
    }
    s.push(src);
}
void dfsRev(int src , vector<vector<int>> t , vector<bool> &vis, vector<int> &comp,int count ){
    vis[src]=true;
    for(int i=0;i<t[src].size();i++){
        if(!vis[t[src][i]]){
           comp.push_back(t[src][i]);
            dfsRev(t[src][i],t,vis,comp,count);
        }
    }
}
vector<vector<int>> kosaraju(vector<vector<int>> g,vector<vector<int>> t, int n){
    vector<bool> vis(n,false); 
    vector<bool> visRev(n,false); 
    vector<vector<int>> scc; 
    int count=0;
    stack<int> s;
    for(int i=0;i<n;i++){
        if(!vis[i])
         dfsForward(i,g,vis,s);
    }
    while(!s.empty()){
        int temp =s.top();
        s.pop();
        if(!visRev[temp]){
           count++;    
           vector<int> comp;
           comp.push_back(temp);
           dfsRev(temp,t,visRev,comp,count);
           scc.push_back(comp);
        }
    } 
    return scc;
}
int main() {
    int n,e,u,v;
    cin>>n>>e;
    vector<vector<int>> g(n);
    vector<vector<int>> t(n);
    for(int i=0;i<e;i++){
        cin>>u>>v;
        g[u].push_back(v);
        t[v].push_back(u);
    }
    cout<<"components are "<<endl;
    vector<vector<int>> scc = kosaraju(g,t,n);
    for(int i=0;i<scc.size();i++){
        vector<int> arr = scc[i];
        for(int j=0;j<arr.size();j++){ 
            cout<<arr[j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}
4

1 回答 1

2

Kosaraju 算法通过三个简单的步骤工作：

1.Reverse the Graph.

2. Apply DFS-Loop in Reverse Graph and calculate ordering of each vertex (we call 
   it finishig times).
3. Apply DFS-loops in Graph in descending order of finishing times.

（通过 DFS 循环，我的意思是图 G 的每个顶点中的 dfs）。

回答您的问题：为什么我们在第一步中反转图表???....

如您所知，图 G 和反向图 G' 中的 SCC 将始终相同。如果你考虑每个 SCC 一个单独的节点 N，G 和 G' 将是一个 DAG（直接无环图）。作为 DFS 的一个属性，DAG 中的最大完成时间将始终是 Graph 的同步顶点（没有出弧的顶点），在这种情况下为 N。因此，如果您从这个同步顶点 N 重新运行 DFS，它只会遍历那个特定的 SCC（形成 N）。因此，通过这种迭代方式，您将发现图中的所有 SCC。

于 2021-01-15T12:18:41.207 回答