0001 template <typename Tv, typename Te> //基于DFS的拓扑排序算法
0002 Stack<Tv>* Graph<Tv, Te>::tSort( Rank s ) { // assert: 0 <= s < n
0003    reset(); Rank clock = 0; //全图复位
0004    Stack<Tv>* S = new Stack<Tv>; //用栈记录排序顶点
0005    for ( Rank v = s; v < s + n; v++ ) //从s起顺次检查所有顶点
0006       if ( UNDISCOVERED == status( v % n ) ) //一旦遇到尚未发现者
0007          if ( !TSort( v, clock, S ) ) { //即从它出发启动一次TSort
0008             while ( !S->empty() ) //任一连通域（亦即整图）非DAG
0009                S->pop();
0010             break; //则不必继续计算，故直接返回
0011          }
0012    return S; //若输入为DAG，则S内各顶点自顶向底排序；否则（不存在拓扑排序），S空
0013 } //如此可完整覆盖全图，且总体复杂度依然保持为O(n+e)
0014 
0015 template <typename Tv, typename Te> //基于DFS的拓扑排序算法（单趟）
0016 bool Graph<Tv, Te>::TSort( Rank v, Rank& clock, Stack<Tv>* S ) { // v < n
0017    dTime( v ) = ++clock; status( v ) = DISCOVERED; //发现顶点v
0018    for ( Rank 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 }