广度优先遍历

广度优先遍历连通图是图的另外一种遍历策略，其基本思想是：

－step1、 从图中某个顶点V0出发，并访问此顶点；

－step2、 从V0出发，访问V0的各个未曾访问的邻接点W1，W2，…,Wk;然后,依此从W1,W2,…,Wk

出发访问各自未被访问的邻接点。

－step3、 重复step2，直到全部顶点都被访问为止。

具体的算法实现：

template <int max_size>

void Digraph<max_size> ::

breadth_first(void (*visit)(Vertex &)) const

/* Post: The function *visit has been performed at each vertex of the Digraph in breadth-first order.

Uses: Methods of class Queue. */

{

Queue q;

bool visited [max_size];

Vertex v, w, x;

for (all v in G) visited [v] = false;

for (all v in G)

if (!visited [v]) {

q.append (v);

while (!q.empty ( )){

q.retrieve (w);

if (!visited [w]) {

visited [w] = true; (*visit) (w);

for (all x adjacent to w) q.append (x); }

q.serve ( ); } }

}