深度优先搜索一般是递归实现的,搜索过程中总是优先遍历当前节点的子节点。从这一节开始,我们将学习广(宽)度优先搜索
这个GIF图中,节点被染成绿色的顺序表示在宽度优先搜索过程中节点被访问的顺序。可以看到从根节点开始访问,每当一层的节点都被访问过后,下一层的节点才会开始被访问。接下来我们对整个过程进行更详细的分解:
在上面的过程中我们发现以下两个事实:
在访问的过程中,由于我们访问一个节点之后,会记录它的子节点。当该层的节点全部完成访问后,才会根据记录依次访问下一层节点。这样也导致同一层节点会集中在记录序列中的一个连续区间内 根据上面所描述的过程我们可以得到广度优先搜索的流程:
看下面一段代码段
int que[MAXN];//用于记录的队列,这里用数组来模拟
bool inq[MAXN];//记录一个节点是否在队列中
int head = 0,tail = 0;//当前队列的头尾指针
que[tail++] = root;//根节点入队
inq[root] = true;
while(head < tail)//若队列内仍有元素
{
int u = que[head++];//取出队首元素
visit(u);//访问该节点
for(int j : g[u])//枚举所有u的子节点
{
if(!inq[j])//如果j不在队列中
{
que[tail++] = j;//将子节点加入队列中
inq[j] = true;
}
}
}
在这段代码中,我们定义了两个数组,分别是记录节点的que数组和一个布尔类型的数组inq。 que数组和变量head、tail用来模拟队列的数据结构,当然你也可以直接使用C++STL中的queue容器。 inq的目的是为了记录哪些节点已经在队列中了,防止重复的将某些节点加入队列中而产生的错误 初始化时,我们将搜索的起始节点加入队列,同时标记它已经被加入队列中。如果还有其他需要初始化的内容,也需要在这里执行。 接下来是while循环,在满足队列不为空的情况下,反复从队列中取出头元素进行访问。访问这个过程具体要做哪些工作是由题目要求决定的。同时在访问一个节点完成后,需要将其子节点也加入到队列之中。当所有的节点均被访问之后,即队列为空时,则会自动跳出该循环 以上就是宽度优先搜索实现的一个基本框架。下图演示了在一张图上BFS的过程:
蓝色方格代表队列,左边一段是已经移出队列的节点,右边是当前队列,红色箭头是首尾指针。白色节点代表还没访问到的节点,灰色节点是在队列中的节点,黑色节点是已经被移出队列的节点 广度优先搜索保证了每个节点只会进入队列一次,离开队列一次。因此假设节点数量为n,边数为m时,广度优先搜索的基础时间复杂度为O(n+m)。但和深度优先相比,由于需要利用que数组记录访问的节点,所以会有额外O(n)的空间开销 在广度优先搜索的过程中,如果节点之间的边的长度都为1,那么当一个节点被访问时所记录的路径长度一定是根到它的最短路径。这是利用广度优先搜索中最重要的性质 举个例子:
在该例子中,初始节点为1,我们想要知道到达3的最短路径。若我们利用深度优先搜索,则第一次访问到3时,路径可能为1->2->3,不是1到3的最短路径。而利用宽度优先搜索,第一次扩展时就能够直接找到1->3的最短路径,不需要花费额外的时间去访问1->2->3的路径 利用这个性质我们就可以完成一些单源点查询最短路径的问题。下面我们就看一道这样的问题:
该题目就是一道典型的利用宽度优先搜索,查询最短路径的问题。根据题目描述,我们可以知道以下几个信息:
根据上面的信息,我们需要使用到下面这些数据结构:
int que[MAXN*MAXN][2];//第二维度为2,因为要记录x,y两个坐标值
int steps[MAXN][MAXN];//记录到达[x,y]的步数
bool inq[MAXN][MAXN];//记录[x,y]是否被访问过
BFS的代码如下:
//方向数组,分别表示上下左右四个方向移动时,坐标的增量
const int dr[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
int head = 0,tail = 0;
que[tail][0] = 1;
que[tail][1] = 1;
steps[1][1] = 0;
inq[1][1] = true;
tail++;
while(head > tail)
{
int x = que[head][0];
int y = que[head][1];
head++;
for(int d = 0;d < 4;d++)
{
int nx = x + dr[d][0];
int ny = y + dr[d][1];
//保证[nx,ny]在地图内
if(inMap[nx][ny] && !inq[nx][ny] &&
map[nx][ny] != '#')
steps[nx][ny] = steps[x][y] + 1;
inq[nx][ny] = true;
que[tail][0] = nx;
que[tail][1] = ny;
tail++;
}
}
程序一开始的dr[]数组起到的作用与之前讲过的DFS中的dx[]和dy[]一样,用于表示上下左右4个方向 在该问题中,我们同样先将初始节点加入队列,再在队列不为空的情况下反复进行节点的扩展,最后完成搜索。由于题目中的`地图是有限制的矩形区域,因此我们需要额外的inMap函数进行位置的辅助判定 同时还需要检查移动到的节点是否为墙壁,当整个搜索完成后,stepsx中记录的是从[1,1]到达[x,y]的最少步数,因此stepsn也就是问题的答案