BFS（廣度優先搜尋，也可稱寬度優先搜尋）是連通圖的一種遍歷策略。
因為它的基本思想是從一個頂點V0 ... BFS演算法一般應用於單源最短路徑的搜尋。
BFS(廣度優先搜尋演算法)
首頁
最新
HTML
CSS
JavaScript
jQuery
Python3
Python2
Java
C
C++
Go
SQL
首頁
最新
Search
BFS(廣度優先搜尋演算法)
2018-12-14254
一、BFS的介紹BFS（廣度優先搜尋，也可稱寬度優先搜尋）是連通圖的一種遍歷策略。
因為它的基本思想是從一個頂點V0開始，輻射狀地優先遍歷其周圍較廣的區域。
廣度優先搜尋（BFS）類似於二叉樹的層序遍歷演算法，它的基本思想是：首先訪問起始頂點v，然後由v出發，依次訪問v的各個未被訪問過的鄰接頂點w1,w2,w3….wn，然後再依次訪問w1，w2,…,wi的所有未被訪問過的鄰接頂點，再從這些訪問過的頂點出發，再訪問它們所有未被訪問過的鄰接頂點….以此類推，直到途中所有的頂點都被訪問過為止。
類似的想法還將應用與Dijkstra單源最短路徑演算法和Prim最小生成樹演算法。
廣度優先搜尋是一種分層的查詢過程，每向前走一步可能訪問一批頂點，不像深度優先搜尋（DFS）那樣有回退的情況，因此它不是一個遞迴的演算法，為了實現逐層的訪問，演算法必須藉助一個輔助佇列並且以非遞迴的形式來實現。
二、BFS搜尋的步驟 1、首先建立一個visit[]陣列和一個佇列q，分別用來判斷該位置是否已經訪問過及讓未訪問過的點入隊； 2、初始化visit[]陣列，清空q佇列； 3、讓起點start入隊，並使該點的visit置1； 4、while（！q.empty()）{......}執行搜尋操作， a、取出隊頭元素後使隊頭元素出隊，判斷該元素是否為目標到達點； b、如果是目標點，就返回結果（一般是最短時間、最短路徑）； c、如果不是目標點，就繼續訪問與其相鄰的位置點，將可走的相鄰的位置點入隊，並更新visit[]陣列；
三、BFS的應用BFS演算法一般應用於單源最短路徑的搜尋。
1、尋找非加權圖（或者所有邊權重相同）中任兩點的最短路徑。
2、尋找其中一個連通分支中的所有節點。
（擴散性）3、bfs染色法判斷是否為二分圖。
四、核心程式碼
#include
#include
#include
#definemaxn105
usingnamespacestd;
intn,m; //矩陣的大小
intsx,sy;
intvis[maxn][maxn],s[maxn][maxn],t[maxn][maxn];
queueQ;
intpx[]={1,-1,0,0}; //人可走的4個方向
intpy[]={0,0,1,-1};
structnode{
intx,y,step;
}r,p,q;
intBFS()
{
//清空佇列及初始化vis陣列
while(!Q.empty())
Q.pop();
memset(vis,0,sizeof(vis));
p.x=sx;
p.y=sy;
p.step=0;
vis[p.x][p.y]=1;
Q.push(p);
while(!Q.empty())
{
p=Q.front();
Q.pop();
if(s[p.x][p.y]=='t')
returnp.step;
for(inti=0;i<4;i++)
{
q=p;
q.x+=px[i];
q.y+=py[i];
q.step++;
if(q.x<0||q.y<0||q.x>=n||q.y>=m)
continue;
//訪問未被訪問過的位置，且此時是在火勢蔓延到此前訪問的，再將該位置入隊
if(vis[q.x][q.y]==0&&q.step
usingnamespacestd;
intn,a,b;
intque[222]={};
intk[222]={};
intvis[222]={};//標記是否詢問過
inttmp[222]={};
inthead=1,tail=0;//隊首隊尾指標
voidbfs(intnow)
{
for(;head<=tail;)//當佇列不為空時
{
inttop=que[head];//top為隊首的層數
head++;//彈出隊首
if(top==b)
return;//假如已經到達了目標（b）層，直接退出
if(top+k[top]<=n&&vis[top+k[top]]==0)//假如沒有超出邊界並且沒有訪問過
{
que[++tail]=top+k[top];//入隊
tmp[top+k[top]]=tmp[top]+1;//次數為上一次+1
vis[top+k[top]]=1;//標記
}
if(top-k[top]>=1&&vis[top-k[top]]==0)
{
que[++tail]=top-k[top];
tmp[top-k[top]]=tmp[top]+1;
vis[top-k[top]]=1;
}
}
return;
}
intmain()
{
cin>>n>>a>>b;
for(inti=1;i<=n;i++)
cin>>k[i];
que[++tail]=a;
vis[a]=1;
bfs(a);
if(vis[b]==0)//假如沒有訪問過
cout<
usingnamespacestd;
intm,n,m1,m2;
inta[33][33]={};
intvis[33][33]={};
intans[33][33]={};
intlx,ly;
structkk
{
intx;
inty;
}que[3333]={};
inthead=1,tail=0;
intbfs()
{
for(;head<=tail;)
{
intx=que[head].x;
inty=que[head].y;//記錄隊首的座標
head++;//彈出隊首
if(x==lx&&y==ly)
returnans[x][y];//返回答案
if(x+m1<=m&&y+m2<=n&&vis[x+m1][y+m2]==0&&a[x+m1][y+m2]==1)
{
que[++tail]=(kk){x+m1,y+m2};
vis[x+m1][y+m2]=1;
ans[x+m1][y+m2]=ans[x][y]+1;
}
if(x-m1>0&&y-m2>0&&vis[x-m1][y-m2]==0&&a[x-m1][y-m2]==1)
{
que[++tail]=(kk){x-m1,y-m2};
vis[x-m1][y-m2]=1;
ans[x-m1][y-m2]=ans[x][y]+1;
}
if(x-m1>0&&y+m2<=n&&vis[x-m1][y+m2]==0&&a[x-m1][y+m2]==1)
{
que[++tail]=(kk){x-m1,y+m2};
vis[x-m1][y+m2]=1;
ans[x-m1][y+m2]=ans[x][y]+1;
}
if(x+m1<=m&&y-m2>0&&vis[x+m1][y-m2]==0&&a[x+m1][y-m2]==1)
{
que[++tail]=(kk){x+m1,y-m2};
vis[x+m1][y-m2]=1;
ans[x+m1][y-m2]=ans[x][y]+1;
}
if(x+m2<=m&&y+m1<=n&&vis[x+m2][y+m1]==0&&a[x+m2][y+m1]==1)
{
que[++tail]=(kk){x+m2,y+m1};
vis[x+m2][y+m1]=1;
ans[x+m2][y+m1]=ans[x][y]+1;
}
if(x-m2>0&&y-m1>0&&vis[x-m2][y-m1]==0&&a[x-m2][y-m1]==1)
{
que[++tail]=(kk){x-m2,y-m1};
vis[x-m2][y-m1]=1;
ans[x-m2][y-m1]=ans[x][y]+1;
}
if(x-m2>0&&y+m1<=n&&vis[x-m2][y+m1]==0&&a[x-m2][y+m1]==1)
{
que[++tail]=(kk){x-m2,y+m1};
vis[x-m2][y+m1]=1;
ans[x-m2][y+m1]=ans[x][y]+1;
}
if(x+m2<=m&&y-m1>0&&vis[x+m2][y-m1]==0&&a[x+m2][y-m1]==1)
{
que[++tail]=(kk){x+m2,y-m1};
vis[x+m2][y-m1]=1;
ans[x+m2][y-m1]=ans[x][y]+1;
}
}//八個方向進行跳躍
}
intmain()
{
cin>>m>>n>>m1>>m2;
for(inti=1;i<=m;i++)
for(intj=1;j<=n;j++)
{
cin>>a[i][j];
if(a[i][j]==3)
{
que[++tail]=(kk){i,j};
vis[i][j]=1;
}//如果為初始位置，入隊，並進行標記
if(a[i][j]==4)
{
lx=i;
ly=j;
a[i][j]=1;//為了方便，這樣只需要判斷a[i][j]為1時可以跳躍
}//記錄結束位置
}
cout<
