小小介绍之双端BFS

骆心恬

2026-01-09 21:37:53

发布于：上海

7阅读

0回复

0点赞

好像是叫双端BFS来着。
前置知识点：普通队列BFS

整理一下学习的双端队列。

假设这是一个需要跑BFS的图

红色是起点，绿色是终点。

如果是普通的BFS，可以使用队列作为容器，以红点为起点，承载节点去完成遍历。

Q：此过程如何加速？

A：以红点为起点，绿点为起点同时进行BFS，直到相遇。

比如：

红色数字表示由红点出发的遍历（由于BFS是一层一层进行遍历的，所以第一层表示为1，第二层表示为2），绿色数字表示由绿点出发的遍历。

直到红，绿数字相遇。那么本次遍历完成。花费（时间）：红点花费+绿点花费。

注意：由于BFS的特点，（一般）取第一次。

这就是双端BFS的大体思路。

然后再提一提代码框架。
首先，有一个
while(!q1.empty()&&！q2.empty())
的循环。（因为要分别以红，绿点为起点；所以需要两个队列）

然后每一次循环，去判断红点队列中的点多还是绿点队列中的点多。优先选择点数小的那一个进行BFS。

原因：有一点贪心的感觉，另外极端例图打破一切偏见：

在本图中，如果你优先取遍历红色顶点，你可能要遍历n+1个点。

但如果你选择先遍历绿色顶点，你只需要遍历 $1+\frac{n}{2}$ 个顶点即可。

大体上似乎就是这样，然后请看例题：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;
}