Kosaraju算法是求有向图强连通分量的经典算法,这个算法在算法导论第三版22.5节有详细介绍(包括正确性证明),这里简要回顾一下算法流程
Kosaraju算法流程(针对有向图G)
1.对G进行深度优先搜索,遍历完每一个顶点的dfs树后(此时该顶点变为黑色),将每一个顶点按变成黑色的逆序放入finish_time数组
2.求出G的转置图G’
3.利用finish_time选取G’中尚未被dfs访问的顶点中完成时间最大的顶点,从该顶点出发dfs,访问到的顶点构成一个强连通分量.重复该步骤,当G’中所有顶点均被访问完毕后就获得了所有的强连通分量
C++代码(简单易懂,就不注释了)
#include<iostream>#include<vector>#include<queue>#include<set>usingnamespacestd;#include"graph.h"constintN=6;voiddfs(size_t cur,Graph&_graph,vector<bool>&visited,vector<size_t>&finish_time,size_t&i){visited[cur]=true;for(EdgeNode*run=_graph.getFirstEdge(cur);run!=nullptr;run=_graph.nextEdge(run)){if(visited[run->vertex_id]==false){dfs(run->vertex_id,_graph,visited,finish_time,i);}}finish_time[--i]=cur;}voiddfs_on_t_graph(size_t cur,Graph&_graph,vector<bool>&visited,vector<set<size_t>>&SCC){visited[cur]=true;SCC.back().insert(cur);for(EdgeNode*run=_graph.getFirstEdge(cur);run!=nullptr;run=_graph.nextEdge(run)){if(visited[run->vertex_id]==false){dfs_on_t_graph(run->vertex_id,_graph,visited,SCC);}}}intmain(){Graphg(N);Graphg_reverse(N);vector<pair<size_t,size_t>>edge{{0,1},{0,2},{1,3},{2,3},{2,4},{3,0},{3,5},{4,5}};for(constauto&p:edge){g.insertEdge(p.first,p.second);g_reverse.insertEdge(p.second,p.first);}vector<bool>visited(N,false);vector<size_t>finish_time(N);size_t j=N;for(size_t i=0;i<visited.size();++i){if(!visited[i]){dfs(i,g,visited,finish_time,j);}}vector<set<size_t>>SCC;SCC.reserve(N);visited.assign(visited.size(),false);for(size_t i=0;i<finish_time.size();++i){if(visited[finish_time[i]]){continue;}SCC.push_back(set<size_t>());dfs_on_t_graph(finish_time[i],g_reverse,visited,SCC);}for(size_t i=0;i<SCC.size();++i){cout<<"第"<<i+1<<"个强连通分量"<<endl;for(constauto&p:SCC[i]){cout<<p+1<<" ";}cout<<endl;}return0;}graph.h内容
#pragmaonce#include<vector>structEdgeNode{size_t vertex_id;EdgeNode*next=nullptr;EdgeNode(size_t&v):vertex_id(v){}};classGraph{public:Graph(constsize_t&N):vertex_list(N,nullptr){};~Graph();boolinsertEdge(size_t u,size_t v){if(u!=v&&u<vertex_list.size()&&v<vertex_list.size()){if(vertex_list[u]==nullptr){vertex_list[u]=newEdgeNode(v);}else{EdgeNode*t=newEdgeNode(v);t->next=vertex_list[u];vertex_list[u]=t;}returntrue;}returnfalse;}booldeleteEdge(size_t u,size_t v){if(u!=v&&u<vertex_list.size()&&v<vertex_list.size()){if(vertex_list[u]==nullptr){returnfalse;}EdgeNode*run=vertex_list[u];EdgeNode*pre=nullptr;while(run!=nullptr){if(run->vertex_id==v)break;pre=run;run=run->next;}if(run==nullptr){returnfalse;}if(pre==nullptr){vertex_list[u]=run->next;}else{pre->next=run->next;}deleterun;returntrue;}returnfalse;}EdgeNode*getFirstEdge(size_t u){returnvertex_list[u];}EdgeNode*nextEdge(EdgeNode*cur){if(cur==nullptr)returnnullptr;returncur->next;}private:vector<EdgeNode*>vertex_list;};Graph::~Graph(){if(vertex_list.empty())return;for(size_t i=vertex_list.size()-1;;--i){EdgeNode*run=vertex_list[i];while(run!=nullptr){vertex_list[i]=run->next;deleterun;run=vertex_list[i];}vertex_list.pop_back();if(i==0)break;}}
