广度优先搜索

入门

首先让我们回忆一下,深度优先搜索是个什么东西.

​

上面这张图想必大家都不陌生,这张图虽然简单,但是说明了DFS和BFS的本质区别:按什么方式遍历一个图(为了方便叙述,上图实际是一棵树),DFS按深度优先的方式,BFS则是层序遍历,下面让我们看一个具体例子:

问题

DFS解法

若采用DFS,规定移动方向为顺时针方向右 -> 下 -> 左 -> 上,则搜索最短路径的情况为:

为了方便区分,DFS每次回溯时路径用不同的颜色标识,在所有可能的情况尝试过后,我们发现,一共有3条路可以到达终点,路径长度分别是5,9和11,因此我们断定,[0,0]到[2,3]的最短路径为5.

BFS解法

如上图,我们把同一层的点用相同颜色的三角形做一个标记(设起点为第0层),对应关系如下表:

颜色	层数
蓝色	1
浅绿	2
橙色	3
灰色	4
深绿	5

则由上图不难看出,处在同一层的点,起点到该点的路径长度是一样的.而终点在第5层上,即最短路径为5.细心的同学可能会注意到,图中还有三个点未遍历到,为什么不必遍历呢? 这显然是因为,已经有一层到达了终点,再往下遍历下一层的点,即使到达终点也必然不是最短路,因此我们可以在某一层达到终点时,就退出循环,认定此时已经找到一条最短路径.

实现

通过刚才的例子,我们显然发现了BFS的一大长处: 寻找一条最短路! DFS需要把所有可达和不可达的路径全部遍历一遍从而能找到一条最短路径,而BFS只需到达终点即是最短路径.可以预测,在绝大部分的图上,寻找最短路BFS要比DFS更有优势,那么如何实现呢?

队列显然是个好办法!

为什么?

考虑一下队列的特点——先进先出!

?? What？

初始化一个空队列

将起点入队,遍历队首下一层所有的可达顶点

在遍历的过程中，找到一个点就把它存入队列

遍历队首下一层结束后别忘了将队首出队

对于新的队首,重复上述操作

到达终点或队列为空时,结束

因为队列有先进先出的特点,因此当当前一层遍历结束时,下一个处于队首的元素必然属于下一层,这样就能保证BFS的层序遍历次序.

队列那些事

那么,队列怎么实现?
如果你非要自己实现队列的话

ACM比赛的话,建议使用轮子——STL之queue容器

说一点在本文用得上的操作:

queue<int> q;
while(!q.empty()) {    //清空队列;
	q.pop
}

queue<typename> q;	
q.front();    //取队首元素;
q.back();    //取队尾元素;
q.push((typename)a);	//将a入队;
q.pop();	//将队首出队;

稍微写个queue的使用标程:

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n,t;
    queue<int> q;
    while(cin>>n) {
        while(n--) {
            cin>>t;
            q.push(t);
        }
        while(!q.empty()) {
            cout<<q.front()<<" ";
            q.pop();
        }
        cout<<endl;
    }
    return 0;
}

上个问题的解(BFS)

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int nxt[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};   //位移数组;
struct node {
    int x,y,step;
    node(int x,int y,int step):
        x(x),y(y),step(step){};
};

int main() {
    int n,m,tx,ty,Min = inf;
    queue<node> q;
    bool vis[10][10],flag = 0;
    char e[10][10];
    cin>>n>>m;
    memset(vis,0,sizeof vis);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin>>e[i][j];
    q.push(node(0,0,0));    //起点入队;
    vis[0][0] = 1;
    while(!q.empty()) {
        node tmp = q.front();
//   cout<<tmp.x<<" "<<tmp.y<<endl;
        q.pop();
        for(int i = 0; i < 4; i++) {
            node t(tmp.x+nxt[i][0],tmp.y+nxt[i][1],tmp.step+1);
            if(t.x < 0 || t.x > n || t.y < 0 || t.y > m || e[t.x][t.y] == '#')    //越界或障碍;
                continue;
            if(!vis[t.x][t.y]) {    //下一层且未走过的点入队;
                vis[t.x][t.y] = 1;
                q.push(t);
            }
            if(t.x == 2 && t.y == 3) {  //到达终点;
                Min = t.step;
                flag = 1;
                break;
            }
        }
        if(flag)    break;
    }
    cout<<Min<<endl;
    return 0;
}

