0-1 BFS：双端队列与二值边权最短路

一、算法起源：从 Dijkstra 到 01BFS 的蜕变

在解决单源最短路问题时，最通用的算法是 Dijkstra。它的核心思想是利用优先队列（堆），每次提取全局距离最小的点去松弛其相邻节点，时间复杂度为 $O((V+E)\log V)$ 。

现在，我们考虑一种特殊的图：图中所有的边权只有 $0$ 和 $1$ 两种。

想象一下在这种图上运行 Dijkstra 的场景：假设当前从优先队列中弹出的节点，其最短距离为 $d$ 。那么它松弛出的相邻节点，距离只有两种可能：

走边权为 $0$ 的边，新距离依然是 $d$ 。
走边权为 $1$ 的边，新距离变为 $d+1$ 。

这意味着，在整个算法运行的任意时刻，优先队列内部最多只同时存在两种距离值（一批 $d$ 和一批 $d+1$ ）。面对如此简单的层级结构，维护一个 $O(\log V)$ 的二叉堆显得极其多余。

因此，我们可以废弃优先队列，使用一个双端队列 (std::deque) 来完美替代它的功能：

$0$ 权边插队：新距离仍为 $d$ ，具有最高优先级，直接推入队首 (push_front)。
$1$ 权边排队：新距离变为 $d+1$ ，优先级次之，推入队尾 (push_back)。

通过这种“ $0$ 前 $1$ 后”的入队策略，双端队列自始至终维持着“队首到队尾距离单调递增”的性质，精准复刻了 Dijkstra 贪心提取最小值的逻辑，并成功将时间复杂度降维打击至严格的 $O(V+E)$ 。这就是 01BFS 的底层逻辑。

01BFS：Dijkstra、BFS 与双端队列的关系

二、核心模板与思维误区剖析

由于 01BFS 本质上是 Dijkstra 的变体，它的代码结构必须遵循最短路算法的“松弛”原则。初学者常会沿用普通 BFS “入队即打 vis 标记”的习惯，这在 01BFS 中是致命的错误。

1. 传统 BFS 思维陷阱剖析

初学者常写出类似如下带有隐患的代码：

// 存在隐患的传统写法
struct node { int x, y, len; };

void bfs(){
	deque<node>q;
	q.push_front({x1,y1,0});
	while(!q.empty()){
		node now=q.front();
		q.pop_front();
		int x=now.x,y=now.y,len=now.len;
		
		// 误区 1：在终点处比较所有到达路径的最小值
		if(x==x2&&y==y2) ans=min(ans,len); 
		
		for(int i=0;i<4;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(can(nx,ny)){ // 这里假设 can 同时检查边界和 !vis[nx][ny]
				// 误区 2：一旦入队，立刻打上 vis=1 标记阻挡后续访问
				if(a[x][y]==a[nx][ny]) q.push_front({nx,ny,len}),vis[nx][ny]=1;
				if(a[x][y]!=a[nx][ny]) q.push_back({nx,ny,len+1}),vis[nx][ny]=1;
			}
		}
	}
}

传统写法失效的原因分析：

传统 BFS 能够“入队即标记”的前提是边权恒定为 $1$ ，搜索如同水波一样均匀向外扩散。但在 01BFS 中，边权的差异打破了这一规律：

“劣币驱逐良币”效应：假设节点 $A$ 通过一条代价为 $1$ 的路径被发现，并被 push_back 到了队尾。若在入队瞬间就给 $A$ 打上 vis=1，那么后续如果有一条代价为 $0$ 的更优路径（通过 push_front 插队）蔓延到 $A$ 时，就会被 vis 直接拦截。最终到达 $A$ 的距离并非最短路。
失去提前退出的极值优势：在 ans = min(ans, len) 的写法中，程序被迫跑完队列里的所有状态。而 01BFS 严格保证了队首提取的必然是当前的全局最小距离，第一次从队首弹出终点时，直接 return 即可，大幅降低耗时。

2. 标准规范模板（基于 `dis` 数组的松弛操作）

核心法则：废弃传统的 vis 数组，引入 dis 全局数组记录最短距离。只有当发现严格更短的路径时，才允许更新 dis 并入队。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=505;

int n,m,sx,sy,ex,ey;
char a[N][N];
int dis[N][N];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};

