[数据结构与算法]双端队列BFS——通俗易懂

问题：给一个带权图，让你求从一点到另一点的最短路径。

肯定会想到用Dijkstra，但这个带权图比较特殊，权值只有0和1。那么就可以用双端队列BFS啦。

不同点：双端队列BFS和普通BFS区别，从字面也可以理解，差别在队列上。

双端队列是啥？

容器deque和vector非常相似，属于序列式容器。都是采用动态数组来管理元素，提供随机存取，并且有着和vector一样的接口。不同的是deque具有首尾两端进行快速插入、删除的能力。通俗来讲就是队列首尾都可以入队。

双端队列怎么用？

STL函数

deque<数据类型> a；//创建

a.empty() 判断容器是否为空

a.push_back(elem) 在尾部加入一个数据

a.push_front(elem) 在头部插入一个数据

c.pop_front() 删除头部数据

当然STL中还有很多函数，不够这些足以解决此类问题。

怎么用双端队列去BFS？

很简单，权值为0，插队首，权值为1，插队尾。其他和普通BFS一样。

为什么这么用呢？

因为我们要求的是最短路径，BFS广搜下本来就是最短的访问顺序。但现在加了权值，权值为1插队尾，和普通BFS一样，不用过多纠结。主要是权值为0插入队首，这不是会改变后面结点的出队顺序吗，其实不用担心，因为权值为0，所以不论访问顺序如何，最终之和还是0。故这样就保证了出队的结点一定是当前最短路径，因为它是尽可能多的权为0的边更新过来的。

实战一下！

双端队列BFS经典题目便是电路连接那个题，但其实那道题对新手不太友好。

直到遇到她——拖拉机https://www.acwing.com/problem/content/2021/

解题思路：没有干草堆可以看成权值为0的点，有干草堆可以看成权值为1的点。于是，它就变成一道板子题啦。

具体代码：

#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<cmath>
#include<queue>
#include<stack>
#include<deque>
#include<cstring>

using namespace std;
#define ll long long
const int maxn = 1000 + 50;
const int inf = 1e9 + 7;
int a[maxn][maxn];//存图形矩阵
int dis[maxn][maxn];//记录源点到该点的最短距离
int sx, sy;
int mov[4][2] = {{1,  0},{-1, 0},{0,  1},{0,  -1}};//移动数组
struct node {
    int nx, ny;
};
int vis[maxn][maxn];//标记是否走过
void bfs(int x, int y) {
    deque<node> q;
    q.push_front({x,y});
    while (!q.empty()) {
        node w = q.front();//返回队首
        q.pop_front();//弹出队首
        for (int i = 0; i < 4; i++) {
            int nowx = w.nx + mov[i][0], nowy = w.ny + mov[i][1];
            if (nowx >= 0 && nowx <= 1001 && nowy >= 0 && nowy <= 1001 && !vis[nowx][nowy]) {
                if (!a[nowx][nowy]) {
                    q.push_front({nowx,nowy});
                    dis[nowx][nowy] = dis[w.nx][w.ny];
                }//边权为0入队首
                else {
                    if (dis[nowx][nowy] > dis[w.nx][w.ny] +1) {
                        dis[nowx][nowy] = dis[w.nx][w.ny] +1;
                        q.push_back({nowx,nowy});
                    }
                }
                //cout<<nowx<<' '<<nowy<<' '<<dis[nowx][nowy]<<endl;
                vis[nowx][nowy]=1;
                if(nowx==1&&nowy==1) return ;
            }
        }
    }
}

int main() {
    int t;
    cin >> t;
    cin >> sx >> sy;
    while (t--) {
        int x, y;
        cin >> x >> y;
        a[x][y] = 1;//将草堆标记为1
    }
    vis[sx][sy] = 1;//标记源点
    memset(dis,0x7f,sizeof(dis));
    dis[sx][sy] = 0;
    bfs(sx, sy);
    cout << dis[1][1];
    return 0;
}