7.3.2 广度优先搜索遍历图 算法 7.5 　　void BFSTraverse(MGraph G) 　{ 　　// 对以数组存储表示的图G进行广度优先搜索遍历 　　bool visited[G.vexnum];　　　　　　　　　　　// 附设访问标识数组 　　Queue Q;　　　　　　　　　　　　　　　　　　// 附设队列 Q 　　for (v=0; v<G.vexnum; ++v) visited[v] = FALSE; 　　InitQueue(Q，G.vexnum);　　　　　　　　　　　// 设置空队列 Q 　　for ( v=0; v<G.vexnum; ++v ) 　　　if ( !visited[v]) 　　　{ 　　　　　　　　// 从每一个未被访问的顶点出发进行广度优先搜索		由于广度优先搜索遍历要求先被访问的顶点的邻接点也先于后被访问的顶点的邻接点进行访问，因此在遍历过程中需要一个队列保存被访问顶点的次序，以便按照已被访问过的顶点的访问次序先后访问它们的未曾被访问过的邻接点。
	visited[v] = TRUE; VisitFunc(G.vexs[v]);　// 访问图中第 v 个顶点 　　　　EnQueue(Q, v); 　　　　　　　　　　　　　// v 入队列 　　　　while (!QueueEmpty(Q)) { 　　　　　DeQueue(Q, u); 　　　　　　　　　　　　// 队头元素出队并置为 u 　　　　　for ( w=0; w<G.vexnum; w++; ) 　　　　　　if ( G.arcs[u, w].adj && ! visited[w] ) { 　　　　　　　visited[w] = TRUE; VisitFunc(w);　　// 访问图中第 w 个顶点 　　　　　　　EnQueue(Q, w); 　　　　　　　　// 当前访问的顶点 w 入队列 Q 　　　　　} // if 　　　　} // while 　　　} // if 　　DestroyQueue(Q); 　} // BFSTraverse		第 u 个顶点的邻接点应该是邻接矩阵中第 u 行的非零元所在的列号。 　　由于队列中保存的是已被访问过的顶点，则待队列变空时说明所有已被访问的顶点的邻接点也都已经被访问过了。 　　遍历图的过程实质上是通过边或弧找邻接点的过程，其消耗时间取决于所采用的存储结构，因此若采用同样的存储结构，广度优先遍历的时间复杂度和深度优先遍历相同，由于算法7.5中的存储结构为邻接矩阵，因此算法7.5的时间复杂度为O(n2)。