void bfs(){
	// 1. 多测清空：全局 dis 数组必须初始化为极大值
	memset(dis,0x3f,sizeof(dis)); // long long 下约 4.5e18，作为无穷大够用
	deque<pair<int,int>> q;
	
	q.push_front({sx,sy});
	dis[sx][sy]=0;

	while(!q.empty()){
		int x=q.front().first;
		int y=q.front().second;
		q.pop_front();

		// 2. 找到终点直接退出：队首出队必定是最短路
		if(x==ex&&y==ey) return; 

		for(int i=0;i<4;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
				// 3. 计算当前转移的边权 w (0 或 1)
				int w=(a[x][y]==a[nx][ny]?0:1);
				
				// 4. Dijkstra式松弛：只有距离变小，才更新入队
				if(dis[nx][ny]>dis[x][y]+w){
					dis[nx][ny]=dis[x][y]+w;
					if(w==0) q.push_front({nx,ny});
					else q.push_back({nx,ny});
				}
			}
		}
	}
}

void solve(){
	// 读入逻辑...
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

三、典型实战题型解析

课上重点讲例 1、4、6；例 2、3、5 留作课后练习。

1. 题型一：基础网格状态转移

例 1：P4554 小明的游戏

思路：走到相同字符花费为 $0$ ，不同字符花费为 $1$ 。完全契合标准的 01BFS 模型。注意题目是多组数据，每次需重新初始化 dis 数组。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=505;

int n,m,sx,sy,ex,ey;
char a[N][N];
int dis[N][N];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};

void bfs(){
	memset(dis,0x3f,sizeof(dis));
	deque<pair<int,int>> q;
	q.push_front({sx,sy});
	dis[sx][sy]=0;
	
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;
		q.pop_front();
		if(x==ex&&y==ey) return;
		
		for(int i=0;i<4;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
				int w=(a[x][y]==a[nx][ny]?0:1);
				if(dis[nx][ny]>dis[x][y]+w){
					dis[nx][ny]=dis[x][y]+w;
					if(w==0) q.push_front({nx,ny});
					else q.push_back({nx,ny});
				}
			}
		}
	}
}

void solve(){
	while(cin>>n>>m&&(n||m)){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				cin>>a[i][j];
			}
		}
		cin>>sx>>sy>>ex>>ey;
		// 题目下标从 0 开始，全部加 1 转为 1-based
		sx++,sy++,ex++,ey++;
		bfs();
		cout<<dis[ex][ey]<<'\n';
	}
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

例 2：UVA11573 Ocean Currents

思路：将 $4$ 个方向扩展为 $8$ 个方向。网格中的数字代表水流方向，顺水流移动代价为 $0$ （由于有洋流提供动力，无需耗能），向其他方向移动代价为 $1$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;

int n,m,k,sx,sy,ex,ey;
char a[N][N];
int dis[N][N];
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};

void bfs(){
	memset(dis,0x3f,sizeof(dis));
	deque<pair<int,int>> q;
	q.push_front({sx,sy});
	dis[sx][sy]=0;
	
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;
		q.pop_front();
		if(x==ex&&y==ey) return;
		
		for(int i=0;i<8;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
				int w=((a[x][y]-'0')==i?0:1);
				if(dis[nx][ny]>dis[x][y]+w){
					dis[nx][ny]=dis[x][y]+w;
					if(w==0) q.push_front({nx,ny});
					else q.push_back({nx,ny});
				}
			}
		}
	}
}

void solve(){
	if(!(cin>>n>>m)) return;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) cin>>a[i][j];
	}
	cin>>k;
	while(k--){
		cin>>sx>>sy>>ex>>ey;
		bfs();
		cout<<dis[ex][ey]<<'\n';
	}
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

2. 题型二：状态空间的升维

例 3：CF173B Chamber of Secrets

思路：光线在迷宫中穿梭，能否到达下一个位置不仅与“当前坐标”有关，还与“当前朝向”有关。继续沿原方向直行，由于不需要对柱子施法，花费为 $0$ ；遇到 # 时，可花费 $1$ 次施法机会改变至其他三个朝向。因此，状态定义必须升维，由 dis[x][y] 变为 dis[x][y][dir]。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;

int n,m;
char a[N][N];
int dis[N][N][4];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0}; // 右, 左, 下, 上

struct node{
	int x,y,dir;
};

