第八章 廣度優(yōu)先搜索

1、第八章 廣度優(yōu)先搜索,廣度優(yōu)先搜索的過程,廣度優(yōu)先搜索算法（又稱寬度優(yōu)先搜索）是最簡便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹算法都采用了和寬度優(yōu)先搜索類似的思想。 廣度優(yōu)先算法的核心思想是：從初始節(jié)點(diǎn)開始，應(yīng)用算符生成第一層節(jié)點(diǎn)，檢查目標(biāo)節(jié)點(diǎn)是否在這些后繼節(jié)點(diǎn)中，若沒有，再用產(chǎn)生式規(guī)則將所有第一層的節(jié)點(diǎn)逐一擴(kuò)展，得到第二層節(jié)點(diǎn)，并逐一檢查第二層節(jié)點(diǎn)

2、中是否包含目標(biāo)節(jié)點(diǎn)。若沒有，再用算符逐一擴(kuò)展第二層的所有節(jié)點(diǎn)……，如此依次擴(kuò)展，檢查下去，直到發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)為止。即 ⒈從圖中的某一頂點(diǎn)V0開始，先訪問V0； ⒉訪問所有與V0相鄰接的頂點(diǎn)V1，V2，......，Vt； ⒊依次訪問與V1，V2，......，Vt相鄰接的所有未曾訪問過的頂點(diǎn)； ⒋循此以往，直至所有的頂點(diǎn)都被訪問過為止。 這種搜索的次序體現(xiàn)沿層次向橫向擴(kuò)

3、展的趨勢，所以稱之為廣度優(yōu)先搜索。,廣度優(yōu)先搜索算法描述：,int bfs(){初始化，初始狀態(tài)存入隊(duì)列；隊(duì)列首指針head=0; 尾指針tail=1；do { 指針head后移一位，指向待擴(kuò)展結(jié)點(diǎn)； for (int i=1;i<=max;++i) //max為產(chǎn)生子結(jié)點(diǎn)的規(guī)則數(shù) { if (子結(jié)點(diǎn)符合條件) {

4、 tail指針增1，把新結(jié)點(diǎn)存入列尾； if (新結(jié)點(diǎn)與原已產(chǎn)生結(jié)點(diǎn)重復(fù)) 刪去該結(jié)點(diǎn)（取消入隊(duì)，tail減1）; else if (新結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)) 輸出并退出； } }}while(head<tail); //隊(duì)列為空},廣度優(yōu)先搜索注意事項(xiàng)：,1、每生成一個(gè)子結(jié)點(diǎn)，就要提供指向它們父

5、親結(jié)點(diǎn)的指針。當(dāng)解出現(xiàn)時(shí)候，通過逆向跟蹤，找到從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的一條路徑。當(dāng)然不要求輸出路徑，就沒必要記父親。 2、生成的結(jié)點(diǎn)要與前面所有已經(jīng)產(chǎn)生結(jié)點(diǎn)比較，以免出現(xiàn)重復(fù)結(jié)點(diǎn)，浪費(fèi)時(shí)間和空間，還有可能陷入死循環(huán)。 3、如果目標(biāo)結(jié)點(diǎn)的深度與“費(fèi)用”（如：路徑長度）成正比，那么，找到的第一個(gè)解即為最優(yōu)解，這時(shí)，搜索速度比深度搜索要快些，在求最優(yōu)解時(shí)往往采用廣度優(yōu)先搜索；如果結(jié)點(diǎn)的“費(fèi)用”不與深度成正比時(shí)，第一

6、次找到的解不一定是最優(yōu)解。 4、廣度優(yōu)先搜索的效率還有賴于目標(biāo)結(jié)點(diǎn)所在位置情況，如果目標(biāo)結(jié)點(diǎn)深度處于較深層時(shí)，需搜索的結(jié)點(diǎn)數(shù)基本上以指數(shù)增長。,下面我們看看怎樣用寬度優(yōu)先搜索來解決八數(shù)碼問題。 例如　圖8-1給出廣度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時(shí)所生成的搜索樹。搜索樹上的所有結(jié)點(diǎn)都標(biāo)記它們所對應(yīng)的狀態(tài)，每個(gè)結(jié)點(diǎn)旁邊的數(shù)字表示結(jié)點(diǎn)擴(kuò)展的順序。粗線條路徑表明求得的一個(gè)解。從圖中可以看出，擴(kuò)展第２６個(gè)結(jié)點(diǎn)，總共生成４

