【算法】BFS—广度优先搜索
【算法】BFS—广度优先搜索
1.BFS介绍
2.连通图
3.BFS算法流程图
4.实例:poj3984迷宫问题
5.核心代码
参考：
《算法导论》
【算法入门】广度/宽度优先搜索(BFS) https://blog.csdn.net/raphealguo/article/details/7523411
广度优先搜索算法 https://blog.csdn.net/ywjun0919/article/details/8838491
poj3984 迷宫问题 https://blog.csdn.net/u012679707/article/details/79952123
1.BFS介绍
宽度优先搜索算法（BFS，又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。
已知图G=(V,E)和一个源顶点s，宽度优先搜索以一种系统的方式探寻G的边，从而“发现”s所能到达的所有顶点，并计算s到所有这些顶点的距离(最少边数)，该算法同时能生成一棵根为s且包括所有可达顶点的宽度优先树。对从s可达的任意顶点v，宽度优先树中从s到v的路径对应于图G中从s到v的最短路径，即包含最小边数的路径。该算法对有向图和无向图同样适用。
之所以称之为宽度优先算法，是因为算法自始至终一直通过已找到和末找到顶点之间的边界向外扩展，就是说，算法首先搜索和s距离为k的所有顶点，然后再去搜索和S距离为k+1的其他顶点。
BFS经典的例子就是走迷宫，我们从起点开始，找出到终点的最短路程，很多最短路径算法就是基于广度优先的思想成立的。
2.连通图
广度优先搜索是连通图的一种遍历策略，那就有必要将图先简单解释一下。
图2-1 连通图示例图
如图2-1所示，这就是我们所说的连通图，这里展示的是一个无向图，连通即每2个点都有至少一条路径相连，例如V0到V4的路径就是V0->V1->V4。
一般我们把顶点用V缩写，把边用E缩写，图用G(V,E)表示。
3.BFS算法流程图
BFS假定输入图G=(V,E)采用邻接表表示，对于图中的每个顶点还采用了几种附加的数据结构，对每个顶点u∈V，其色彩存储于变量color[u]中，结点u的父母存于变量π[u]中。如果u没有父母(例如u=s或u还没有被检索到)，则 π[u]=NIL，由算法算出的源点s和顶点u之间的距离存于变量d[u]中，算法中使用了一个先进先出队列Q来存放灰色节点集合。其中head[Q]表示队列Q的队头元素，Enqueue(Q,v)表示将元素v入队， Dequeue(Q)表示对头元素出队；Adj[u]表示图中和u相邻的节点集合。
伪代码如下：
procedure BFS(G,S);
begin
1. for 每个节点u∈V[G]-{s} do
begin
2.color[u]←White;
3. d[u]←∞;
4. π[u]←NIL;
end;
5.color[s]←Gray;
6. d[s]←0;
7. π[s]←NIL;
8. Q←{s}
9. while Q≠φdo
begin
10.u←head[Q];
11. for 每个节点v∈Adj[u] do
12. if color[v]=White then
begin
13.color[v]←Gray;
14.d[v]←d[v]+1;
15. π[v]←u;
16.Enqueue(Q,v);
end;
17.Dequeue(Q);
18.color[u]←Black;
end;
end;
BFS算法流程图
4.实例
实例搜索，要求V0到V6的一条最短路。
我们采用示例图来说明这个过程，在搜索的过程中，初始所有节点是白色（代表了所有点都还没开始搜索），把起点V0标志成灰色（表示即将辐射V0），下一步搜索的时候，我们把所有的灰色节点访问一次，然后将其变成黑色（表示已经被辐射过了），进而再将他们所能到达的节点标志成灰色（因为那些节点是下一步搜索的目标点了），但是这里有个判断，就像刚刚的例子，当访问到V1节点的时候，它的下一个节点应该是V0和V4，但是V0已经在前面被染成黑色了，所以不会将它染灰色。这样持续下去，直到目标节点V6被染灰色，说明了下一步就到终点了，没必要再搜索（染色）其他节点了，此时可以结束搜索了，整个搜索就结束了。然后根据搜索过程，反过来把最短路径找出来，图3-1中把最终路径上的节点标志成绿色。
实例应用：poj 3984 迷宫问题 https://blog.csdn.net/u012679707/article/details/79952123
// BFS.c++
//广度优先搜索
typedef struct
{
int x;
int y;
}Node;
// Vs:startpoint
// Vd:end point
int Bfs(Node&Vs,Node& Vd)
{
queue<Node> Q;
Node Vn,Vw; //Vn:当前节点； Vw:临近节点
int i;
//标记
bool visit[MAX][MAX] ; //颜色标记 ==true 说明该节点已被访问过
Node mother[MAX][MAX]; //母亲节点
int dis[MAX][MAX]; //距离
//四个方向 (x,y)
dir[][2]={ {0,1},{1,0},{0,-1},{-1,0} } ;
//初始状态将起点 加入队列
Q.push(Vs);
visit[Vs.x][Vs.y]=true;//设置该节点已被访问过
//mother[Vs.x][Vs.y]=NIL;
dis[Vs.x][Vs.y]=0; //初始距离为0
while( !Q.empty() )
{
//取出队列的头
Vn=Q.front();
Q.pop();
for(i=0;i<4;i++) //四个方向的 邻接点
{
Vw=Node(Vn.x+dir[i][0],Vn.y+dir[i][1] ) ;//计算相邻节点
if(Vw==Vd)//找到终点了
{
//把路径记录下来，需根据情况添加代码
mother[Vs.x][Vs.y]=Vn;
dis[Vw.x][Vw.y]=dis[Vn.x][Vn.y]+1;
return true;
}
if(isValid(Vw)&& !visit[Vw.x][Vw.y]) //Vw使一个合法的节点并且为白色
{
Q.push(Vw);//加入队列
visit[Vw.x][Vw.y]=true;//设置节点颜色
mother[Vs.x][Vs.y]=Vn;//父辈节点
dis[Vw.x][Vw.y]=dis[Vn.x][Vn.y]+1;
}
}
}
return false; //无解，此无通路
}