void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) cin>>a[i][j];
	}
	memset(dis,0x3f,sizeof(dis));
	deque<node> q;
	
	// 从 (n, m) 出发，初始面朝左 (方向1) 射出光线
	q.push_front({n,m,1});
	dis[n][m][1]=0;
	
	while(!q.empty()){
		node u=q.front();
		q.pop_front();
		
		if(u.x==1&&u.y==1&&u.dir==1){ // 门在左上格左侧，必须朝左射出
			cout<<dis[1][1][u.dir]<<'\n';
			return;
		}
		
		// 1. 直行 (不需要施法，代价0)
		int nx=u.x+dx[u.dir],ny=u.y+dy[u.dir];
		if(nx>=1&&nx<=n&&ny>=1&&ny<=m){
			if(dis[nx][ny][u.dir]>dis[u.x][u.y][u.dir]){
				dis[nx][ny][u.dir]=dis[u.x][u.y][u.dir];
				q.push_front({nx,ny,u.dir});
			}
		}
		
		// 2. 遇柱子转向 (施加魔咒，代价1)
		if(a[u.x][u.y]=='#'){
			for(int i=0;i<4;i++){
				if(i==u.dir) continue; // 原方向已处理
				if(dis[u.x][u.y][i]>dis[u.x][u.y][u.dir]+1){
					dis[u.x][u.y][i]=dis[u.x][u.y][u.dir]+1;
					q.push_back({u.x,u.y,i});
				}
			}
		}
	}
	cout<<"-1\n";
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

3. 题型三：网格图转格点图建模

例 4：P4667 [BalticOI 2011] Switch the Lamp On

思路：题目给出的电路板是 $N \times M$ 个格子，但电源和电线实际上连接的是格子的顶点。因此，我们需要在一张 $(N+1) \times (M+1)$ 个顶点的图上跑 BFS。

每次从当前顶点向四个对角的顶点移动，判断这期间穿过的网格字符。若电线方向匹配，代价为 $0$ ；若需要旋转电路元件，代价为 $1$ 。此题可利用横纵坐标之和的奇偶性快速判断是否无解。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=505;

int n,m;
char a[N][N];
int dis[N][N];
// 从当前格点走向四个对角格点：左上, 右上, 左下, 右下
int dx[4]={-1,-1,1,1},dy[4]={-1,1,-1,1};
// 移动过程中对应穿过的格子坐标偏移
int cx[4]={-1,-1,0,0},cy[4]={-1,0,-1,0};
char ideal[4]={'\\','/','/','\\'}; // 左上、右上、左下、右下逐项对应

void solve(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) cin>>a[i][j];
	}
	
	// 起点(1,1)和终点(n+1,m+1)不在同一对角线回路上
	if((n+m)%2!=0){
		cout<<"NO SOLUTION\n";
		return;
	}
	
	memset(dis,0x3f,sizeof(dis));
	deque<pair<int,int>> q;
	q.push_front({1,1});
	dis[1][1]=0;
	
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;
		q.pop_front();
		
		if(x==n+1&&y==m+1){
			cout<<dis[x][y]<<'\n';
			return;
		}
		
		for(int i=0;i<4;i++){
			int nx=x+dx[i],ny=y+dy[i];
			int gx=x+cx[i],gy=y+cy[i];
			
			if(nx>=1&&nx<=n+1&&ny>=1&&ny<=m+1){
				int w=(a[gx][gy]!=ideal[i]);
				if(dis[nx][ny]>dis[x][y]+w){
					dis[nx][ny]=dis[x][y]+w;
					if(w==0) q.push_front({nx,ny});
					else q.push_back({nx,ny});
				}
			}
		}
	}
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

4. 题型四：数学性质推导降维

例 5：CF1063B Labyrinth

思路：题目限制了向左最多 $X$ 步，向右最多 $Y$ 步。如果在队列里记录四个状态（加上左右步数），必然 MLE。

破局点：根据平面坐标的相对关系，无论中间怎么绕路，终点坐标恒满足：终点列 y - 起点列 c = 向右总步数 R - 向左总步数 L。

由此可知，只要保证到达某点时的向左步数 $L$ 最少，对应的向右步数 $R$ 也必然是所有合法路径中最少的。将向左移动的代价设为 $1$ ，其余三个方向代价设为 $0$ 。跑一次 01BFS 即可得到所有点的最少左移步数。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2005;

int n,m,r,c,lx,ly;
char a[N][N];
int dis[N][N];
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};