7、６個(gè)結(jié)點(diǎn)之后，才求得這個(gè)解。此外，直接觀察此圖表明，不存在有更短走步序列的解。,【例8.1】圖8-2表示的是從城市A到城市H的交通圖。從圖中可以看出，從城市A到城市H要經(jīng)過若干個(gè)城市?，F(xiàn)要找出一條經(jīng)過城市最少的一條路線。,圖8-2,【算法分析】看到這圖很容易想到用鄰接距陣來表示，0表示能走，1表示不能走。如圖。,首先想到的是用隊(duì)列的思想。a數(shù)組是存儲(chǔ)擴(kuò)展結(jié)點(diǎn)的隊(duì)列，a[i]記錄經(jīng)過的城市,b[i]記錄前趨城市，這樣就可以倒推出最短線路

8、。具體過程如下：（1） 將城市A入隊(duì)，隊(duì)首為0、隊(duì)尾為1。（2）將隊(duì)首所指的城市所有可直通的城市入隊(duì)（如果這個(gè)城市在隊(duì)列中出現(xiàn)過就不入隊(duì)，可用一布爾數(shù)組s[i]來判斷），將入隊(duì)城市的前趨城市保存在b[i]中。然后將隊(duì)首加1，得到新的隊(duì)首城市。重復(fù)以上步驟，直到搜到城市H時(shí)，搜索結(jié)束。利用b[i]可倒推出最少城市線路。,【參考程序】#include#includeusing namespace std;int ju[9][9

9、]={{0,0,0,0,0,0,0,0,0}, {0,1,0,0,0,1,0,1,1}, {0,0,1,1,1,1,0,1,1}, {0,0,1,1,0,0,1,1,1}, {0,0,1,0,1,1,1,0,1}, {0,1,1,0,1,1

10、,1,0,0}, {0,0,0,1,1,1,1,1,0}, {0,1,1,1,0,0,1,1,0}, {0,1,1,1,1,0,0,0,1}};int a[101],b[101];bool s[9]; //初始化int out(int d)

11、 //輸出過程{ cout<<char(a[d]+64); while (b[d]) { d=b[d]; cout<<"--"<<char(a[d]+64); } cout<<endl;},,void doit(){ int head,tail,i; head=0;

12、tail=1; //隊(duì)首為0、隊(duì)尾為1 a[1]=1; //記錄經(jīng)過的城市 b[1]=0; //記錄前趨城市 s[1]=1; //表示該城市已經(jīng)到過 do

13、 //步驟2 { head++; //隊(duì)首加一，出隊(duì) for (i=1;i<=8;i++) //搜索可直通的城市 if ((ju[a[head]][i]==0)&&(s[i]==0)) //判斷城市是否走過 {

14、 tail++; //隊(duì)尾加一，入隊(duì) a[tail]=i; b[tail]=head; s[i]=1; if (i==8) { out(tail);head=tail;break; //第一次搜到H城市時(shí)路線最短 }

15、 } }while (head<tail);}int main() //主程序{ memset(s,false,sizeof(s)); doit(); //進(jìn)行Bfs操作 return 0;},【例8.2】一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細(xì)胞,細(xì)胞的定義為沿細(xì)胞

16、數(shù)字上下左右還是細(xì)胞數(shù)字則為同一細(xì)胞,求給定矩形陣列的細(xì)胞個(gè)數(shù)。如:陣列 4 100234500067103456050020456006710000000089有4個(gè)細(xì)胞?！舅惴ǚ治觥?⑴從文件中讀入m*n矩陣陣列，將其轉(zhuǎn)換為boolean矩陣存入bz數(shù)組中； ⑵沿bz數(shù)組矩陣從上到下，從左到右，找到遇到的第一個(gè)細(xì)胞； ⑶將細(xì)胞的位置入隊(duì)h，并沿其上、下、左、右四個(gè)方向上的細(xì)胞位置入隊(duì)，入隊(duì)后的位

17、置bz數(shù)組置為flase；⑷將h隊(duì)的隊(duì)頭出隊(duì)，沿其上、下、左、右四個(gè)方向上的細(xì)胞位置入隊(duì)，入隊(duì)后的位置bz數(shù)組置為flase； ⑸重復(fù)4，直至h隊(duì)空為止，則此時(shí)找出了一個(gè)細(xì)胞； ⑹重復(fù)2，直至矩陣找不到細(xì)胞； ⑺輸出找到的細(xì)胞數(shù)。,,【參考程序】#includeusing namespace std;int dx[4]={-1,0,1,0}, dy[4]={0,1,0,-1};int bz[100][100