更高要求

假设需要输出这条最短路径,用BFS如何实现呢?

我们知道,在DFS中,一条路径无论通不通,当搜索到头(到达终点/无法前进时),它必然是本次搜索的一条完整路径,我们可以每次都保存路径,当路径最小值更新时,将上次搜索的最小路径覆盖为当前保存的路径即可.但是在BFS中可没有这么简单,因为我们搜索的过程中会将一层又一层的点存入队列,因此无法保证顺序遍历队列就一定是完整的路径,它可能是多条路径的混合(一般都是),那么我们如何从这些混合路径中选取最短路呢?

这个过程也很简单,仔细想想分为以下两步:

第一步: 保存队列状态

因为队列是动态变化的,会丢失信息.

我们要在每一个点入队时保存这个点

理想的情况就是拿一个数组把整个队列复制下来

具体表现为,当有点可以入队时,同时将其往数组存一份

第二步: 从数组中选择最短路

当达到终点时,必然存在最短路,此时数组中的最后一个点必然是终点.

问题是如何在数组中找一条从终点到起点的最短路径(这条路径必然在数组中,且大概率不连续)

对于每一个点,我们要是知道它是从哪里扩展来的就好办了

这就是说,我们应该在当前点存一下它前一个点的存储位置(数组下标)

通过一个点扩展时,知道其上一个点是什么很容易,但获取上一个点的存储位置,不见得容易

我们可以在当前点存一下自身的存储位置,这样下一个点找到当前点就一并找到其存储位置

当达到终点时,通过当前点,不断向前迭代,直到找到起点即路径结束

建议用一个最短路数组保存,从后往前存最短路,再从前往后输出就是正确的顺序

实现输出最短路

如前文所说,输出最短路需要记录当前点和上一点的存储位置,因此修改节点结构如下:

struct node {
    int x,y,step,pre,pos;       //pos:当前存储位置,pre:上一点存储位置;
    node(){};
    node(int x,int y,int step):
        x(x),y(y),step(step){};
};

完整实现如下:

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
int nxt[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};   //位移数组;
struct node {
    int x,y,step,pre,pos;       //pos:当前存储位置,pre:上一点存储位置;
    node(){};
    node(int x,int y,int step):
        x(x),y(y),step(step){};
};

int main() {
    int n,m,tx,ty,Min = inf,cnt = 0;
    queue<node> q;
    node temp[25],path[25];
    bool vis[10][10],flag = 0;
    char e[10][10];
    cin>>n>>m;
    memset(vis,0,sizeof vis);
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin>>e[i][j];
    node st(0,0,0);
    st.pre = st.pos = 0;
    q.push(st);    //起点入队;
    temp[cnt] = path[cnt] = st;
    vis[0][0] = 1;
    while(!q.empty()) {
        node tmp = q.front();
        q.pop();
        for(int i = 0; i < 4; i++) {
            node t(tmp.x+nxt[i][0],tmp.y+nxt[i][1],tmp.step+1);
            if(t.x < 0 || t.x >= n || t.y < 0 || t.y >= m || e[t.x][t.y] == '#')    //越界或障碍;
                continue;
            if(!vis[t.x][t.y]) {    //下一层且未走过的点入队;
                vis[t.x][t.y] = 1;
                t.pos = ++cnt;          //当前存储位置;
                t.pre = tmp.pos;        //上层节点存储位置;
                temp[cnt] = t;          //存入备份数组;
                q.push(t);
            }
            if(t.x == 2 && t.y == 3) {  //到达终点;
                Min = t.step;
                for(int i = Min,j = cnt; i > 0; i--) {      //根据节点前驱pre和位置pos,寻找并存储最短路径;
                    path[i] = temp[j];
                    j = temp[j].pre;
                }
                flag = 1;
                break;
            }
        }
        if(flag)    break;
    }
    cout<<Min<<endl;
    for(int i = 0; i <= Min; i++)       //包括起点,最短路长度为Min+1;
        cout<<path[i].x<<" "<<path[i].y<<endl;
    return 0;
}

