一、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<iostream> #include<queue> #include<string.h> #define maxn 105 using namespace std;int n,m; ? ?//矩陣的大小? int sx,sy;? int vis[maxn][maxn],s[maxn][maxn],t[maxn][maxn]; queue<struct node>Q;? int px[]={1,-1,0,0}; ? ? ? ?//人可走的4個方向? int py[]={0,0,1,-1}; struct node{int x,y,step; }r,p,q;int BFS() { ??//清空隊列及初始化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')return p.step;for(int i=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<t[q.x][q.y]){vis[q.x][q.y]=1;Q.push(q);}}}return -1; }int main(){//功能需求代碼?//........return 0; }

五、例題?

【奇怪的電梯】

-題目描述-

有一天我做了一個夢，夢見了一種很奇怪的電梯。大樓的每一層樓都可以停電梯，而且第i層樓(1<=i<=N)上有一個數字Ki(0<=Ki<=N)。電梯只有四個按鈕：開，關，上，下。上下的層數等于當前樓層上的那個數字。當然，如果不能滿足要求，相應的按鈕就會失靈。例如：3 3 1 2 5代表了Ki(K1=3,K2=3,……)，從一樓開始。在一樓，按“上”可以到4樓，按“下”是不起作用的，因為沒有-2樓。那么，從A樓到B樓至少要按幾次按鈕呢？點擊打開鏈接

-輸入格式-

共二行。第一行為 3 個用空格隔開的正整數，表示 N,A,B(1≤N≤200, 1≤A,B≤N)N,A,B(1≤N≤200,1≤A,B≤N) 。第二行為 N 個用空格隔開的非負整數，表示 K_i。

-輸出格式-

一行，即最少按鍵次數,若無法到達，則輸出?-1?1?。

-樣例數據-

input

5 1 5
3 3 1 2 5
output

3
-分析-

這道題所要求的是最小值（最少要按的按鈕數）。用BFS找到答案便可以退出（DFS不能保證答案為最優解）。要注意邊界：是否可以繼續往上或向下（沒有0樓，-1樓......）。

-代碼-

#include<bits/stdc++.h> using namespace std; int n,a,b; int que[222]={}; int k[222]={}; int vis[222]={};//標記是否詢問過 int tmp[222]={}; int head=1,tail=0;//隊首隊尾指針 void bfs(int now) {for(;head<=tail;)//當隊列不為空時{int top=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;//次數為上一次+1vis[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 ; } int main() {cin>>n>>a>>b;for(int i=1;i<=n;i++)cin>>k[i];que[++tail]=a;vis[a]=1;bfs(a);if(vis[b]==0)//假如沒有訪問過cout<<-1<<endl;else//訪問過cout<<tmp[b]<<endl;return 0; }

【青銅蓮花池】

-題目描述-

為了讓奶牛們娛樂和鍛煉，農夫約翰建造了一個美麗的池塘。這個長方形的池子被分成了 M 行 N 列個方格（1 ≤ M, N ≤ 30） 。一些格子是堅固得令人驚訝的蓮花，還有一些格子是巖石，其余的只是美麗、純凈、湛藍的水。貝西正在練習芭蕾舞，她站在一朵蓮花上，想跳到另一朵蓮花上去，她只能從一朵蓮花跳到另一朵蓮花上，既不能跳到水里，也不能跳到巖石上。貝西的舞步很像象棋中的馬步：每次總是先橫向移動 M1 (1 ≤ M1 ≤ 30)格，再縱向移動 M2 (1 ≤ M2 ≤ 30, M1≠M2)格，或先縱向移動 M1 格，再橫向移動 M2 格。最多時，貝西會有八個移動方向可供選擇。給定池塘的布局和貝西的跳躍長度，請計算貝西從起點出發，到達目的地的最小步數，我們保證輸入數據中的目的地一定是可達的。點擊打開鏈接

-輸入格式-

第一行：四個用空格分開的整數：M，N，M1 和 M2第二行到 M + 1 行：第 i + 1 行有 N 個用空格分開的整數，描述了池塘第i 行的狀態：0 為水，1 為蓮花，2 為巖石，3 為貝西所在的起點，4 為貝西想去的終點。

-輸出格式-

一行，從起點到終點的最少步數。

-樣例數據-

input

4 5 1 2
1 0 1 0 1
3 0 2 0 4
0 1 2 0 0
output

2
-分析-

貝西的跳躍方式像馬（馬按“日”字形走（點擊打開鏈接））。只要列出八個方向，判斷這幾個方向是否可以進行跳躍（跳躍到的位置必須有蓮葉且先前沒有進行過標記），如果可以則入隊，不斷彈出隊首，直至隊列為空或者跳到目標位置，跳出循環。

-代碼-

#include<bits/stdc++.h> using namespace std; int m,n,m1,m2; int a[33][33]={}; int vis[33][33]={}; int ans[33][33]={}; int lx,ly; struct kk {int x;int y; } que[3333]={}; int head=1,tail=0; int bfs() {for(;head<=tail;){int x=que[head].x;int y=que[head].y;//記錄隊首的坐標head++;//彈出隊首if(x==lx&&y==ly)return ans[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;}}//八個方向進行跳躍 } int main() {cin>>m>>n>>m1>>m2;for(int i=1;i<=m;i++)for(int j=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<<bfs()<<endl;//bfsreturn 0; }

?

總結

以上是生活随笔為你收集整理的BFS(广度优先搜索算法)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。