18、],num=0,n,m; void doit(int p,int q){ int x,y,t,w,i; int h[1000][2]; num++;bz[p][q]=0; t=0;w=1;h[1][1]=p;h[1][2]=q; //遇到的第一個(gè)細(xì)胞入隊(duì) do { t++; //隊(duì)頭指針加1

19、 for (i=0;i=0)&&(x=0)&&(y<n)&&(bz[x][y])) //判斷該點(diǎn)是否可以入隊(duì) { w++; h[w][1]=x; h[w][2]=y; bz[x][y]=0; }

20、 //本方向搜索到細(xì)胞就入隊(duì) } }while (t<w); //直至隊(duì)空為止},int main(){ int i,j; char s[100],ch; scanf("%d%d\n",&m,&n); for (i=0; i<=m-1;i++ ) for

21、(j=0;j<=n-1;j++ ) bz[i][j]=1; //初始化 for (i=0;i<=m-1;i++) { gets(s); for (j=0;j<=n-1;j++) if (s[j]=='0') bz[i][j]=0; } for (i=0;i&l

22、t;=m-1;i++) for (j=0;j<=n-1;j++) if (bz[i][j]) doit(i,j); //在矩陣中尋找細(xì)胞 printf("NUMBER of cells=%d",num); return 0;},【例8.3】最短路徑（1995年高中組第4 題）如下圖所示，從入口（1）

23、到出口（17）的可行路線圖中，數(shù)字標(biāo)號(hào)表示關(guān)卡。,現(xiàn)將上面的路線圖，按記錄結(jié)構(gòu)存儲(chǔ)如下圖6：,請?jiān)O(shè)計(jì)一種能從存儲(chǔ)數(shù)據(jù)中求出從入口到出口經(jīng)過最少關(guān)卡路徑的算法。,【算法分析】 該題是一個(gè)路徑搜索問題，根據(jù)圖示，從入口（1）到出口（17）可能有多條途徑，其中最短的路徑只有一條，那么如何找最短路徑呢？根據(jù)題意，用數(shù)組no存儲(chǔ)各關(guān)卡號(hào)，用數(shù)組per存儲(chǔ)訪問到某關(guān)卡號(hào)的前趨關(guān)卡號(hào)。其實(shí)本題是一個(gè)典型的圖的遍歷問題，我們可以采用圖的

24、廣度優(yōu)先遍歷，并利用隊(duì)列的方式存儲(chǔ)頂點(diǎn)之間的聯(lián)系。從入口（1）開始先把它入隊(duì)，然后把（1）的所有關(guān)聯(lián)頂點(diǎn)都入隊(duì)，即訪問一個(gè)頂點(diǎn)，將其后繼頂點(diǎn)入隊(duì)，并存儲(chǔ)它的前趨頂點(diǎn)，……，直到訪問到出口（17）。最后，再從出口的關(guān)卡號(hào)（17）開始回訪它的前趨關(guān)卡號(hào)，……，直到入口的關(guān)卡號(hào)（1），則回訪的搜索路徑便是最短路徑。從列表中可以看出出口關(guān)卡號(hào)（17）的被訪問路徑最短的是： （17）← （16）←（19）←（18）←（1）

25、 由此，我們得到廣度優(yōu)先遍歷求最短路徑的基本方法如下： 假設(shè)用鄰接矩陣存放路線圖（a[i][j]=1表示I與j連通，a[i][j]=0表示i與j不連通）。 再設(shè)一個(gè)隊(duì)列和一個(gè)表示拓展到哪個(gè)頂點(diǎn)的指針變量pos。 （1）從入口開始，先把（1）入隊(duì)，并且根據(jù)鄰接矩陣，把（1）的后繼頂點(diǎn)全部入隊(duì)，并存儲(chǔ)這些后繼頂點(diǎn)的前趨頂點(diǎn)為（1）；再把pos后移一個(gè)，繼續(xù)拓展它，將其后繼頂點(diǎn)入隊(duì)，并存儲(chǔ)它們的前趨頂點(diǎn)，

26、……，直到拓展到出口（目的地（17））；,注意后繼頂點(diǎn)入隊(duì)前，必須要檢查這個(gè)頂點(diǎn)是否已在隊(duì)列中，如果已經(jīng)在了就不要入隊(duì)了；這一步可稱為圖的遍歷或拓展； （2）從隊(duì)列的最后一個(gè)關(guān)卡號(hào)（出口（17））開始，依次回訪它的前驅(qū)頂點(diǎn)，倒推所得到的路徑即為最短路徑。主要是依據(jù)每個(gè)頂點(diǎn)的前趨頂點(diǎn)倒推得到的。實(shí)現(xiàn)如下： i=1 ； while (no[i]!=17) ++i ; do {

27、 cout<<"("<<no[i]<<")"; cout<<" ←"; i=pre[i] ; } while ( I!=0)；【參考程序】留給同學(xué)們完成，文件名ex8_3.cpp。,【例8.4】迷宮問題 如下圖所示，給出一個(gè)N*M的迷宮圖和一個(gè)

