我感觉这个算法是作为dijkstra等求最短路的优秀替换！

适用于求最短路或者其他的，但是有个特征：边权为0和1(或0和其他正数）。

求最短路的时间复杂度可以由 O(mlogn) 降到 O(m)！(n为点的个数，m为边的个数）

原理：感觉就是 dijkstra 的优化。如果边权只是 0 和 1 的话，启用优先队列未免太浪费资源了！这里用双端队列正是对这个地方的优化，将优先队列插入元素 O(logn) 的时间复杂度降到了 O(1)！！

过程是这样的：

• 从起点开始，加入队列。

• while队列非空，取队首元素，用这个节点更新其他节点。

• 如果可以更新的话：

  1、边权为0，放到队首。（从边权为0的边走，不增加消耗，得多走这样的边）

  2、边权为其他，放到队尾。（增加消耗，少用）

（这样，队列前面的元素值一定比后面的元素值小（可以手动模拟下），每次求队首元素来更新相连的点的距离，完美的替代了优先队列的功能！）

典例1——小明的游戏：

大意：一个棋盘，从初始点走到终点，棋盘坐标中有两个符号。上下左右四个方向走，如果当前的符号和要走到的位置符号一样的话，不花费；如果不一样，花费1。求从起点到终点的最小花费。

思路：边权0和1，清清楚楚。队列中存坐标！

Code：

#include<iostream>
#include<cstring>
#include<queue> 
using namespace std;

const int N=510;
int n,m,a[N][N],dist[N][N],stx,sty,enx,eny;
typedef pair<int,int> PII;
int dir[4][2]={{-1,0},{0,-1},{0,1},{1,0}}; 
bool f[N][N];

//有权值的边1放队尾，少用；无权值0放队首，尽量用；
//这样先出队的队头元素永远是距离较小的点，完美替代优先队列。

void bfs()
{
	memset(dist,0x3f,sizeof dist);
	memset(f,0,sizeof f); 
	dist[stx][sty]=0;
	
	deque<PII> que;
	que.push_front({stx,sty});
	
	while(que.size())
	{
		int x=que.front().first,y=que.front().second;
		que.pop_front(); 
		if(f[x][y]) continue; //该点之前出队过，最短路径已确定，跳过。
		
		f[x][y] = true;
		for(int i=0;i<4;i++)
		{
			int tx=x+dir[i][0],ty=y+dir[i][1],flag=0;
			
			if(tx<1||tx>n||ty<1||ty>m) continue;
			
			if(a[x][y]!=a[tx][ty]) flag=1;
			if(dist[tx][ty]>dist[x][y]+flag){
				dist[tx][ty]=dist[x][y]+flag;
				if(flag) que.push_back({tx,ty}); //有权值的边放队尾，少用 
				else que.push_front({tx,ty}); //无权值放队首，尽量用 
			}
		}
	}
}

int main(){
	while(cin>>n>>m&&n!=0&&m!=0)
	{
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				a[i][j]=0;
				char c;cin>>c;
				if(c=='@') a[i][j]=1; 	
			}
		}
		cin>>stx>>sty>>enx>>eny;
		stx++,sty++,enx++,eny++;
		bfs();
		cout<<dist[enx][eny]<<endl;
	}
	return 0;
} 

但是，并不只是局限于边权是0和1的情况，比如说，下面这个题。

典例2——Labyrinth：

大意：走迷宫，给出一个起点。规定只能往左走l步，往右走r步，往上和往下任意走。求能够到达的位置的个数。

分析：这个题也能用01bfs来做！往上走和往下走的话，花费为0，更新节点放到队首，要尽量往上走和往下走。往左和往右走，更新节点放队尾，有花费，少用！跑一遍bfs就行了。

#include<iostream>
#include<queue>
using namespace std;

const int N=2010;
int n,m,a[N][N],stx,sty,l,r;
struct node{
	int x,y,l,r;
};
bool f[N][N];
int dir[4][2]={{1,0},{-1,0},{0,-1},{0,1}},cnt;

//双端队列
//往上或往下走是不消耗资源的，于是优先进行这两种操作，每次更新放到队首
//往左或往右走消耗资源，于是尽量少执行，每次更新放到队尾

void bfs()
{
	deque<node> que; //双端队列中存结构体 
	que.push_front({stx,sty,l,r});
	cnt++;
	f[stx][sty]=true;
	
	while(que.size())
	{
		int x=que.front().x,y=que.front().y,tl=que.front().l,tr=que.front().r;
		que.pop_front();
		
		for(int i=0;i<4;i++)
		{
			int tx=x+dir[i][0],ty=y+dir[i][1];
			if(tx<1||tx>n||ty<1||ty>m||!a[tx][ty]||f[tx][ty]) continue; //不能走或走过了 
			
			if(i==0||i==1){ //往上或往下走放队首，多用 
				que.push_front({tx,ty,tl,tr});
				f[tx][ty]=true;cnt++;
			}
			else if(i==2){ //往左放队尾，少用 
				if(tl<1) continue; //当前节点往左走资源不足 
				que.push_back({tx,ty,tl-1,tr});
				f[tx][ty]=true;cnt++;
			}
			else if(i==3){
				if(tr<1) continue;
				que.push_back({tx,ty,tl,tr-1});
				f[tx][ty]=true;cnt++;
			}
		}
	}
}