void solve(){
	cin>>n>>m>>r>>c>>lx>>ly;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) cin>>a[i][j];
	}
	
	memset(dis,0x3f,sizeof(dis));
	deque<pair<int,int>> q;
	q.push_front({r,c});
	dis[r][c]=0;
	
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;
		q.pop_front();
		
		for(int i=0;i<4;i++){
			int nx=x+dx[i],ny=y+dy[i];
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]=='.'){
				int w=(dy[i]==-1?1:0); // 只有向左走代价为 1
				if(dis[nx][ny]>dis[x][y]+w){
					dis[nx][ny]=dis[x][y]+w;
					if(w==0) q.push_front({nx,ny});
					else q.push_back({nx,ny});
				}
			}
		}
	}
	
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(dis[i][j]>1e18) continue;
			int left_cnt=dis[i][j];
			int right_cnt=left_cnt+(j-c);
			if(left_cnt<=lx&&right_cnt<=ly) ans++;
		}
	}
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

5. 题型五：二分答案嵌套图论 01BFS

例 6：P1948 Telephone Lines S

思路：题目要求找一条路径，使得该路径上第 $K+1$ 大的边尽可能小。这是经典的“最大值最小”模型，使用二分答案解决。

假设当前二分的答案为 $mid$ ，我们将原图中所有长度 $> mid$ 的边代价记为 $1$ （表示不得不消耗掉一次免费连接的名额）， $\le mid$ 的边代价记为 $0$ 。每次 Check 时，以点 $1$ 为源点跑一次图论版的 01BFS。如果到达点 $n$ 消耗的最少名额 $\le k$ ，说明当前 $mid$ 是合法的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;

int n,p,k;
vector<pair<int,int>> node[N];
int dis[N];

bool check(int mid){
	memset(dis,0x3f,sizeof(dis));
	deque<int> q;
	q.push_front(1);
	dis[1]=0;
	
	while(!q.empty()){
		int u=q.front();
		q.pop_front();
		
		for(auto edge:node[u]){
			int v=edge.first,len=edge.second;
			int w=(len>mid?1:0);
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				if(w==0) q.push_front(v);
				else q.push_back(v);
			}
		}
	}
	return dis[n]<=k;
}

void solve(){
	cin>>n>>p>>k;
	for(int i=1;i<=p;i++){
		int u,v,w;
		cin>>u>>v>>w;
		node[u].push_back({v,w});
		node[v].push_back({u,w});
	}
	
	int l=0,r=1e6+5,ans=-1;
	while(l<=r){
		int mid=(l+r)>>1;
		if(check(mid)){
			ans=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	}
	cout<<ans<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	solve();
	return 0;
}

四、进阶技巧与模型补齐

1. 多源 0-1 BFS：从单个起点到多个起点的蔓延

场景：如果地图上有多个起点（例如同时扩散的多个感染区或火源），我们需要找全图每个点到最近起点的代价。

如果对每个起点都跑一次完整的 BFS，必然会超时。我们只需在 BFS 开始前，把所有起点全部压入双端队列的队首，并初始化它们的距离为 0。

物理意义：这就好比在天上建了一个“超级源点”，它到所有实际起点的距离都是 0（边权为 0，理应插队放到队首）。这就把多源最短路降维成了单源最短路，完全兼容 0-1 BFS。

💡 【实战小例子】 地图上有 $k$ 个毒气泄漏点，毒气走平地花费 0（瞬间蔓延），穿过防毒门花费 1。
C++
memset(dis, 0x3f, sizeof(dis));
deque<pair<int,int>> q;
// 把所有泄漏点作为起点，全部入队
for(int i = 1; i <= k; i++){
    q.push_front({px[i], py[i]});
    dis[px[i]][py[i]] = 0;
}
// 接下来正常进入 while(!q.empty()) 跑 0-1 BFS 即可

2. 状态空间的扩展：把“是否使用操作”并入状态

分层建图的完整讲解见《最短路与状态建图》第十节。这里的状态设计相同，只是边权限于 0、1，可以改用双端队列：免费跨层边用 push_front，其余边也按 0 前 1 后入队。

在前面的 CF173B 中，我们已经看到如何把“当前朝向”这一维度并入状态。还有一类极高频的考法：你拥有若干次“特权”（比如一次免费穿墙、一次免疫伤害）。

这就需要把“是否用过特权”加进状态里：定义 dis[x][y][used]，其中 used=0 表示特权未使用，used=1 表示已使用。

转移逻辑拆解：

不使用特权正常走：花费原本的代价 $w$ ，状态从 used 转移到 used。
发动特权走：如果你正面临一堵代价为 1 的墙，且 used == 0（特权还在），那么你可以花费 0 的代价穿过它。状态从 0 转移到 1，代价为 0，理直气壮地压入队首 push_front。

这就把图切分成了“使用特权前”和“使用特权后”两层，跨层边就是那次特权操作，同样完美契合 0-1 BFS 体系。

3. 记录前驱：还原最短路的真实轨迹

只求出最小代价往往不够，如果题目要求输出完整路径，我们需要在“松弛成功”的瞬间记录脚印。

实现法则：新增一个与 dis 维度一致的 pre 数组。在执行 dis[nx][ny] = dis[x][y] + w; 时，顺手记录 pre[nx][ny] = {x, y}。搜索结束后，从终点逆向回溯即可。

💡 【实战例题：带路径输出的破墙迷宫】 题意：从 (1,1) 走到 (n,m)。走空地 . 代价为 0，打破墙壁 # 代价为 1。求最少破墙次数，并打印出坐标轨迹。如果有多次机会同等破墙，输出任意一条最短路即可。 数据范围： $n, m \le 1000$ 。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1005;

int n, m;
char a[N][N];
int dis[N][N];
pair<int,int> pre[N][N];
int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1};

