小小介绍之双端BFS
2026-01-09 21:37:53
发布于:上海
好像是叫双端BFS来着。
前置知识点:普通队列BFS
整理一下学习的双端队列。
假设这是一个需要跑BFS的图
!

红色是起点,绿色是终点。
如果是普通的BFS,可以使用队列作为容器,以红点为起点,承载节点去完成遍历。
Q:此过程如何加速?
A:以红点为起点,绿点为起点同时进行BFS,直到相遇。
比如:

红色数字表示由红点出发的遍历(由于BFS是一层一层进行遍历的,所以第一层表示为1,第二层表示为2),绿色数字表示由绿点出发的遍历。
直到红,绿数字相遇。那么本次遍历完成。花费(时间):红点花费+绿点花费。
注意:由于BFS的特点,(一般)取第一次。
这就是双端BFS的大体思路。
然后再提一提代码框架。
首先,有一个
while(!q1.empty()&&!q2.empty())
的循环。(因为要分别以红,绿点为起点;所以需要两个队列)
然后每一次循环,去判断红点队列中的点多还是绿点队列中的点多。优先选择点数小的那一个进行BFS。
原因:有一点贪心的感觉,另外极端例图打破一切偏见:

在本图中,如果你优先取遍历红色顶点,你可能要遍历n+1个点。
但如果你选择先遍历绿色顶点,你只需要遍历个顶点即可。
大体上似乎就是这样,然后请看例题:P1746离开中山路
代码:
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
char a[N][N];
int vis1[N][N];
int vis2[N][N];
struct Node{
int x,y;
};
queue<Node>q1;
queue<Node>q2;
int n;
int sx,sy,ex,ey;
int xx[4]={1,0,-1,0};
int yy[4]={0,1,0,-1};
int bfs(queue<Node>&q,int visa[N][N],int visb[N][N]){
while(!q.empty()){
Node sum=q.front();
q.pop();
for(int i=0;i<4;i++){
int xx1=xx[i]+sum.x;
int yy1=yy[i]+sum.y;
if(xx1>=1&&xx1<=n&&yy1>=1&&yy1<=n&&a[xx1][yy1]=='0'&&!visa[xx1][yy1]){
visa[xx1][yy1]=visa[sum.x][sum.y]+1;
if(visb[xx1][yy1]!=0){
return visa[xx1][yy1]+visb[xx1][yy1]-2;
}
Node sum1={xx1,yy1};
q.push(sum1);
}
}
}
}
void bi_bfs(){
Node sum1={sx,sy};
q1.push(sum1);
vis1[sx][sy]=1;
Node sum2={ex,ey};
q2.push(sum2);
vis2[ex][ey]=1;
if(sx==ex&&sy==ey){
cout<<0;
return;
}
while(!q1.empty()&&!q2.empty()){
int sum1=-1;
if(q1.size()<=q2.size())sum1=bfs(q1,vis1,vis2);
else sum1=bfs(q2,vis2,vis1);
if(sum1!=-1){
cout<<sum1;
return;
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
}
}
cin>>sx>>sy>>ex>>ey;
bi_bfs();
return 0;
}
全部评论 1
双端BFS为什么只求图这个玩意不是搜状态用的吗
6天前 来自 广东
0哦,因为这里只是说了一下(我所知)的一个模板。
谢谢建议。
我再去学一下之后再出一篇好了,然后把两个都详细说一下。5天前 来自 上海
1
















有帮助,赞一个