0001 template <typename Tv, typename Te> //广度优先搜索BFS算法(全图) 0002 void Graph<Tv, Te>::bfs ( int s ) { //assert: 0 <= s < n 0003 reset(); int clock = 0; int v = s; //初始化 0004 do //逐一检查所有顶点 0005 if ( UNDISCOVERED == status ( v ) ) //一旦遇到尚未发现的顶点 0006 BFS ( v, clock ); //即从该顶点出发启动一次BFS 0007 while ( s != ( v = ( ++v % n ) ) ); //按序号检查,故不漏不重 0008 } 0009 0010 template <typename Tv, typename Te> //广度优先搜索BFS算法(单个连通域) 0011 void Graph<Tv, Te>::BFS ( int v, int& clock ) { //assert: 0 <= v < n 0012 Queue<int> Q; //引入辅助队列 0013 status ( v ) = DISCOVERED; Q.enqueue ( v ); //初始化起点 0014 while ( !Q.empty() ) { //在Q变空之前,不断 0015 int v = Q.dequeue(); dTime ( v ) = ++clock; //取出队首顶点v 0016 for ( int u = firstNbr ( v ); -1 < u; u = nextNbr ( v, u ) ) //枚举v的所有邻居u 0017 if ( UNDISCOVERED == status ( u ) ) { //若u尚未被发现,则 0018 status ( u ) = DISCOVERED; Q.enqueue ( u ); //发现该顶点 0019 type ( v, u ) = TREE; parent ( u ) = v; //引入树边拓展支撑树 0020 } else { //若u已被发现,或者甚至已访问完毕,则 0021 type ( v, u ) = CROSS; //将(v, u)归类于跨边 0022 } 0023 status ( v ) = VISITED; //至此,当前顶点访问完毕 0024 } 0025 }