0001 template <typename Tv, typename Te>
0002 Stack<Tv> Graph<Tv, Te>::tSort(Rank s) { //assert: 0 <= s < n
0003    reset();  Rank clock = 0; //全图复位
0004    Stack<Tv> S; //用栈记录排序顶点
0005    for (Rank v = s; v < s+n; v++) //从s起顺次检查所有顶点
0006       if (UNDISCOVERED == status(v%n)) //一旦遇到尚未发现者
0007          if (!TSort(v%n, clock, S)) { //即从它出发启动一次TSort
0008             while (!S.empty()) //若判定非DAG，则
0009                S.pop(); //清空栈后
0010             break; //直接返回
0011          }
0012    return S; //对于DAG，S内顶点自顶而下，即是一个拓扑排序
0013 } //tSort：覆盖全图
0014 template <typename Tv, typename Te>
0015 bool Graph<Tv, Te>::TSort(Rank v, Rank& clock, Stack<Tv>& S) { //v < n
0016    dTime(v) = clock++;  status(v) = DISCOVERED; //发现顶点v
0017    for (Rank u = firstNbr(v); -1 != u; u = nextNbr(v, u)) //枚举v的所有邻居u
0018       switch (status(u)) { //并视u的状态分别处理
0019          case UNDISCOVERED :
0020             parent(u) = v;  type(v, u) = TREE;
0021             if (!TSort(u, clock, S)) //从顶点u处出发深入搜索
0022                return false; //一旦判定不能拓扑排序，随即终止搜索
0023             break;
0024          case DISCOVERED :
0025             type(v, u) = BACK; //一旦发现后向边（非DAG），则
0026             return false; //不必深入，故返回并报告
0027          default : //VISITED(digraphs only)
0028             type(v, u) = dTime(v) < dTime(u) ? FORWARD : CROSS;
0029             break;
0030       }
0031    status(v) = VISITED;  fTime(v) = clock++;  S.push(vertex(v)); //顶点回溯即入栈
0032    return true; //可以拓扑排序
0033 } //TSort：覆盖当前可达分量