int main(){
	cin>>n>>m;
	cin>>stx>>sty;
	cin>>l>>r;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			char c;cin>>c;
			if(c=='.') a[i][j]=1;
		}
	}
	bfs();
	
	cout<<cnt;
	return 0;
} 

此外，01bfs不一定在题目中体现出来。完全可能作为题意的转换。

典例3——通信线路

大意：从1到n，选一条路，所有的边中，能将k条权值变为0，剩余边的权值的最大值最小为多少？

最大值最小，很容易想到二分。那就二分答案，二分权值的取值范围：判断条件为，从1到n，能否存在一条路径，其中的边的权值大于mid的个数小于等于k！

这样，dist数组存的就不是距离起点的最短距离了，而是从起点过来所经过的大于mid的边的最少个数！（这种题型之前也是见过的，是最短路题型的转化）

这样，边权就换成了0和1！如果原来的边权大于mid，那新边权就是1，否则就是0。我们求从节点1到节点n的最短路。

如果对二分答案不太熟的话，可以参考我的这篇博客：二分查找 & 二分答案 万字详解，超多例题，带你学透二分！！（QWQ，安利一波自己的博客，逃~

Code：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int N=20010;
int n,m,k,e[N],ne[N],w[N],h[N],idx;
int dist[1010];

//dist[i]数组中存的是1~i路径中，最少经过的权值>k的边数 
//在01边权求最短路的问题中，双端队列是 dij等求最短路的 优秀替代！ 

void add(int x,int y,int z){
	e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;
}

int check(int mid)
{
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	deque<int> que;
	que.push_back(1);
	
	while(que.size())
	{
		int x=que.front();
		que.pop_front();
		if(f[x]) continue;
		
		f[x]=true;
		for(int i=h[x];i!=-1;i=ne[i])
		{
			int tx=e[i],flag=0;
			
			if(w[i]>mid) flag=1;
			if(dist[tx]>dist[x]+flag){
				dist[tx]=dist[x]+flag;
				if(flag) que.push_back(tx);
				else que.push_front(tx);
			}
		}
	}
	if(dist[n]==0x3f3f3f3f) return -1;
	if(dist[n]>k) return 0;
	return 1;
}

int main(){
	cin>>n>>m>>k;
	memset(h,-1,sizeof h);
	while(m--)
	{
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	int l=0,r=1e6;
	while(l<r)
	{
		int mid=l+r>>1;
		int t=check(mid);
		if(t==-1){
			cout<<-1;return 0;
		}
		if(t) r=mid;
		else l=mid+1;
	}
	cout<<l;
	return 0;
} 

典例4——电路维修

大意：一个n*m的格子，每个格子有一道斜线（左斜或右斜），要求，改变其中几个斜线的方向，使从左上角能连接到右下角。求改变的最小个数。

分析：

把每个格子的四个角当作节点（注），那么整张图就变成了这样：

如果，两个节点有边连接，走过去边权为0；否则，走过去边权为1。这样，dist数组中存的是最少需要移动的格子数量，就找到了到终点最少移动数。
但是，有个问题，如何标记这两个点之间有边相连？

一开始想到，用数组存坐标，那得用四维数组，开不了那么大，不行。那，用map！那，map里有两个点的坐标，得用二维map，而且两个元素都是PII！

 map<PII,map<PII,int>>;
 a[{i,j}][{i+1,j+1}]=1;

嘿，能用！提交一下。。。超时！？？可能是map更新太耗时了。

方法1：

那，要不就建边？建边就得将二维换成一维了。稍微推了一下，出了一个公式，该点的编号为：m*x + y - m（m为矩阵宽）；这样就把二维转换为一维了。
那，如何建边呢？输入的时候，如果是‘ \ ‘，就把当前的节点和右下角的节点建边，边权为0，同时，反向建（无向边）。如果是’/ ',类似。这样，就建好了边。
接着就遍历就可以了。如果是和相连的节点边权为0，走过去放到队首；如果为1，放到队尾。
有一个需要注意的问题：e[N*N*4]等建边的数组要开够！！一共N*N个节点，每个节点建四条边！否则，超时！！（亲测，呜呜呜。。）

Code：

#include<iostream>
#include<cstring>
#include<queue>
#include<map>
using namespace std;

const int N=510;
int n,m,T,dist[N*N];
int e[N*N*4],ne[N*N*4],w[N*N*4],h[N*N],idx;
//数组大小计算，一共N*N个点，每个点建四条边！ 

void add(int x,int y,int z){
	e[idx]=y,w[idx]=z,ne[idx]=h[x],h[x]=idx++;
} 

void bfs()
{
	memset(dist,0x3f,sizeof dist);
	dist[1]=0;
	deque<int> que;
	que.push_back(1);
	
	while(que.size())
	{
		int x=que.front();
		que.pop_front();
		
		for(int i=h[x];i!=-1;i=ne[i])
		{
			int tx=e[i],flag=w[i];
			
			if(dist[tx]>dist[x]+flag){
				dist[tx]=dist[x]+flag;
				if(flag) que.push_back(tx);
				else que.push_front(tx);
			}
		}
	}
}

int main()
{
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		idx=0;
		memset(h,-1,sizeof h);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				char c;cin>>c;
				int t1,t2;
				if(c=='\\') t1=0,t2=1;
				else t1=1,t2=0;
				//二维坐标编号(m*x+y-m)变一维，建边 
				add((m+1)*i+j-(m+1),(m+1)*(i+1)+(j+1)-(m+1),t1);
				add((m+1)*(i+1)+(j+1)-(m+1),(m+1)*i+j-(m+1),t1);
				add((m+1)*i+j+1-(m+1),(m+1)*(i+1)+j-(m+1),t2);
				add((m+1)*(i+1)+j-(m+1),(m+1)*i+j+1-(m+1),t2);
			}
		}
		bfs();
		if(dist[(n+1)*(m+1)]!=0x3f3f3f3f) cout<<dist[(n+1)*(m+1)]<<endl;
		else cout<<"NO SOLUTION"<<endl;
	}
}

