0001 template <typename Tv, typename Te> //深度优先搜索DFS算法（全图）
0002 void Graph<Tv, Te>::dfs( Rank s ) { // s < n
0003    reset(); Rank clock = 0; //全图复位
0004    for ( Rank v = s; v < s + n; v++ ) //从s起顺次检查所有顶点
0005       if ( UNDISCOVERED == status( v % n ) ) //一旦遇到尚未发现者
0006          DFS( v % n, clock ); //即从它出发启动一次DFS
0007 } //如此可完整覆盖全图，且总体复杂度依然保持为O(n+e)
0008 
0009 template <typename Tv, typename Te> //深度优先搜索DFS算法（单个连通域）
0010 void Graph<Tv, Te>::DFS( Rank v, Rank& clock ) { // v < n
0011    dTime( v ) = clock++; status( v ) = DISCOVERED; //发现当前顶点v
0012    for ( Rank u = firstNbr( v ); - 1 != u; u = nextNbr( v, u ) ) //考查v的每一个邻居u
0013       switch ( status( u ) ) { //并视其状态分别处理
0014          case UNDISCOVERED : // u尚未发现，意味着支撑树可在此拓展
0015             type( v, u ) = TREE; parent( u ) = v; DFS( u, clock ); break;
0016          case DISCOVERED : // u已被发现但尚未访问完毕，应属被后代指向的祖先
0017             type( v, u ) = BACKWARD; break;
0018          default : // u已访问完毕（VISITED，有向图），则视承袭关系分为前向边或跨边
0019             type( v, u ) = ( dTime( v ) < dTime( u ) ) ? FORWARD : CROSS; break;
0020       }
0021    status( v ) = VISITED; fTime( v ) = clock++; //至此，当前顶点v方告访问完毕
0022 }