数据结构与算法之图的广度优先遍历

• 前要
• 图的广度优先遍历
• • 树 VS 图
  • • 树的层序遍历
    • 图——广度优先遍历
• 代码实现图广度优先遍历
• • 方法说明
  • 代码示例
  • • 算法存在的问题
  • 算法复杂度分析
  • 邻接矩阵存储的图
  • 邻接表存储的图
• 广度优先生成树
• • 广度优先生成森林
• 练习：有向图的 BFS 过程
• 知识回顾与重要考点

在学习图的广度优先算法时，需要先学习树的广度优先遍历 (层序遍历，树是一种特殊的图)
5.6 二叉树的层序遍历

^a54835

1. 树：不存在回路，搜索相邻的结点时，不可能搜索到已经访问过的结点
2. 图：存在回路，搜索相邻的结点时，可能搜索到已经访问过的结点，如上图

1. 若树非空，则根节点入队
2. 若队列非空，队头元素出队并访问，同时将该元素的孩子依次入队 ^241f33
3. 重复 2 直到队列为空。
   

1. 找到一个与顶点相邻的所有顶点
2. 标记那些顶点被访问过
3. 需要一个辅助队列。
   

• FirstNeighbor(G,x)：求图 G 中顶点 x 的第一个邻接点，若有则返回顶点号。若 x 没有邻接点或图中不存在 x，则返回 -1；
• NextNeighbor(G,x,y)：假设图 G 中顶点 y 是顶点 x 的一个邻接点，返回除 y 之外顶点 x 的下一个邻接点的顶点号，若 y 是 x 的最后一个邻接点，则返回 -1；
• bool visited[MAX_VEREX_NUM];//访问标记数组
  

bool visited[MAX_VERTEX_NUM]; //访问标记数组

//广度优先遍历
void BFS(Graph G,int v){ //从顶点v出发，广度优先遍历图G
	visit(v); //访问初始顶点v
	visited[v]=TRUE; //对v做已访问标记
	Enqueue(Q,v); //顶点v入队列Q
	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入队列
		  }
		}
	}
}

改进代码如下：

void BFSTraverse(Graph G){ //对图G进行广度优先遍历
	for(i=0;i=0;w=NextNeighbor(G,v,w)){
		  //检测v所有邻接点
		  if(!visited[w]){  //w为v的尚未访问的邻接顶点
		  	visit(w);  //访问顶点w
		  	visited[w]=TRUE;  //对w做已访问标记
		  	EnQueue(Q,w);  //顶点w入队列
		  }
		}
	}
}

1. 访问|V|个顶点需要 O(|V|) 的时间
2. 查找每个顶点的邻接点都需要 O(|V|) 的时间，而总共有|V|个顶点，时间复杂度= O ( ∣ V ∣ 2 ) O(|V|^2) O(∣V∣2)

1. 访问|V|个顶点需要 O ( ∣ V ∣ ) O(|V|) O(∣V∣)的时间
2. 查找各个顶点的邻接点共需要 O ( ∣ E ∣ ) O(|E|) O(∣E∣)的时间，时间复杂度= O ( ∣ V ∣ + ∣ E ∣ ) O(|V|+|E|) O(∣V∣+∣E∣)

原理同 代码实现图广度优先遍历 相类似。
广度优先生成树有广度优先遍历过程确定。由于邻接表的表示方式不唯一，因此基于邻接表的广度优先生成树不唯一。

对非连通图的广度优先遍历，可得到广度优先生成森林

思考：

1. 从 1 出发，需要调用几次 BFS 函数？
2. 从 7 出发，需要调用几次 BFS 函数？