方法2：

之后，又发现一种方法，不用化一维，也不用建边，类似于邻接矩阵，省了好多事！
开一个三维数组，前两维存的是坐标，后一维存的是标记相连的边的方位（分别为0，1，2，3）。如果为1，说明这个方位存在与其相连的边；否则就不存在。这样，从左上角的坐标开始，遍历四个方位，如果与其有连边，走过去边权为0，放队首；否则，走过去边权为1，放队尾。

Code：

#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int N=510;
int n,m,T,a[N][N][5],dist[N][N],f[N][N];
typedef pair<int,int> PII;
int dir[4][2]={{-1,-1},{-1,1},{1,-1},{1,1}};
//a[i][j][k]：判断点(i,j)的k方向有没有相连 

void bfs()
{
	memset(dist,0x3f,sizeof dist);
	dist[1][1]=0;
	deque<PII> que;
	que.push_back({1,1});
	
	while(que.size())
	{
		int x=que.front().first,y=que.front().second;
		que.pop_front();
		
		for(int i=0;i<4;i++)
		{
			int tx=x+dir[i][0],ty=y+dir[i][1],flag=0;
			if(tx<1||tx>n+1||ty<1||ty>m+1) continue;
			
			if(!a[x][y][i]) flag=1; //判断这个方向是否相连 
			if(dist[tx][ty]>dist[x][y]+flag){
				dist[tx][ty]=dist[x][y]+flag;
				if(flag) que.push_back({tx,ty}); //和i方向不相连，走过去耗费1，放队尾，尽量少用 
				else que.push_front({tx,ty}); //相连，不花费，放队首，多用 
			}
		}
	}
}

int main()
{
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		memset(a,0,sizeof a);
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				char c;cin>>c;
				if(c=='\\') a[i][j][3]=1,a[i+1][j+1][0]=1;
				else a[i][j+1][2]=1,a[i+1][j][1]=1;
			}
		}
		bfs();
		if(dist[n+1][m+1]!=0x3f3f3f3f) cout<<dist[n+1][m+1]<<endl;
		else cout<<"NO SOLUTION"<<endl;
	}
}

注：
问什么要将格子的四个角看作节点，而不把整个格子直接当作节点呢？如果相邻的格子中能走就走，不能走就让距离+1。这样问什么不行呢？二刷的时候遇到了这个问题。
答：当走到一个点，遍历其相邻格子的时候发现不能到达相邻格子，那么就要把当前格子转动，才能到达。但是，当前格子的状态是没转动之前得到的，把当前格子转动之后，目前的状态就需要改变，不能用这个格子的状态去更新相邻格子的状态。于是就混乱了。
而把格子间的交点当作节点就不会出现这个问题。

---

总结下：基本上都是在求最短路时用到，边权有特点：有的边权为0！边权为0的放到队首，多用这样的节点，边权为其他正数（常见为1）的放到队尾，少用这样的节点。

当然，这样的题完全可以跑最短路，但是 01bfs 比其时间复杂度低！

01bfs：O(m)
堆优化dijkstra：O(mlongn)

哈哈，先这么多，有新题的话会更新的~
如果哪里不对或者不明白的地方欢迎留言评论呀~