广度宽度优先搜索(BFS).docx

广度/宽度优先搜索（BFS）
【算法入门】
1■刖言
广度优先搜索（也称宽度优先搜索，缩写BFS,以下采用广度来描述）是连通图的一种遍 历策略。因为它的思想是从一个顶点V0开始，辐射状地优先遍历其周围较广的区域，故得 名。
一般可以数组：
0, 1,0, 0, 0,
0, 1,0, 1,0,
0, 0, 0, 0, 0,
0, 1, 1, 1,0,
0, 0, 0, 1,0,
我们把节点定义为（x,y）, （x,y）表示数组maze的项maze[x][y]。
于是起点就是（0,0）,终点是（4,4）。按照刚刚的思路，我们大概手工梳理一遍： 初始条件：
起点VS为（0,0）
终点Vd为（4,4）
灰色节点集合Q={}
初始化所有节点为白色节点
开始我们的广度搜索！
手工执行步骤【PS:你可以直接看图41】：
1•起始节点VS变成灰色，加入队列Q, Q={（0,0）}
取出队列Q的头一个节点vn, vn={0,0}, Q={}
把vn={0,0}染成黑色，取出vn所有相邻的白色节点{(1,0)}
不包含终点(4,4),染成灰色，加入队列Q, Q={(1,0)}
取出队列Q的头一个节点vn, vn={1,0}, Q={}
把Vn={1,0}染成黑色，取出Vn所有相邻的白色节点{(2,0)}
不包含终点(4,4),染成灰色，加入队列Q, Q={(2,0)}
取出队列Q的头一个节点Vn, Vn={2,0}, Q={}
把Vn={2,0}染成黑色，取出Vn所有相邻的白色节点{(2,1), (3,0)}
不包含终点(4,4),染成灰色，加入队列Q, Q={(2,1), (3,0)}
取出队列Q的头一个节点Vn, Vn={2,1}, Q={(3,0)}
把Vn={2,1}染成黑色，取出Vn所有相邻的白色节点{(2,2)}
不包含终点(4,4),染成灰色，加入队列Q, Q={(3,0), (2,2)}
持续下去，知道Vn的所有相邻的白色节点中包含了(4,4)……
此时获得了答案
起始你很容易模仿上边过程走到终点，那为什么它就是最短的呢?
怎么保证呢？
我们来看看广度搜索的过程中节点的顺序情况：
^O)
图4-1迷宫问题的搜索树
你是否观察到了，广度搜索的顺序是什么样子的？
图中标号即为我们搜索过程中的顺序，我们观察到，这个搜索顺序是按照上图的层次关系来 的，例如节点（0,0 ）在第1层，节点（1,0）在第2层，节点（2,0 ）在第3层，节点（2,1）和节 点（3,0 ）在第3层。
我们的搜索顺序就是第一层-〉第二层-〉第三层-〉第N层这样子。
我们假设终点在第N层，因此我们搜索到的路径长度肯定是N，而且这个N —定是所求最短 的。
我们用简单的反证法来证明：假设终点在第N层上边出现过，例如第M层，M<N,那么我们
在搜索的过程中，肯定是先搜索到第M层的，此时搜索到第M层的时候发现终点出现过了, 那么最短路径应该是M,而不是N 了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
所以根据广度优先搜索的话，搜索到终点时，该路径一定是最短的。
43代码
我给出以下代码用于解决上述题目（仅仅只是核心代码）:
/**
*广度优先搜索
***@param Vs 起点
***@param Vd 终点
*/
bool BFS(Node& Vs, Node& Vd){
queue<Node> Q;
Node Vn, Vw;
int i;
//用于标记颜色当visit[i][j]==true时，说明节点访问过，也就是黑色 bool visit[MAXL][MAXL];
//四个方向
int dir[][2] = {
{0, 1}, {1, 0},
{0, -1}, {-1, 0}
};
//初始状态将起点放进队列Q
(Vs);
visi t[][] = true;//设置节点已经访问过了！
while (! ty()){//队列不为空，继续搜索！
//取出队列的头Vn
Vn = ();
();
for(i = 0; i < 4; ++i){
Vw = Node(+dir[i][0], +dir[i][1])//计算相邻节点
if (Vw == Vd){//找到终点了！
〃把路径记录，这里没给出解法
return true