5.3.1图的遍历
图的遍历是指从图中的某一顶点出发，按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅访问一次。注意到树是一种特殊的图，所以树的遍历实际上也可以看作是一种特殊图的遍历。图的遍历是图的一种最基本的操作，其他许多操作都建立在图的遍历操作基础之上。
5.3.1广度优先搜索（Breadth-First-Search，BFS）
广度优先搜索（BFS）类似于二叉树的层序遍历算法，它的基本思想是：首先访问其实顶点v，接着由v出发，依次访问v的各个未访问过得邻接顶点w1，w2，……，wi，然后再依次访问w1，w2，……，wi的所有未访问过的邻接顶点；再从这些访问过的顶点出发，再访问它们所有未访问过得邻接顶点……依次类推，直到所有顶点都被访问过为止。类似的思想还将应用于Dijstra单源最短路径算法和Prim最小生成树算法。
广度优先搜索是一种分层的查找过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况，因此它不是一个递归的算法。为了实现逐层的访问，算法必须借助一个辅助队列，以记忆正在访问的顶点的一层顶点。
bool visited[MAX_VERTEX_NUM];//访问标记数组
void BFSTraverse(Grap G){
//对图G进行广度优先遍历，设访问函数为visit()
for(i=0;i<G.vexnum;i++)
visited[i]=false;//访问标记数组初始化
InitQueue(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，算法借助一个辅助队列Q
visit(v);//访问初始顶点v
visit[v]=true;//对v做已访问标记
enqueue(Q,v);//顶点v入队
while（!isEmpty(Q)）{
dequeue(Q,v);//顶点v出队列，并将顶点v的孩子结点入队
for(w=firstNeighbor(G,v);w>=0;w=NextNeighbor(G,v,w)){
//检测v的所有邻接点
if(!visited(w)){//w是v的尚未访问的邻接顶点
visit(w);
visited[w]=true;//对w做已访问标记
Enqueue(Q,w);//顶点w入队列
}
}
}
}辅助数组visited[]标志顶点是否被访问过，它的初始状态为FALSE。在图的遍历过程中，一旦某一个顶点vi被访问，就立即置visited[i]为TRUE,访问它被多次访问。
1、BFS算法的性能分析
无论是邻接表还是邻接矩阵的存储方式，BFS算法都需要借助一个辅助队列Q，n个顶点均需入队一次，在最坏的情况下，空间复杂度为O(|v|)。
当采用邻接表存储方式时，每个顶点都需要搜索一次（或入队一次），故时间复杂度为O(|V|)，在搜索任一顶点的邻接点时，每条边至少访问一次，故时间复杂度为O(|E|)，算法总的时间复杂度为O(|V|+|E|)。
当采用邻接矩阵存储方式时，查找每个顶点的邻接点所需时间为O(|V|)，故算法总的时间复杂度为O(|V|^2)。
2.BFS算法求解单源最短路径问题
如果G=(V,E)为非带权图，定义从顶点u到顶点v的最短路径d(u,v)为从u到v的任何路径最短的边数；如果从u到v没有通路，则d（u,v）=无穷。
使用BFS，我们可以求解一个满足上述定义的非带权图的最短路径问题，这是由广度优先搜索总是按距离由近到远来遍历图中每个人顶点的性质决定的。
void BFS_MIN_DISTANCE(Graph G,int u){
//d[i]表示从u到i结点的最短路径
for(i=0;i<G.vexnum;i++)
d[i]=无穷;//初始化路径长度
visited[u]=TRUE;
d[u]=0;
EnQueue(Q,u);
while(!isEmpty(Q){
Dequeue(Q,u);//队头元素u出队
for(w=firstNeighbor(G,u);w>=0;w=NextNeighbor(G,u,w)){
//检测v的所有邻接点
if(!visited(w)){//w是u的尚未访问的邻接顶点
visited[w]=true;//对w做已访问标记
d[w]=d[u]+1;//路径长度加1
Enqueue(Q,w);//顶点w入队列
}
}
}
}3.广度优先生成树
在广度遍历的过程中，我们可以得到一颗遍历树，称为广度遍历生成树，一给定图的邻接矩阵存储表示是唯一的，故其广度优先生成树也是唯一的，但由于邻接表存储表示不唯一，故其广度优先生成树也是不唯一的。
腾讯云开发者
