0001 template <typename Tv, typename Te> //深度优先搜索DFS算法(全图) 0002 void Graph<Tv, Te>::dfs ( int s ) { //assert: 0 <= s < n 0003 reset(); int clock = 0; int v = s; //初始化 0004 do //逐一检查所有顶点 0005 if ( UNDISCOVERED == status ( v ) ) //一旦遇到尚未发现的顶点 0006 DFS ( v, clock ); //即从该顶点出发启动一次DFS 0007 while ( s != ( v = ( ++v % n ) ) ); //按序号检查,故不漏不重 0008 } 0009 0010 template <typename Tv, typename Te> //深度优先搜索DFS算法(单个连通域) 0011 void Graph<Tv, Te>::DFS ( int v, int& clock ) { //assert: 0 <= v < n 0012 dTime ( v ) = ++clock; status ( v ) = DISCOVERED; //发现当前顶点v 0013 for ( int u = firstNbr ( v ); -1 < u; u = nextNbr ( v, u ) ) //枚举v的所有邻居u 0014 switch ( status ( u ) ) { //并视其状态分别处理 0015 case UNDISCOVERED: //u尚未发现,意味着支撑树可在此拓展 0016 type ( v, u ) = TREE; parent ( u ) = v; DFS ( u, clock ); break; 0017 case DISCOVERED: //u已被发现但尚未访问完毕,应属被后代指向的祖先 0018 type ( v, u ) = BACKWARD; break; 0019 default: //u已访问完毕(VISITED,有向图),则视承袭关系分为前向边或跨边 0020 type ( v, u ) = ( dTime ( v ) < dTime ( u ) ) ? FORWARD : CROSS; break; 0021 } 0022 status ( v ) = VISITED; fTime ( v ) = ++clock; //至此,当前顶点v方告访问完毕 0023 }