本篇將會結(jié)合實例解析寬度優(yōu)先搜索(BFS)。

一、BFS概念

寬度優(yōu)先搜索算法（又稱廣度優(yōu)先搜索）是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。其別名又叫BFS，屬于一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點，以找尋結(jié)果。換句話說，它并不考慮結(jié)果的可能位置，徹底地搜索整張圖，直到找到結(jié)果為止。

所謂廣度，就是一層一層的，向下遍歷，層層堵截，還是這幅圖，我們?nèi)绻菑V度優(yōu)先遍歷的話，我們的結(jié)果是V1 V2 V3 V4 V5 V6 V7 V8。

（1）訪問頂點vi ；

（2）訪問vi 的所有未被訪問的鄰接點w1 ,w2 , …wk ；

（3）依次從這些鄰接點（在步驟②中訪問的頂點）出發(fā)，訪問它們的所有未被訪問的鄰接點; 依此類推，直到圖中所有訪問過的頂點的鄰接點都被訪問；

二、BFS（廣度優(yōu)先搜索）

廣度優(yōu)先搜索較之深度優(yōu)先搜索之不同在于，深度優(yōu)先搜索旨在不管有多少條岔路，先一條路走到底，不成功就返回上一個路口然后就選擇下一條岔路，而廣度優(yōu)先搜索旨在面臨一個路口時，把所有的岔路口都記下來，然后選擇其中一個進入，然后將它的分路情況記錄下來，然后再返回來進入另外一個岔路，并重復這樣的操作，用圖形來表示則是這樣的。

從黑色起點出發(fā)，記錄所有的岔路口，并標記為走一步可以到達的。然后選擇其中一個方向走進去，我們走黑點方塊上面的那個，然后將這個路口可走的方向記錄下來并標記為2，意味走兩步可以到達的地方。

接下來，我們回到黑色方塊右手邊的1方塊上，并將它能走的方向也記錄下來，同樣標記為2，因為也是走兩步便可到達的地方。

這樣走一步以及走兩步可以到達的地方都搜索完畢了，下面同理，我們可以迅速把三步的格子給標記出來。

再之后是四步，五步。

我們便成功尋找到了路徑，并且把所有可行的路徑都求出來了。在廣度優(yōu)先搜索中，可以看出是逐步求解的，反復的進入與退出，將當前的所有可行解都記錄下來，然后逐個去查看。在DFS中我們說關鍵點是遞歸以及回溯，在BFS中，關鍵點則是狀態(tài)的選取和標記。

三、例題

（1）題目一：

一位農(nóng)夫在點n上,他要到奶牛所在的點k上,他可以每次從點X到點X-1或點X+1或點2*X,問他到達點k的最短次數(shù).(0 ≤ N ≤ 100,000,0 ≤ K ≤ 100,000)

樣例：

Sample Input

5 17

Sample Output

4

思路：看到這一道題，第一反應就是看看能否找到規(guī)律，然而很顯然它沒有規(guī)律可言，我們需要靠一種近似暴力的方法，而DFS在這里是行不通的,于是只能用BFS來解這道題了。

代碼如下：

#include <iostream>
#include <stdio.h>
#include <cstring>
#include<queue>
#define pp pair<int,int>
using namespace std;
int n,k,ans;
queue<pp>q;
bool v[200004];
void bfs() {
    q.push(pp(n,0));//先將n丟進隊列
    v[n]=1;
    while(!q.empty()) {
        if(q.empty())break;
        pp now=q.front();
        q.pop();
        if(now.first==k) {
            ans=now.second;
            break;
        }
        now.second++;//接下來我們有3種操作,將現(xiàn)在的位置now.second 加1 或 減1 或 乘2
        if(!v[now.first+1]&&now.first<k) {//邊界條件不能少了
            q.push(pp(now.first+1,now.second));
            v[now.first+1]=1;//將已經(jīng)走過的點標記為1,為什么呢??q隊列中到這個數(shù)的次數(shù)是從小到大排序的,now.first+1這個點剛通過now.first被拜訪過,它的此時次數(shù)肯定小于等于下一次拜訪的次數(shù).想一想為什么.
        }
        if(!v[now.first-1]&&now.first-1>=0) {
            q.push(pp(now.first-1,now.second));
            v[now.first-1]=1;
        }
        if(now.first<k&&(!v[now.first*2])) {
            q.push(pp(now.first*2,now.second));
            v[now.first*2]=1;
        }
    }
    return;
}
int main() {
    scanf("%d%d",&n,&k);
    bfs();
    printf("%d\n",ans);
    return 0;
}

（2）題目二：

給你兩個四位數(shù)的質(zhì)數(shù)a,b,讓你通過一個操作使a變成b.這個操作可以使你當前的數(shù)x改變一位上的數(shù)使其變成另一個質(zhì)數(shù),問操作的最小次數(shù)(如果沒有這種方式,輸出Impossible)

注意：沒有前導0!!!;

例如：1033到8179可以從1033->1733->3733->3739->3779->8779->8179

樣例：

Sample Input

3

1033 8179

1373 8017

1033 1033

Sample Output

6

7

0

思路：可以先將10000以內(nèi)所有的質(zhì)數(shù)記錄下來，再進行BFS。

#include<iostream>
#include<stdio.h>
#include<cstring>
#include<queue>
#include<time.h>
#define N 10003
#define pp pair<int,int>
using namespace std;
int T,n,m,ans;
bool v[N],vis[N],t[N];
queue<pp>q;
void pre() {//記錄10000以內(nèi)的質(zhì)數(shù)
    for(int i=2; i<=9999; i++) {
        if(!v[i]) {
            t[i]=1;//t[i]=1表示i是質(zhì)數(shù)
            for(int j=i; j<=9999; j+=i) {
                v[j]=1;
            }
        }
    }
}
void BFS() {
    q.push(pp(n,0));//先將給我們的初始數(shù)加入q隊列
    while(!q.empty()) {
        while(!q.empty()&&vis[q.front().first])q.pop();
        if(q.empty())break;
        pp now=q.front();
        vis[q.front().first]=1;
        q.pop();
        if(now.first==m) {
            ans=now.second;
            break;
        }
        for(int i=1; i<=1000; i*=10) {//枚舉位數(shù)
            int r=now.first-((now.first/i)%10)*i;
            for(int j=0; j<=9; j++) {//枚舉當前位數(shù)更改的值
                if(i==1000&&j==0)continue;//特判前導0的情況!!!
                if(t[r+j*i]&&!vis[r+j*i]) {
                    q.push(pp(r+j*i,now.second+1));//BFS的核心轉(zhuǎn)移代碼
                }
            }
        }
    }
    return;
}
int main() {
    pre();
    scanf("%d",&T);
    while(T--) {
        while(!q.empty())q.pop();
        memset(vis,0,sizeof vis);
        ans=-1;
        scanf("%d%d",&n,&m);
        BFS();
        if(ans==-1)printf("Impossible\n");
        else printf("%d\n",ans);
    }
    return 0;
}