0001 template <typename Tv, typename Te> //广度优先搜索（单个可达分量）
0002 void Graph<Tv, Te>::BFS(Rank v, Rank& dClock) { //0 <= v < n
0003    Queue<Rank> Q;  status(v) = DISCOVERED;  Q.enqueue(v);  dTime(v) = dClock++; //起点入队
0004    for (Rank fClock = 0; !Q.empty(); ) { //在Q变空之前，反复地
0005       if (dTime(v) < dTime(Q.front())) //dTime的增加，意味着开启新的一代，因此
0006          { dClock++;  fClock = 0; } //dTime递增，fTime复位
0007       v = Q.dequeue(); //取出首顶点v，并
0008       for (Rank u = firstNbr(v); -1 != u; u = nextNbr(v, u)) //考查v的每一个邻居u
0009          if (UNDISCOVERED == status(u)) { //若u尚未被发现，则发现之
0010             status(u) = DISCOVERED;  Q.enqueue(u);  dTime(u) = dClock;
0011             type(v, u) = TREE;  parent(u) = v; //引入树边，拓展BFS树
0012          } else //若u已被发现，或者甚至已访问完毕，则
0013             type(v, u) = CROSS; //将(v,u)归类于跨边
0014       status(v) = VISITED;  fTime(v) = fClock++; //至此，v访问完毕
0015    } //for
0016 } //BFS