C语言：广度优先遍历算法

算法分析

深度优先遍历类似于树的层次遍历，它的基本过程如下：
①访问初始点 v，接着访问 v 的所有未被访问过的邻接点 v1，v2，…，vn。
②按照 v1，v2，…，vn的次序，访问每个顶点的所有未被访问过的邻接点。
③依次类推，直到图中所有和初始点 v 有路径的顶点都被访问过为止。

代码

bool visited[MAX_VERTEX_NUM]; //访问标记数组
void BFSTraverse(Graph G)
{
	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
{
	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
				visited[w] = TRUE; //对 w 做已访问标记
				EnQueue(Q,w); //顶点 w 入队列
			}
	}
}