28、入口、一個(gè)出口。 編一個(gè)程序，打印一條從迷宮入口到出口的路徑。這里黑色方塊的單元表示走不通（用-1表示），白色方塊的單元表示可以走（用0表示）。只能往上、下、左、右四個(gè)方向走。如果無路則輸出“no way.”。,,【算法分析】　　只要輸出一條路徑即可，所以是一個(gè)經(jīng)典的回溯算法問題，本例給出了回溯（深搜）程序和廣搜程序。實(shí)現(xiàn)見參考程序。,【深搜參考程序】#include using namespace std;int

29、 n,m,desx,desy,soux,souy,totstep,a[51],b[51],map[51][51];bool f;int move(int x, int y,int step){ map[x][y]=step; //走一步，作標(biāo)記，把步數(shù)記下來 a[step]=x; b[step]=y; //記路徑 if

30、((x==desx)&&(y==desy)) { f=1; totstep=step; } else { if ((y!=m)&&(map[x][y+1]==0)) move(x,y+1,step+1); //向右 if ((!f)&&(x!=n)&&(map[x+1][y]==0)) move(x+

31、1,y,step+1); //往下 if ((!f)&&(y!=1)&&(map[x][y-1]==0)) move(x,y-1,step+1); //往左 if ((!f)&&(x!=1)&&(map[x-1][y]==0)) move(x-1,y,step+1); //往上 }},int main(){ int i,j;

32、 cin>>n>>m; //n行m列的迷宮 for (i=1;i>map[i][j]; cout>soux>>souy; //入口 cout>desx>>desy; //出口 f=0;

33、 //f=0表示無解；f=1表示找到了一個(gè)解 move(soux,souy,1); if (f) { for (i=1;i<=totstep;i++) //輸出直迷宮的路徑 cout<<a[i]<<","<<b[i]<<endl

34、; }else cout<<"no way."<<endl;return 0;},【廣搜參考程序】#include using namespace std;int u[5]={0,0,1,0,-1}, w[5]={0,1,0,-1,0};int n,m,i,j,desx,desy,soux,souy,head,tail,x,y,a[51],b[51],pre[51]

35、,map[51][51];bool f;int print(int d){ if (pre[d]!=0) print (pre[d]); //遞歸輸出路徑 cout>n>>m; //n行m列的迷宮 for (i=1;i>map[i][j]; cout>soux>>souy;

36、 //入口 cout>desx>>desy; //出口 head=0; tail=1;,f=0; map[soux][souy]=-1; a[tail]=soux; b[tail]=souy; pre[tail]=0; while (head!=tail)

37、 //隊(duì)列不為空 { head++; for (i=1;i0)&&(x0)&&(y<=m)&&(map[x][y]==0)) { //本方向上可以走 tail++; a[tail]=x; b[tail

38、]=y; pre[tail]=head; map[x][y]=-1; if ((x==desx)&&(y==desy)) //擴(kuò)展出的結(jié)點(diǎn)為目標(biāo)結(jié)點(diǎn) { f=1; print(tail); break; } } } if (f) break; } if

39、(!f) cout<<"no way."<<endl; return 0;},【上機(jī)練習(xí)】,1、面積（area）編程計(jì)算由“*”號(hào)圍成的下列圖形的面積。面積計(jì)算方法是統(tǒng)計(jì)*號(hào)所圍成的閉合曲線中水平線和垂直線交點(diǎn)的數(shù)目。如下圖所示，在10*10的二維數(shù)組中，有“*”圍住了15個(gè)點(diǎn)，因此面積為15。0 0 0 0 0 0 0 0 0 00 0 0 0 * *

40、 * 0 0 00 0 0 0 * 0 0 * 0 00 0 0 0 0 * 0 0 * 00 0 * 0 0 0 * 0 * 00 * 0 * 0 * 0 0 * 00 * 0 0 * * 0 * * 00 0 * 0 0 0 0 * 0 00 0 0 * * * * * 0 00 0

41、 0 0 0 0 0 0 0 0,【樣例輸入】area.in0 0 0 0 0 0 0 0 0 00 0 0 0 1 1 1 0 0 00 0 0 0 1 0 0 1 0 00 0 0 0 0 1 0 0 1 00 0 1 0 0 0 1 0 1 00 1 0 1 0 1 0 0 1 00 1 0 0 1 1 0 1 1 00 0 1 0 0 0 0 1 0 00 0 0 1 1 1 1 1 0 00