又一个例题

这个题目乍一看好像跟BFS没什么关系.

等等,这不是DFS的题目吗?

——找到一个水池就深度优先搜索啊，直到无法继续进行下去，计数+1就好了啊！

对的,递归大法好,DFS可以轻松解决此类问题,但是BFS不能做吗?

我们仔细想一想,其实BFS和DFS的本质区别,就在于搜索的侧重点不一样而已,深度优先和广度优先,搜索一块水池,不都是要完全遍历吗?而DFS和BFS,正是图论中图的两种遍历方式,因此,用同样的思路,将DFS代码改写为BFS即可,并且BFS有一个得天独厚的优势——vis数组不需要撤销标记,对应的就是这里的,统计过的水池不能再计算一遍的规律,因此用BFS应该是更好的解题策略才是.

我们来想一想,时间复杂度的问题,在这类题目下,BFS和DFS的时间复杂度是一样的!不存在BFS省时的说法因为我们最终都是要将一个水池能扩展的方向全部遍历完,不管是深度优先还是广度优先,实际上遍历的范围是一样的,因此两个算法一样耗时…吗?理论上说是的,实际上BFS不需要递归的时间开销,还是要稍微快那么一点点的,不过呢…忽略不计,忽略不计啦

代码很简单,直接给出了:

#include<iostream>
#include<cstring>
#include<queue>
#define inf 0x3f3f3f3f;
using namespace std;

typedef pair<int,int> pii;
int n,m,nxt[8][2] = {{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};
char e[105][105];
bool vis[105][105];

void bfs(pii st) {
    queue<pii> q;
    q.push(st);
    vis[st.first][st.second] = 1;
    while(!q.empty()) {
        pii tmp = q.front();
        q.pop();
        for(int i = 0; i < 8; i++) {
            pii t = make_pair(tmp.first+nxt[i][0],tmp.second+nxt[i][1]);
            if(t.first < 0 || t.first >= n || t.second < 0 || t.second >= m || vis[t.first][t.second])
                continue;
            if(e[t.first][t.second] == 'W') {
                q.push(t);
                vis[t.first][t.second] = 1;
            }
        }
    }
}

int main() {
    while(cin>>n>>m) {
        if(n == 0 && m == 0)    break;
        int cnt = 0;
        memset(vis,0,sizeof vis);
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                cin>>e[i][j];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                if(e[i][j] == 'W' && !vis[i][j]) {
//                    cout<<i<<" "<<j<<endl;
                    bfs(make_pair(i,j));
                    cnt++;
                }
        cout<<cnt<<endl;
    }
    return 0;
}

总结

我们可以总结一下,DFS和BFS的异同:

搜索方式	使用数据结构	递归?	vis数组标记
DFS	栈	是	需要撤销标记
BFS	队列	否	无需撤销标记

• DFS使用递归,调用系统堆栈,时间开销大于BFS
• DFS一个点可能包含在多条路径中,递归回溯时需要撤销vis标记
• BFS一个点只入队一次,因此无需撤销vis标记
• BFS不要忘了队首使用完之后出队
• BFS和DFS常用于优化很多算法,如Dijkstra的DFS优化,BFS实现二分图匹配的匈牙利算法等

---

总之,深入理解并熟练应用DFS和BFS,将是之后学习图论的坚实基础和理论前提
在踏入图论的大门(深渊)之前,不会这两个搜索算法可不行哦~