广度优先搜索(Breadth-First-Search)

bool visited[MAX_VERTEX_NUM];   

//访问标记数组

void BFSTraverse(Graph G){

//对图G进行广度优先遍历，设访问函数为visit()

for(i=0;i<G.vexnum,i++)

visited[i] = FALSE;   

//访问标记数组初始化

InitQueue(Q);   

//初始化辅助队列Q

for(i=0;i<G.vexnum;i++)   

//从0号顶点开始遍历

if(!visited[i])   

//对每个连通量调用一次BFS

BFS(G,i);   

//Vi未访问过，从Vi开始BFS

}

void BFS(Graph G, int V){

//从顶点v出发，广度优先遍历图G,算法借助一个辅助队列Q

visit(v);     

//访问初始顶点v

visited[v] = TRUE;     

//对v做已访问标记

Enqueue(Q,v);     

//顶点v入队列

while(! isEmpty(Q)){

DeQueue(Q,v);      

//顶点v出队列

for(w = FirstNeighbor(G,v); w>=0; w=NextNeighbor(G,v,w))

//检测v所有邻接点

if(! visited[w]){      

//w为v的尚未访问的邻接顶点

visit(w);     

//访问定点w

EnQueue(Q,w);      

//顶点w入队列

}

}

}