对于一个有向无环图,它的拓扑排序是指它的所有顶点构成的一个有序序列,使得任意一条有向边一定从该有序序列的靠前顶点指向靠后顶点,对于没有有向边关联的两个顶点它们在拓扑序列中的顺序任意dfs求拓扑排序的算法思路是把有向无环图的顶点按dfs完成时间从大到小依次排列所得的序列即为拓扑有序序列利用归纳法可以证明只要在对从一个顶点出发的dfs结束后将该顶点插入当前获得的部分序列的最前面,则对图的dfs结束后获得的序列中的顶点一定按完成时间从大到小依次排列从而构成拓扑有序序列。dfs算法的正确性证明可参考算法导论第三版22.4节使用队列生成拓扑排序的算法比较简单合格的数据结构教科书上都会介绍这里直接看最后的代码即可很容易理解需要提及的是在使用队列生成拓扑排序时,之所以当剩下的顶点入度均不为0时图中存在有向圈是因为从剩下顶点中的任意一个出发沿顶点的入边走到下一个和已经过的顶点都不同的下一个顶点的过程是不可能永远进行下去的(因为剩下的顶点数目是有限的)因而必然在某一步通过入边抵达的下一个顶点就是之前经过的顶点从该顶点出发沿经过顶点的顺序的逆序前进最终就回到了出发顶点这就是一个有向圈。拓扑排序两种算法的C代码实现(dfs和队列)#includeiostream#includevector#includeutility#includequeue#includelist#includegraph.husingnamespacestd;constintN6;booldfs(Graphg,listsize_ttop_seq,size_t cur,vectorboolvisited,vectorboolvisiting){visited[cur]true;visiting[cur]true;for(EdgeNode*rung.getFirstEdge(cur);run!nullptr;rung.nextEdge(run)){if(visited[run-vertex_id]false){if(dfs(g,top_seq,run-vertex_id,visited,visiting)false){returnfalse;}}elseif(visiting[run-vertex_id]){returnfalse;}}top_seq.insert(top_seq.begin(),cur);visiting[cur]false;returntrue;}intmain(){Graphg(N);vectorpairsize_t,size_tedge{{0,1},{0,3},{1,5},{2,1},{2,5},{4,0},{4,1},{4,5}};for(constautorun:edge){g.insertEdge(run.first,run.second);}vectorintdegree(N,0);for(size_t i0;iN;i){for(EdgeNode*rung.getFirstEdge(i);run!nullptr;rung.nextEdge(run)){degree[run-vertex_id];}}queuesize_twork_queue;for(size_t i0;idegree.size();i){if(degree[i]0){work_queue.push(i);}}vectorsize_ttopology_seq;while(work_queue.empty()false){size_t curwork_queue.front();work_queue.pop();topology_seq.push_back(cur);for(EdgeNode*rung.getFirstEdge(cur);run!nullptr;rung.nextEdge(run)){if(degree[run-vertex_id]!0){--degree[run-vertex_id];if(degree[run-vertex_id]0){work_queue.push(run-vertex_id);}}}}cout队列算法运行结果endl;if(topology_seq.size()!N){cout有向图中存在环endl;}else{cout拓扑排序结果endl;for(constautorun:topology_seq){coutrun ;}coutendl;}coutDFS算法运行结果endl;vectorboolvisited(N,false);vectorboolvisiting(N,false);listsize_ttop_seq;size_t i0;for(;iN;i){if(visited[i]false){if(dfs(g,top_seq,i,visited,visiting)false){cout有向图中存在环endl;break;}}}if(iN){cout拓扑排序结果endl;for(constautorun:top_seq){coutrun ;}coutendl;}return0;}graph.h内容#pragmaonce#includevectorusingstd::vector;structEdgeNode{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;}}
有向无环图的拓扑排序
对于一个有向无环图,它的拓扑排序是指它的所有顶点构成的一个有序序列,使得任意一条有向边一定从该有序序列的靠前顶点指向靠后顶点,对于没有有向边关联的两个顶点它们在拓扑序列中的顺序任意dfs求拓扑排序的算法思路是把有向无环图的顶点按dfs完成时间从大到小依次排列所得的序列即为拓扑有序序列利用归纳法可以证明只要在对从一个顶点出发的dfs结束后将该顶点插入当前获得的部分序列的最前面,则对图的dfs结束后获得的序列中的顶点一定按完成时间从大到小依次排列从而构成拓扑有序序列。dfs算法的正确性证明可参考算法导论第三版22.4节使用队列生成拓扑排序的算法比较简单合格的数据结构教科书上都会介绍这里直接看最后的代码即可很容易理解需要提及的是在使用队列生成拓扑排序时,之所以当剩下的顶点入度均不为0时图中存在有向圈是因为从剩下顶点中的任意一个出发沿顶点的入边走到下一个和已经过的顶点都不同的下一个顶点的过程是不可能永远进行下去的(因为剩下的顶点数目是有限的)因而必然在某一步通过入边抵达的下一个顶点就是之前经过的顶点从该顶点出发沿经过顶点的顺序的逆序前进最终就回到了出发顶点这就是一个有向圈。拓扑排序两种算法的C代码实现(dfs和队列)#includeiostream#includevector#includeutility#includequeue#includelist#includegraph.husingnamespacestd;constintN6;booldfs(Graphg,listsize_ttop_seq,size_t cur,vectorboolvisited,vectorboolvisiting){visited[cur]true;visiting[cur]true;for(EdgeNode*rung.getFirstEdge(cur);run!nullptr;rung.nextEdge(run)){if(visited[run-vertex_id]false){if(dfs(g,top_seq,run-vertex_id,visited,visiting)false){returnfalse;}}elseif(visiting[run-vertex_id]){returnfalse;}}top_seq.insert(top_seq.begin(),cur);visiting[cur]false;returntrue;}intmain(){Graphg(N);vectorpairsize_t,size_tedge{{0,1},{0,3},{1,5},{2,1},{2,5},{4,0},{4,1},{4,5}};for(constautorun:edge){g.insertEdge(run.first,run.second);}vectorintdegree(N,0);for(size_t i0;iN;i){for(EdgeNode*rung.getFirstEdge(i);run!nullptr;rung.nextEdge(run)){degree[run-vertex_id];}}queuesize_twork_queue;for(size_t i0;idegree.size();i){if(degree[i]0){work_queue.push(i);}}vectorsize_ttopology_seq;while(work_queue.empty()false){size_t curwork_queue.front();work_queue.pop();topology_seq.push_back(cur);for(EdgeNode*rung.getFirstEdge(cur);run!nullptr;rung.nextEdge(run)){if(degree[run-vertex_id]!0){--degree[run-vertex_id];if(degree[run-vertex_id]0){work_queue.push(run-vertex_id);}}}}cout队列算法运行结果endl;if(topology_seq.size()!N){cout有向图中存在环endl;}else{cout拓扑排序结果endl;for(constautorun:topology_seq){coutrun ;}coutendl;}coutDFS算法运行结果endl;vectorboolvisited(N,false);vectorboolvisiting(N,false);listsize_ttop_seq;size_t i0;for(;iN;i){if(visited[i]false){if(dfs(g,top_seq,i,visited,visiting)false){cout有向图中存在环endl;break;}}}if(iN){cout拓扑排序结果endl;for(constautorun:top_seq){coutrun ;}coutendl;}return0;}graph.h内容#pragmaonce#includevectorusingstd::vector;structEdgeNode{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;}}
