每天一个数据结构知识——图的广度优先遍历BFS
图的广度优先遍历和树的广度优先遍历类似，树是层序遍历，从根节点出发找到其所有的孩子结点。而图的广度优先就是从一个结点开始，搜索所有的相邻节点。而图与树不同点在于，树不存在回路，所以搜索相邻的结点不会搜到已经访问过的结点，而图搜索相邻顶点时可能会重复访问。所以，图需要对每个顶点进行标记。
那么具体如何实现对图的广度优先遍历呢？之前了解到，树的层序遍历需要一个辅助队列，BFS也是采取类似的方法。这里我们主要用到两个图的基本操作，一个是寻找第一个相邻节点FirstNeighbor，一个是寻找相邻节点的下一个相邻节点NextNeighbor。同时定义一个bool型的数组visited[]标记每个顶点有没有被访问过。
算法如下：
void BFS(G,v){ //从顶点v出发遍历图G
visit(v);
visited(v)=true;
Enqueue(Q,v); //v进入队列Q
while(isempty(Q)){ //队列非空
Dequeue(Q,v); //队头出队
for(w=FirstNeighbor(G,v);w>=0;w=NextNeighbor){ //遍历与队头顶点相邻的所有顶点
if(!visited(w)){ //邻接节点没有被访问过
visit(w);
visited(w)=true;
Enqueue(Q,w); //访问并入队
}
}
}
}
总体来看，广度优先遍历和层序遍历从实现方式来看十分类似（因为树其实就是一个特殊的图），只是要记住广度优先遍历每次访问完需要标记，访问时也要排除掉标记的。但是图的存储方式不同遍历的次序也是不同的，邻接表的遍历次序是唯一的。
并且此方法对于非连接图的遍历也存在弊端，不过只需在遍历停止后，再遍历一遍visited[]数组，如果存在数组值为false，在以该节点为起始节点进行BFS遍历，直到没有没访问的节点即可。实现方法如下：
void BFSTraverse(G){
for(i=0;i<G.vexnum;i++)visited[i]=false; //初始化visited数组
InitQueue(Q);
for(i=0;i<G.vexnum;i++){
if(visited[i]==false){
BFS(G,i);
}
}
}
显然对于无向图，调用BFS的次数=连通分量数。BFS的空间复杂度，辅助队列最大为O（|v|）。此算法的主要开销来自于访问顶点和找到相邻的邻接点，对于邻接矩阵，寻找顶点邻接点的时间复杂度为O(v)，共有v个顶点因而查找所有顶点的邻接点的时间复杂度为O（v^2）。对于邻接表，查找每个顶点的邻接点只需O(E)的时间复杂度，总时间复杂度为O(V+E)。
因为我们在进行广度优先时避免了重复访问，因此有的边不需要经过就能访问到所有的点，那么我们把这些边去掉就得到了广度优先生成树。而由于邻接表不唯一可能遍历的序列不唯一，从而导致广度优先生成树也不唯一。由此，我们可以想到，对于非连通图的BFS可以得到广度优先森林。
在了解了广度优先搜索的原理后，下面我们开始学习其最重要的一个应用——求最短路径。最短路径问题有几个常见的场景：单源最短路径，每对顶点间的最短路径。BFS可以用来求无权图的单元最短路径。
我们只需在BFS算法的基础上增加两个数组，一个数组存放源节点到其他节点的距离，一个数组存放该路径的上一个顶点。实现方法如下：
void BFS_Min_Distance(G,u){
visited(u)=true;
for(i=0;i<G.vexnum;i++){d[i]=-1;
path[i]=-1;
}//初始化路径长度和路径前驱节点
d[u]=0;
EnQueue(Q,u);
while(isEmpty(Q)){
DeQueue(Q,u);//队头元素出队
for(w=FirstNeigobor(G,u);w>=0;w=NextNeighbor(G,u,w)){//访问邻接节点
while(!visited[w]){
d[w]=d[u]+1;
path[w]=u;
visited[w]=true;
EnQueue(Q,w);}
}//if
}//while
}
通过回溯path数组，我们可以找到最短路径，多么精妙的算法。同时我们可以发现，通过广度优先生成树的节点和根节点的距离就是最短路径。