42、 0 0 0 0 0 0 0 0 0,【樣例輸出】area.out 15,,2、營救【問題描述】 鐵塔尼號(hào)遇險(xiǎn)了！他發(fā)出了求救信號(hào)。距離最近的哥倫比亞號(hào)收到了訊息，時(shí)間就是生命，必須盡快趕到那里。 通過偵測，哥倫比亞號(hào)獲取了一張海洋圖。這張圖將海洋部分分化成n*n個(gè)比較小的單位，其中用1標(biāo)明的是陸地，用0標(biāo)明是海洋。船只能從一個(gè)格子，移到相鄰的四個(gè)格子。 為了盡快趕到出事地點(diǎn)，哥倫

43、比亞號(hào)最少需要走多遠(yuǎn)的距離?！据斎敫袷健康谝恍袨閚,下面是一個(gè)n*n的0、1矩陣，表示海洋地圖最后一行為四個(gè)小于n的整數(shù)，分別表示哥倫比亞號(hào)和鐵塔尼號(hào)的位置?！据敵龈袷健扛鐐惐葋喬?hào)到鐵塔尼號(hào)的最短距離，答案精確到整數(shù)?！据斎霕永縮ave.in30011011001 1 3 3【數(shù)據(jù)范圍】N<=1000,【輸出樣例】save.out4,3、最少轉(zhuǎn)彎問題（TURN）【問題描述】 給出一張

44、地圖，這張地圖被分為n×m（n,m<=100）個(gè)方塊，任何一個(gè)方塊不是平地就是高山。平地可以通過，高山則不能。現(xiàn)在你處在地圖的（x1,y1）這塊平地，問：你至少需要拐幾個(gè)彎才能到達(dá)目的地（x2,y2）？你只能沿著水平和垂直方向的平地上行進(jìn)，拐彎次數(shù)就等于行進(jìn)方向的改變（從水平到垂直或從垂直到水平）的次數(shù)。例如：如圖，最少的拐彎次數(shù)為5。,【輸入格式】第1行：n m第2至n+1行：整個(gè)地圖地形描述（0：空地；1：高

45、山），如（圖）第2行地形描述為：1 0 0 0 0 1 0 第3行地形描述為：0 0 1 0 1 0 0 ……第n+2行：x1 y1 x2 y2 （分別為起點(diǎn)、終點(diǎn)坐標(biāo)）【輸出格式】s （即最少的拐彎次數(shù)）【輸入輸出樣例】（見圖）：,4.麻將游戲【題目描述】在一種"麻將"游戲中，游戲是在一個(gè)有W＊H格子的矩形平板上進(jìn)行的。每個(gè)格子可以放

46、置一個(gè)麻將牌，也可以不放（如圖所示）。玩家的目標(biāo)是將平板上的所有可通過一條路徑相連的兩張相同的麻將牌，從平板上移去。最后如果能將所有牌移出平板，則算過關(guān)。 　　這個(gè)游戲中的一個(gè)關(guān)鍵問題是：兩張牌之間是否可以被一條路徑所連接，該路徑滿足以下兩個(gè)特性： 　　1. 它由若干條線段組成，每條線段要么是水平方向，要么是垂直方向。 　　2. 這條路徑不能橫穿任何一個(gè)麻將牌 (但允許路徑暫時(shí)離開平板)。 　　這是一個(gè)例子： 在（1，

47、3）的牌和在(4, 4)的牌可以被連接。(2, 3)和(3, 4)不能被連接。 你的任務(wù)是編一個(gè)程序，檢測兩張牌是否能被一條符合以上規(guī)定的路徑所連接。,【輸入】第一行有兩個(gè)整數(shù)w，h （1<=w，h<=75），表示平板的寬和高。接下來h行描述平板信息，每行包含w個(gè)字符，如果某格子有一張牌，則這個(gè)格子上有個(gè)'X'，否則是一個(gè)空格。平板上最左上角格子的坐標(biāo)為（1，1），最右下角格子的坐標(biāo)為（w,h）。接下

48、來的若干行，每行有四個(gè)數(shù)x1， y1， x2， y2 ，且滿足1<=x1,x2<=w，1<=y1,y2<=h，表示兩張牌的坐標(biāo)（這兩張牌的坐標(biāo)總是不同的）。如果出現(xiàn)連續(xù)四個(gè)0，則表示輸入結(jié)束?！据敵觥繉τ诿恳粚ε戚敵稣家恍校瑸檫B接這一對牌的路徑最少包含的線段數(shù)。如果不存在路徑則輸出0?！据斎霕永?【輸出樣例】 5 4 4 XXXXX