void solve(){
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++) cin >> a[i][j];
    }
    
    memset(dis, 0x3f, sizeof(dis));
    deque<pair<int,int>> q;
    q.push_front({1, 1});
    dis[1][1] = 0;
    
    while(!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop_front();
        
        // 第一次出队即是最短路，到达终点即可结束扩展
        if(x == n && y == m) break; 
        
        for(int i=0; i<4; i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx >= 1 && nx <= n && ny >= 1 && ny <= m){
                int w = (a[nx][ny] == '#' ? 1 : 0);
                if(dis[nx][ny] > dis[x][y] + w){
                    dis[nx][ny] = dis[x][y] + w;
                    pre[nx][ny] = {x, y}; // 顺手记录是从哪个坐标走过来的
                    if(w == 0) q.push_front({nx, ny});
                    else q.push_back({nx, ny});
                }
            }
        }
    }
    
    cout << dis[n][m] << '\n';
    
    // 逆向回溯路径
    vector<pair<int,int>> path;
    int cx = n, cy = m;
    while(cx != 0 && cy != 0){ // 回溯到起点 (1,1) 的前驱 (0,0) 为止
        path.push_back({cx, cy});
        pair<int,int> p = pre[cx][cy];
        cx = p.first;
        cy = p.second;
    }
    
    reverse(path.begin(), path.end()); // 翻转得到正向路径
    for(auto p : path) cout << p.first << " " << p.second << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    solve();
    return 0;
}
/*
自拟样例：
输入：
4 4
.###
.###
..##
#..#
输出：
1
1 1
2 1
3 1
3 2
4 2
4 3
4 4
*/

4. 性能优化：出队即永久访问（`vis` 标记的正确用法）

在前面的第二部分我们强调过：绝对不能在入队时打 vis 标记，否则会阻拦更优解。但这并不意味着 0-1 BFS 彻底抛弃了 vis。

联系 Dijkstra 算法的核心：当一个节点被弹出优先队列时，它的最短路就被永久确定了。在 0-1 BFS 的双端队列里也是完全一样的道理：当节点第一次从队首被取出时，当前积累的距离就是它的绝对最短路。

如果图中存在错综复杂的 0 权边环，一个节点可能会被多次松弛并推入队列。为了避免重复向外扩展浪费时间，我们应该在出队的瞬间给它打上标记。

标准防卡写法片段（结合已有模板）：

bool vis[N][N]; // 全局访问标记

while(!q.empty()){
    int x = q.front().first, y = q.front().second;
    q.pop_front();
    
    // 节点第一次出队，最短路已被确认；若已出队过，直接跳过冗余扩展
    if(vis[x][y]) continue; 
    vis[x][y] = 1; 
    
    if(x == ex && y == ey) return; 
    
    // ... 下面继续 for 循环四向松弛，逻辑不变
}

这样既保留了 0-1 BFS 正确松弛的权利，又避免了反复扩展同一个节点，确保时间复杂度严格保持在 $O(V+E)$ 。

0-1 BFS