0001 template <typename Tv, typename Te> //基于DFS的拓扑排序算法 0002 Stack<Tv>* Graph<Tv, Te>::tSort ( int s ) { //assert: 0 <= s < n 0003 reset(); int clock = 0; int v = s; 0004 Stack<Tv>* S = new Stack<Tv>; //用栈记录排序顶点 0005 do { 0006 if ( UNDISCOVERED == status ( v ) ) 0007 if ( !TSort ( v, clock, S ) ) { //clock并非必需 0008 while ( !S->empty() ) //任一连通域(亦即整图)非DAG 0009 S->pop(); break; //则不必继续计算,故直接返回 0010 } 0011 } while ( s != ( v = ( ++v % n ) ) ); 0012 return S; //若输入为DAG,则S内各顶点自顶向底排序;否则(不存在拓扑排序),S空 0013 } 0014 0015 template <typename Tv, typename Te> //基于DFS的拓扑排序算法(单趟) 0016 bool Graph<Tv, Te>::TSort ( int v, int& clock, Stack<Tv>* S ) { //assert: 0 <= v < n 0017 dTime ( v ) = ++clock; status ( v ) = DISCOVERED; //发现顶点v 0018 for ( int u = firstNbr ( v ); -1 < u; u = nextNbr ( v, u ) ) //枚举v的所有邻居u 0019 switch ( status ( u ) ) { //并视u的状态分别处理 0020 case UNDISCOVERED: 0021 parent ( u ) = v; type ( v, u ) = TREE; 0022 if ( !TSort ( u, clock, S ) ) //从顶点u处出发深入搜索 0023 return false; //若u及其后代不能拓扑排序(则全图亦必如此),故返回并报告 0024 break; 0025 case DISCOVERED: 0026 type ( v, u ) = BACKWARD; //一旦发现后向边(非DAG),则 0027 return false; //不必深入,故返回并报告 0028 default: //VISITED (digraphs only) 0029 type ( v, u ) = ( dTime ( v ) < dTime ( u ) ) ? FORWARD : CROSS; 0030 break; 0031 } 0032 status ( v ) = VISITED; S->push ( vertex ( v ) ); //顶点被标记为VISITED时,随即入栈 0033 return true; //v及其后代可以拓扑排序 0034 }