尧图网站建设 
Kosaraju算法是求有向图强连通分量的经典算法,这个算法在算法导论第三版22.5节有详细介绍(包括正确性证明),这里简要回顾一下算法流程Kosaraju算法流程(针对有向图G)1.对G进行深度优先搜索,遍历完每一个顶点的dfs树后(此时该顶点变为黑色),将每一个顶点按变成黑色的逆序放入finish_time数组2.求出G的转置图G’3.利用finish_time选取G’中尚未被dfs访问的顶点中完成时间最大的顶点,从该顶点出发dfs,访问到的顶点构成一个强连通分量.重复该步骤,当G’中所有顶点均被访问完毕后就获得了所有的强连通分量C代码(简单易懂,就不注释了)#includeiostream#includevector#includequeue#includesetusingnamespacestd;#includegraph.hconstintN6;voiddfs(size_t cur,Graph_graph,vectorboolvisited,vectorsize_tfinish_time,size_ti){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,vectorboolvisited,vectorsetsize_tSCC){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);vectorpairsize_t,size_tedge{{0,1},{0,2},{1,3},{2,3},{2,4},{3,0},{3,5},{4,5}};for(constautop:edge){g.insertEdge(p.first,p.second);g_reverse.insertEdge(p.second,p.first);}vectorboolvisited(N,false);vectorsize_tfinish_time(N);size_t jN;for(size_t i0;ivisited.size();i){if(!visited[i]){dfs(i,g,visited,finish_time,j);}}vectorsetsize_tSCC;SCC.reserve(N);visited.assign(visited.size(),false);for(size_t i0;ifinish_time.size();i){if(visited[finish_time[i]]){continue;}SCC.push_back(setsize_t());dfs_on_t_graph(finish_time[i],g_reverse,visited,SCC);}for(size_t i0;iSCC.size();i){cout第i1个强连通分量endl;for(constautop:SCC[i]){coutp1 ;}coutendl;}return0;}graph.h内容#pragmaonce#includevectorstructEdgeNode{size_t vertex_id;EdgeNode*nextnullptr;EdgeNode(size_tv):vertex_id(v){}};classGraph{public:Graph(constsize_tN):vertex_list(N,nullptr){};~Graph();boolinsertEdge(size_t u,size_t v){if(u!vuvertex_list.size()vvertex_list.size()){if(vertex_list[u]nullptr){vertex_list[u]newEdgeNode(v);}else{EdgeNode*tnewEdgeNode(v);t-nextvertex_list[u];vertex_list[u]t;}returntrue;}returnfalse;}booldeleteEdge(size_t u,size_t v){if(u!vuvertex_list.size()vvertex_list.size()){if(vertex_list[u]nullptr){returnfalse;}EdgeNode*runvertex_list[u];EdgeNode*prenullptr;while(run!nullptr){if(run-vertex_idv)break;prerun;runrun-next;}if(runnullptr){returnfalse;}if(prenullptr){vertex_list[u]run-next;}else{pre-nextrun-next;}deleterun;returntrue;}returnfalse;}EdgeNode*getFirstEdge(size_t u){returnvertex_list[u];}EdgeNode*nextEdge(EdgeNode*cur){if(curnullptr)returnnullptr;returncur-next;}private:vectorEdgeNode*vertex_list;};Graph::~Graph(){if(vertex_list.empty())return;for(size_t ivertex_list.size()-1;;--i){EdgeNode*runvertex_list[i];while(run!nullptr){vertex_list[i]run-next;deleterun;runvertex_list[i];}vertex_list.pop_back();if(i0)break;}} Kosaraju强连通分量算法
Kosaraju算法是求有向图强连通分量的经典算法,这个算法在算法导论第三版22.5节有详细介绍(包括正确性证明),这里简要回顾一下算法流程Kosaraju算法流程(针对有向图G)1.对G进行深度优先搜索,遍历完每一个顶点的dfs树后(此时该顶点变为黑色),将每一个顶点按变成黑色的逆序放入finish_time数组2.求出G的转置图G’3.利用finish_time选取G’中尚未被dfs访问的顶点中完成时间最大的顶点,从该顶点出发dfs,访问到的顶点构成一个强连通分量.重复该步骤,当G’中所有顶点均被访问完毕后就获得了所有的强连通分量C代码(简单易懂,就不注释了)#includeiostream#includevector#includequeue#includesetusingnamespacestd;#includegraph.hconstintN6;voiddfs(size_t cur,Graph_graph,vectorboolvisited,vectorsize_tfinish_time,size_ti){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,vectorboolvisited,vectorsetsize_tSCC){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);vectorpairsize_t,size_tedge{{0,1},{0,2},{1,3},{2,3},{2,4},{3,0},{3,5},{4,5}};for(constautop:edge){g.insertEdge(p.first,p.second);g_reverse.insertEdge(p.second,p.first);}vectorboolvisited(N,false);vectorsize_tfinish_time(N);size_t jN;for(size_t i0;ivisited.size();i){if(!visited[i]){dfs(i,g,visited,finish_time,j);}}vectorsetsize_tSCC;SCC.reserve(N);visited.assign(visited.size(),false);for(size_t i0;ifinish_time.size();i){if(visited[finish_time[i]]){continue;}SCC.push_back(setsize_t());dfs_on_t_graph(finish_time[i],g_reverse,visited,SCC);}for(size_t i0;iSCC.size();i){cout第i1个强连通分量endl;for(constautop:SCC[i]){coutp1 ;}coutendl;}return0;}graph.h内容#pragmaonce#includevectorstructEdgeNode{size_t vertex_id;EdgeNode*nextnullptr;EdgeNode(size_tv):vertex_id(v){}};classGraph{public:Graph(constsize_tN):vertex_list(N,nullptr){};~Graph();boolinsertEdge(size_t u,size_t v){if(u!vuvertex_list.size()vvertex_list.size()){if(vertex_list[u]nullptr){vertex_list[u]newEdgeNode(v);}else{EdgeNode*tnewEdgeNode(v);t-nextvertex_list[u];vertex_list[u]t;}returntrue;}returnfalse;}booldeleteEdge(size_t u,size_t v){if(u!vuvertex_list.size()vvertex_list.size()){if(vertex_list[u]nullptr){returnfalse;}EdgeNode*runvertex_list[u];EdgeNode*prenullptr;while(run!nullptr){if(run-vertex_idv)break;prerun;runrun-next;}if(runnullptr){returnfalse;}if(prenullptr){vertex_list[u]run-next;}else{pre-nextrun-next;}deleterun;returntrue;}returnfalse;}EdgeNode*getFirstEdge(size_t u){returnvertex_list[u];}EdgeNode*nextEdge(EdgeNode*cur){if(curnullptr)returnnullptr;returncur-next;}private:vectorEdgeNode*vertex_list;};Graph::~Graph(){if(vertex_list.empty())return;for(size_t ivertex_list.size()-1;;--i){EdgeNode*runvertex_list[i];while(run!nullptr){vertex_list[i]run-next;deleterun;runvertex_list[i];}vertex_list.pop_back();if(i0)break;}}