图的遍历 —— 广度优先遍历

与树的遍历类似，图的遍历指从图的某一节点出发，按照某种搜索方式对图中的所有节点都仅访问一次。图的遍历可以解决很多搜索问题，实际应用非常广泛。图的遍历根据搜索方式的不同，分为广度优先遍历和深度优先遍历。

图的遍历 —— 广度优先遍历

广度优先搜索（Breadth First Search，BFS）又被称为宽度优先搜索，是最常见的图搜索方法之一。

广度优先搜索指从某个节点（源点）出发，一次性访问所有未被访问的邻接点，再依次从这些已访问过的邻接点出发，一层一层地访问。如下图所示，广度优先遍历是按照广度优先搜索的方式对图进行遍历的。

假设源点为1，从1出发访问1的邻接点2、3，从2出发访问4，从3出发访问5，从4出发访问6，访问完毕。访问路径如下图所示。

广度优先遍历的秘籍：先被访问的节点，其邻接点先被访问。

根据广度优先遍历的秘籍，先来先服务，这可以借助于队列实现。

因为对每个节点只访问一次，所以可以设置一个辅助数组visited[i]=false，表示第i 个节点未被访问；visited[ i ]=true，表示第i 个节点已被访问。

【算法步骤】

① 初始化所有节点均未被访问，并初始化一个空队列。

② 从图中的某个节点v 出发，访问v 并标记其已被访问，将v入队。

③ 如果队列非空，则继续执行，否则算法结束。

④ 将队头元素v 出队，依次访问v 的所有未被访问的邻接点，标记已被访问并入队。转向步骤3。

【完美图解】

例如，一个有向图如下图所示

广度优先遍历：

① 初始化所有节点均未被访问，visited[i ]=false，i =1,2,…,6。并初始化一个空队列Q 。

② 从节点1出发，标记其已被访问，visited[1]=true，将节点1入队。

③ 将队头元素1出队，依次访问1的所有未被访问的邻接点2、3，标记其已被访问并将其入队。

④ 将队头元素2出队，将2的未被访问的邻接点4标记为已被访问，并将其入队。

⑤ 将队头元素3出队，3的邻接点2已被访问，将未被访问的邻接点5标记为已被访问，并将其入队。

⑥ 将队头元素4出队，4的邻接点3已被访问，将未被访问的邻接点6标记为已被访问，并将其入队。

⑦ 将队头元素5出队，5的邻接点4、6均已被访问，没有未被访问的邻接点。

⑧ 将队头元素6出队，6没有邻接点。

⑨ 队列为空，算法结束。广度优先遍历序列为1 2 3 4 5 6。

广度优先遍历经过的节点及边，被称为广度优先生成树。如果广度优先遍历非连通图，则每一个连通分量都会产生一棵广度优先生成树。

【算法实现】

① 基于邻接矩阵的广度优先遍历。

void BFS_AM(AMGragh G , int v){ //基于邻接矩阵的广度优先遍历
	int u , w;
	queue<int>Q;  //创建一个普通队列(先进先出)存放int 类型
	cout << G.Vex[v] << "\t";
	visited[v] = true;
	
	Q.push(v);  //将源点v 入队
	while(!Q.empty()){ //如果队列不为空
		u = Q.front(); //则取出队头元素并赋值给u
		Q.pop(); //将队头元素出队
		for(w = 0 ; w < G.vexnum ; w++){ //依次检查u 的所有邻接点
			if(G.Edge[u][w] && !visited[w]){ //u、w邻接并且w 未被访问
				cout << G.Vex[w] << "\t";
				visited[w] = true;
				Q.push(w);	
			}
		}
	}
}

② 基于邻接表的广度优先遍历

void BFS_AL(ALGragh G , int v){ //基于邻接表的广度优先遍历
	int u , w;
	AdjNode *p;
	queue<int>Q; //创建一个普通队列(先进先出)存放int 类型
	cout << G.Vex[v].data = "\t";

	visited[v] = true;
	Q.push(v); //将源点v 入队
	while(!Q.empty()){ //如果队列不空
		u = Q.front();  //则取出队头元素赋值给u
		Q.pop();  //将队头元素出队
		p = G.Vex[u].first;
		while(p){  //依次检查 u 的所有邻接点
			w = p->v; //w 为 u 的邻接点
			if(!visited[w]){ //w 未被访问
				cout << G.Vex[w].data << "\t";
				visited[w] = true;
				Q.push(w);
			}
			p = p->next;
		}
	}
}

③ 基于非连通图的广度优先遍历

void BFS_AL(ALGragh G){ //非连通图的广度优先遍历
	for(int i = 0 ; i < G.vexnum; i ++){ //对非连通图需要查漏点，检查未被访问的节点
		if(!visited[i]){ //i 未被访问，以i 为起点再次广度优先遍历
			BFS_AL(G , i); //基于邻接表，也可以替换为基于邻接矩阵的BFS_AM(G , i)
		}
	}
}

【算法分析】

广度优先遍历的过程实质上是对每个节点都搜索其邻接点的过程，图的存储方式不同，其算法复杂度也不同。

① 基于邻接矩阵的广度优先遍历算法。

查找每个节点的邻接点需要O (n )时间，共n 个节点，总的时间复杂度为O (n^2 )。这里使用了一个辅助队列，每个节点只入队一次，空间复杂度为O (n )。

② 基于邻接表的广度优先遍历算法。

查找节点vi 的邻接点需要O (d (vi ))时间，d (vi )为vi 的出度，对有向图而言，所有节点的出度之和等于边数e ；对无向图而言，所有节点的度之和等于2e ，因此查找邻接点的时间复杂度为O (e )，加上初始化时间O (n )，总的时间复杂度为O (n +e )。这里使用了一个辅助队列，每个节点只入队一次，空间复杂度为O (n )。