0001 template <typename Tv, typename Te> //广度优先搜索BFS算法(全图) 0002 void Graph<Tv, Te>::bfs( Rank s ) { // s < n 0003 reset(); Rank dClock = 0; //全图复位 0004 for ( Rank v = s; v < s + n; v++ ) //从s起顺次检查所有顶点 0005 if ( UNDISCOVERED == status( v % n ) ) //一旦遇到尚未发现者 0006 BFS( v % n, dClock ); //即从它出发启动一次BFS 0007 } //如此可完整覆盖全图,且总体复杂度依然保持为O(n+e) 0008 0009 template <typename Tv, typename Te> //广度优先搜索BFS算法(单个连通域) 0010 void Graph<Tv, Te>::BFS( Rank v, Rank& dClock ) { // v < n 0011 Queue<Rank> Q; status( v ) = DISCOVERED; Q.enqueue( v ); dTime( v ) = dClock++; //起点入队 0012 for ( Rank fClock = 0; !Q.empty(); ) { //在Q变空之前,反复地 0013 if ( dTime( v ) < dTime( Q.front() ) ) //dTime的增加,意味着开启新的一代,因此 0014 dClock++, fClock = 0; //dTime递增,fTime复位 0015 v = Q.dequeue(); //取出首顶点v,并 0016 for ( Rank u = firstNbr( v ); -1 != u; u = nextNbr( v, u ) ) //考查v的每一个邻居u 0017 if ( UNDISCOVERED == status( u ) ) { //若u尚未被发现,则发现之 0018 status( u ) = DISCOVERED; Q.enqueue( u ); dTime( u ) = dClock; 0019 type( v, u ) = TREE; parent( u ) = v; //引入树边,拓展BFS树 0020 } else //若u已被发现,或者甚至已访问完毕,则 0021 type( v, u ) = CROSS; //将(v, u)归类于跨边 0022 status( v ) = VISITED; fTime( v ) = fClock++; //至此,v访问完毕 0023 } //for 0024 } //BFS