图的遍历——广度优先遍历BFS/BFT

7.3 图的遍历

• 7.3.2 图的深度优先遍历(Breadth First Traversal)

7.3.2 图的深度优先遍历(Breadth First Traversal)

1. 图的广度优先遍历基于广度优先搜索（breadth first search，BFS），广度优先搜索是从图中某一顶点v出发，在访问顶点v后再访问v的各个未曾被访问过的邻接顶点w1，w2，…，wk，然后再依次访问w1，w2，.…，wk 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点……如此下去，直到图中所有和顶点v由路径连通的顶点都被访问到为止。
   广度优先搜索是一种分层的搜索过程，它类似于树的层次遍历。
2. 图7-16（a）给出了一个从顶点A出发进行广度优先遍历的示例。
   
   图7-16（b）给出了由广度优先遍历得到的广度优先生成树，它由遍历时访问过的n个顶点和遍历时经历的n-l条边组成，各顶点旁边的数字标明了顶点被访问的顺序。
   从图7-16（a）中可以看出，搜索每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此，广度优先遍历不是一个递归的过程，其算法也不是递归的。为了实现逐层访问，算法中使用了一个队列，以记录刚才访问过的上一层和本层顶点，以便于向下一层访问。
3. 从指定的结点v开始进行广度优先搜索的算法思想：
   1）访问结点v，并标记v已枝访问，同时顶点v入队列。
   2）当队列空时算法结束，否则继续步骤(3)。
   3）队头顶点出队列为v。
   4）取顶点v的第一个邻接顶点w。
   5）若顶点w不存在，转步骤(3)：否则继续步骤(6)。
   6）若顶点w未被访问，则访问结点w.并标记w已被访问，同时顶点w入队列；否则继续步骤(7)。
   7）使w为顶点v的在原来w之后的下一个邻接顶点，转到步骤(5)。
4. 广度优先遍历 BFT 代码实现
   利用无向图邻接矩阵。

#include "AdjMatrixUndirGraph.h"		// 无向图邻接矩阵
#include ///广度优先搜索 BFS
template <class ElemType>
void BFS(const AdjMatrixUndirGraph<ElemType> &g, int v, void (*Visit)(const ElemType &))
// 初始条件：存在图g
// 操作结果：从顶点v出发进行广度优先搜索
{queue<int> q;int u, w;ElemType e;g.SetTag(v, VISITED);						// 作访问标志g.GetElem(v, e);							// 取顶点v的数据元素值Visit(e);									// 访问顶点vq.push(v);	                            // 顶点v入队while (!q.empty()){u=q.front();q.pop();for (w = g.FirstAdjVex(u); w != -1; w = g.NextAdjVex(u, w))if (g.GetTag(w) == UNVISITED)  // 对u尚未访问过的邻接顶点w进行访问{g.SetTag(w, VISITED);g.GetElem(w, e);Visit(e);q.push(w);}}
}///广度优先遍历 BFT
template <class ElemType>
void BFSTraverse(const AdjMatrixUndirGraph<ElemType> &g, void (*Visit)(const ElemType &))
// 初始条件：存在图g
// 操作结果：对图g进行广度优先遍历
{int v;for (v = 0; v < g.GetVexNum(); v++)g.SetTag(v, UNVISITED); // 对每个顶点作未访问标志for (v = 0; v < g.GetVexNum(); v++)if (g.GetTag(v) == UNVISITED)BFS(g, v, Visit); 	// 从尚未访问的顶点v开始进行广度优先搜索
}///广度优先遍历 BFT 非递归算法
template <class ElemType>
void BFSTraverse_nonrecursion(const AdjMatrixUndirGraph<ElemType> &g, void (*Visit)(const ElemType &))
{int v,w;ElemType e;for (v = 0; v < g.GetVexNum(); v++)g.SetTag(v, UNVISITED); // 对每个顶点作未访问标志queue<int> q;for (v = 0; v < g.GetVexNum(); v++){if(g.GetTag(v)==UNVISITED){g.SetTag(v, VISITED);						// 作访问标志g.GetElem(v, e);							// 取顶点v的数据元素值Visit(e);									// 访问顶点vq.push(v);	                            // 顶点v入队}while(!q.empty()){v=q.front();q.pop();for (w = g.FirstAdjVex(v); w != -1; w = g.NextAdjVex(v, w)){if (g.GetTag(w) == UNVISITED)  // 对u尚未访问过的邻接顶点w进行访问{g.SetTag(w, VISITED);g.GetElem(w, e);Visit(e);q.push(w);}}}}
}

注意：深度优先遍历和广度优先遍历都有一个每个顶点的for大循环，是为了走过每个顶点，避免顶点不连通的情况。
5. 算法效率
在图的广度优先遍历算法中，图中每一个顶点需进队列一次且仅进队列一次，而在遍历过程中是通过边来搜索邻接点的。所以，图的广度优先遍历算法的时间复杂度和图的深度优先遍历算法的时间复杂度类似.
（1）如果使用邻接表表示图，则其时间复杂度为O(n+e)。
（2）如果使用邻接矩阵表示图，则其时间复杂度为O(n^2)。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！