廣度優(yōu)先搜索課件

第八章廣度優(yōu)先搜索第八章廣度優(yōu)先搜索廣度優(yōu)先搜索的過(guò)程

廣度優(yōu)先搜索算法（又稱(chēng)寬度優(yōu)先搜索）是最簡(jiǎn)便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹(shù)算法都采用了和寬度優(yōu)先搜索類(lèi)似的思想。廣度優(yōu)先算法的核心思想是：從初始節(jié)點(diǎn)開(kāi)始，應(yīng)用算符生成第一層節(jié)點(diǎn)，檢查目標(biāo)節(jié)點(diǎn)是否在這些后繼節(jié)點(diǎn)中，若沒(méi)有，再用產(chǎn)生式規(guī)則將所有第一層的節(jié)點(diǎn)逐一擴(kuò)展，得到第二層節(jié)點(diǎn)，并逐一檢查第二層節(jié)點(diǎn)中是否包含目標(biāo)節(jié)點(diǎn)。若沒(méi)有，再用算符逐一擴(kuò)展第二層的所有節(jié)點(diǎn)……，如此依次擴(kuò)展，檢查下去，直到發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)為止。即⒈從圖中的某一頂點(diǎn)V0開(kāi)始，先訪(fǎng)問(wèn)V0；⒉訪(fǎng)問(wèn)所有與V0相鄰接的頂點(diǎn)V1，V2，......，Vt；⒊依次訪(fǎng)問(wèn)與V1，V2，......，Vt相鄰接的所有未曾訪(fǎng)問(wèn)過(guò)的頂點(diǎn)；⒋循此以往，直至所有的頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)為止。這種搜索的次序體現(xiàn)沿層次向橫向擴(kuò)展的趨勢(shì)，所以稱(chēng)之為廣度優(yōu)先搜索。廣度優(yōu)先搜索的過(guò)程廣度優(yōu)先搜索算法（又稱(chēng)寬廣度優(yōu)先搜索算法描述：intbfs(){初始化，初始狀態(tài)存入隊(duì)列；隊(duì)列首指針head=0;尾指針tail=1；do{

指針head后移一位，指向待擴(kuò)展結(jié)點(diǎn)；

for(inti=1;i<=max;++i)//max為產(chǎn)生子結(jié)點(diǎn)的規(guī)則數(shù)

{if(子結(jié)點(diǎn)符合條件){tail指針增1，把新結(jié)點(diǎn)存入列尾；

if(新結(jié)點(diǎn)與原已產(chǎn)生結(jié)點(diǎn)重復(fù))刪去該結(jié)點(diǎn)（取消入隊(duì)，tail減1）;elseif(新結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn))輸出并退出；

}}}while(head<tail);//隊(duì)列為空}廣度優(yōu)先搜索算法描述：intbfs()廣度優(yōu)先搜索注意事項(xiàng)：1、每生成一個(gè)子結(jié)點(diǎn)，就要提供指向它們父親結(jié)點(diǎn)的指針。當(dāng)解出現(xiàn)時(shí)候，通過(guò)逆向跟蹤，找到從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的一條路徑。當(dāng)然不要求輸出路徑，就沒(méi)必要記父親。

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)用”（如：路徑長(zhǎng)度）成正比，那么，找到的第一個(gè)解即為最優(yōu)解，這時(shí)，搜索速度比深度搜索要快些，在求最優(yōu)解時(shí)往往采用廣度優(yōu)先搜索；如果結(jié)點(diǎn)的“費(fèi)用”不與深度成正比時(shí)，第一次找到的解不一定是最優(yōu)解。

4、廣度優(yōu)先搜索的效率還有賴(lài)于目標(biāo)結(jié)點(diǎn)所在位置情況，如果目標(biāo)結(jié)點(diǎn)深度處于較深層時(shí)，需搜索的結(jié)點(diǎn)數(shù)基本上以指數(shù)增長(zhǎng)。

下面我們看看怎樣用寬度優(yōu)先搜索來(lái)解決八數(shù)碼問(wèn)題。例如圖8-1給出廣度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時(shí)所生成的搜索樹(shù)。搜索樹(shù)上的所有結(jié)點(diǎn)都標(biāo)記它們所對(duì)應(yīng)的狀態(tài)，每個(gè)結(jié)點(diǎn)旁邊的數(shù)字表示結(jié)點(diǎn)擴(kuò)展的順序。粗線(xiàn)條路徑表明求得的一個(gè)解。從圖中可以看出，擴(kuò)展第２６個(gè)結(jié)點(diǎn)，總共生成４６個(gè)結(jié)點(diǎn)之后，才求得這個(gè)解。此外，直接觀(guān)察此圖表明，不存在有更短走步序列的解。廣度優(yōu)先搜索注意事項(xiàng)：1、每生成一個(gè)子結(jié)點(diǎn)，廣度優(yōu)先搜索課件【例8.1】圖8-2表示的是從城市A到城市H的交通圖。從圖中可以看出，從城市A到城市H要經(jīng)過(guò)若干個(gè)城市。現(xiàn)要找出一條經(jīng)過(guò)城市最少的一條路線(xiàn)。圖8-2【例8.1】圖8-2表示的是從城市A到城市H的交通圖。從圖中【算法分析】看到這圖很容易想到用鄰接距陣來(lái)表示，0表示能走，1表示不能走。如圖。

首先想到的是用隊(duì)列的思想。a數(shù)組是存儲(chǔ)擴(kuò)展結(jié)點(diǎn)的隊(duì)列，a[i]記錄經(jīng)過(guò)的城市,b[i]記錄前趨城市，這樣就可以倒推出最短線(xiàn)路。具體過(guò)程如下：（1）將城市A入隊(duì)，隊(duì)首為0、隊(duì)尾為1。（2）將隊(duì)首所指的城市所有可直通的城市入隊(duì)（如果這個(gè)城市在隊(duì)列中出現(xiàn)過(guò)就不入隊(duì)，可用一布爾數(shù)組s[i]來(lái)判斷），將入隊(duì)城市的前趨城市保存在b[i]中。然后將隊(duì)首加1，得到新的隊(duì)首城市。重復(fù)以上步驟，直到搜到城市H時(shí)，搜索結(jié)束。利用b[i]可倒推出最少城市線(xiàn)路?！舅惴ǚ治觥渴紫认氲降氖怯藐?duì)列的思想。a數(shù)組是【參考程序】#include<iostream>#include<cstring>usingnamespacestd;intju[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,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}};inta[101],b[101];bools[9];//初始化intout(intd)//輸出過(guò)程{cout<<char(a[d]+64);while(b[d]){d=b[d];cout<<"--"<<char(a[d]+64);}cout<<endl;}【參考程序】voiddoit(){inthead,tail,i;head=0;tail=1;//隊(duì)首為0、隊(duì)尾為1a[1]=1;//記錄經(jīng)過(guò)的城市

b[1]=0;//記錄前趨城市

s[1]=1;//表示該城市已經(jīng)到過(guò)

do//步驟2{head++;//隊(duì)首加一，出隊(duì)

for(i=1;i<=8;i++)//搜索可直通的城市

if((ju[a[head]][i]==0)&&(s[i]==0))//判斷城市是否走過(guò)

{tail++;//隊(duì)尾加一，入隊(duì)

a[tail]=i;

b[tail]=head;s[i]=1;if(i==8){out(tail);head=tail;break;//第一次搜到H城市時(shí)路線(xiàn)最短

}}}while(head<tail);}intmain()//主程序{memset(s,false,sizeof(s));doit();//進(jìn)行Bfs操作

return0;}voiddoit()【例8.2】一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細(xì)胞,細(xì)胞的定義為沿細(xì)胞數(shù)字上下左右還是細(xì)胞數(shù)字則為同一細(xì)胞,求給定矩形陣列的細(xì)胞個(gè)數(shù)。如:陣列4100234500067103456050020456006710000000089有4個(gè)細(xì)胞?！舅惴ǚ治觥竣艔奈募凶x入m*n矩陣陣列，將其轉(zhuǎn)換為boolean矩陣存入bz數(shù)組中；

⑵沿bz數(shù)組矩陣從上到下，從左到右，找到遇到的第一個(gè)細(xì)胞；

⑶將細(xì)胞的位置入隊(duì)h，并沿其上、下、左、右四個(gè)方向上的細(xì)胞位置入隊(duì)，入隊(duì)后的位置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ù)。

【例8.2】一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細(xì)胞,【參考程序】#include<cstdio>usingnamespacestd;intdx[4]={-1,0,1,0},

dy[4]={0,1,0,-1};intbz[100][100],num=0,n,m;voiddoit(intp,intq){intx,y,t,w,i;inth[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ì)頭指針加1for(i=0;i<=3;i++)//沿細(xì)胞的上下左右四個(gè)方向搜索細(xì)胞

{x=h[t][1]+dx[i];y=h[t][2]+dy[i];

if((x>=0)&&(x<m)&&(y>=0)&&(y<n)&&(bz[x][y]))//判斷該點(diǎn)是否可以入隊(duì)

{w++;h[w][1]=x;h[w][2]=y;bz[x][y]=0;

}//本方向搜索到細(xì)胞就入隊(duì)

}}while(t<w);//直至隊(duì)空為止}【參考程序】intmain(){inti,j;chars[100],ch;scanf("%d%d\n",&m,&n);

for(i=0;i<=m-1;i++)for(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<=m-1;i++)for(j=0;j<=n-1;j++)if(bz[i][j])doit(i,j);//在矩陣中尋找細(xì)胞

printf("NUMBERofcells=%d",num);return0;}intmain()【例8.3】最短路徑（1995年高中組第4題）如下圖所示，從入口（1）到出口（17）的可行路線(xiàn)圖中，數(shù)字標(biāo)號(hào)表示關(guān)卡?，F(xiàn)將上面的路線(xiàn)圖，按記錄結(jié)構(gòu)存儲(chǔ)如下圖6：請(qǐng)?jiān)O(shè)計(jì)一種能從存儲(chǔ)數(shù)據(jù)中求出從入口到出口經(jīng)過(guò)最少關(guān)卡路徑的算法。【例8.3】最短路徑（1995年高中組第4題）現(xiàn)將上面的路【算法分析】

該題是一個(gè)路徑搜索問(wèn)題，根據(jù)圖示，從入口（1）到出口（17）可能有多條途徑，其中最短的路徑只有一條，那么如何找最短路徑呢？根據(jù)題意，用數(shù)組no存儲(chǔ)各關(guān)卡號(hào)，用數(shù)組per存儲(chǔ)訪(fǎng)問(wèn)到某關(guān)卡號(hào)的前趨關(guān)卡號(hào)。其實(shí)本題是一個(gè)典型的圖的遍歷問(wèn)題，我們可以采用圖的廣度優(yōu)先遍歷，并利用隊(duì)列的方式存儲(chǔ)頂點(diǎn)之間的聯(lián)系。從入口（1）開(kāi)始先把它入隊(duì)，然后把（1）的所有關(guān)聯(lián)頂點(diǎn)都入隊(duì)，即訪(fǎng)問(wèn)一個(gè)頂點(diǎn)，將其后繼頂點(diǎn)入隊(duì)，并存儲(chǔ)它的前趨頂點(diǎn)，……，直到訪(fǎng)問(wèn)到出口（17）。最后，再?gòu)某隹诘年P(guān)卡號(hào)（17）開(kāi)始回訪(fǎng)它的前趨關(guān)卡號(hào)，……，直到入口的關(guān)卡號(hào)（1），則回訪(fǎng)的搜索路徑便是最短路徑。從列表中可以看出出口關(guān)卡號(hào)（17）的被訪(fǎng)問(wèn)路徑最短的是：（17）←（16）←（19）←（18）←（1）由此，我們得到廣度優(yōu)先遍歷求最短路徑的基本方法如下：假設(shè)用鄰接矩陣存放路線(xiàn)圖（a[i][j]=1表示I與j連通，a[i][j]=0表示i與j不連通）。再設(shè)一個(gè)隊(duì)列和一個(gè)表示拓展到哪個(gè)頂點(diǎn)的指針變量pos。（1）從入口開(kāi)始，先把（1）入隊(duì)，并且根據(jù)鄰接矩陣，把（1）的后繼頂點(diǎn)全部入隊(duì)，并存儲(chǔ)這些后繼頂點(diǎn)的前趨頂點(diǎn)為（1）；再把pos后移一個(gè)，繼續(xù)拓展它，將其后繼頂點(diǎn)入隊(duì)，并存儲(chǔ)它們的前趨頂點(diǎn)，……，直到拓展到出口（目的地（17））；

【算法分析】

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

i=1；

while(no[i]!=17)++i;do{cout<<"("<<no[i]<<")";

cout<<"←";i=pre[i];}while(I!=0)；【參考程序】留給同學(xué)們完成，文件名ex8_3.cpp。注意后繼頂點(diǎn)入隊(duì)前，必須要檢查這個(gè)頂點(diǎn)是否已【例8.4】迷宮問(wèn)題如下圖所示，給出一個(gè)N*M的迷宮圖和一個(gè)入口、一個(gè)出口。編一個(gè)程序，打印一條從迷宮入口到出口的路徑。這里黑色方塊的單元表示走不通（用-1表示），白色方塊的單元表示可以走（用0表示）。只能往上、下、左、右四個(gè)方向走。如果無(wú)路則輸出“noway.”。入口→0-1000000-10000-1000-1-100000-1-1-100-1-100000→出口0000000-1-1【算法分析】只要輸出一條路徑即可，所以是一個(gè)經(jīng)典的回溯算法問(wèn)題，本例給出了回溯（深搜）程序和廣搜程序。實(shí)現(xiàn)見(jiàn)參考程序?！纠?.4】迷宮問(wèn)題入口→0-1000000-10000-1【深搜參考程序】#include<iostream>usingnamespacestd;intn,m,desx,desy,soux,souy,totstep,a[51],b[51],map[51][51];boolf;intmove(intx,inty,intstep){map[x][y]=step;//走一步，作標(biāo)記，把步數(shù)記下來(lái)

a[step]=x;b[step]=y;//記路徑

if((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+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);//往上

}}【深搜參考程序】intmain(){inti,j;cin>>n>>m;//n行m列的迷宮

for(i=1;i<=n;i++)//讀入迷宮，0表示通，-1表示不通

for(j=1;j<=m;j++)cin>>map[i][j];

cout<<"inputtheenter:";cin>>soux>>souy;//入口

cout<<"inputtheexit:";cin>>desx>>desy;//出口

f=0;//f=0表示無(wú)解；f=1表示找到了一個(gè)解

move(soux,souy,1);if(f){for(i=1;i<=totstep;i++)//輸出直迷宮的路徑

cout<<a[i]<<","<<b[i]<<endl;}elsecout<<"noway."<<endl;return0;}intmain()【廣搜參考程序】#include<iostream>usingnamespacestd;intu[5]={0,0,1,0,-1},w[5]={0,1,0,-1,0};intn,m,i,j,desx,desy,soux,souy,head,tail,x,y,a[51],b[51],pre[51],map[51][51];boolf;intprint(intd){if(pre[d]!=0)print(pre[d]);//遞歸輸出路徑

cout<<a[d]<<","<<b[d]<<endl;}intmain(){inti,j;cin>>n>>m;//n行m列的迷宮

for(i=1;i<=n;i++)//讀入迷宮，0表示通，-1表示不通

for(j=1;j<=m;j++)cin>>map[i][j];

cout<<"inputtheenter:";cin>>soux>>souy;//入口

cout<<"inputtheexit:";cin>>desx>>desy;//出口

head=0;

tail=1;【廣搜參考程序】

f=0;map[soux][souy]=-1;a[tail]=soux;b[tail]=souy;pre[tail]=0;while(head!=tail)//隊(duì)列不為空

{head++;for(i=1;i<=4;i++)//4個(gè)方向

{x=a[head]+u[i];y=b[head]+w[i];

if((x>0)&&(x<=n)&&(y>0)&&(y<=m)&&(map[x][y]==0)){//本方向上可以走

tail++;a[tail]=x;b[tail]=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(!f)cout<<"noway."<<endl;return0;}

f=0;輸入1：輸出1：輸入2：輸出2：85-1-1-1-1-10000-1-1-1-10-1-1000-1-100-1-1-1000-1-1-1-10-1-1000-121842,12,22,32,43,44,44,35,36,385-1-1-1-1-10000-1-1-1-10-1-1000-1-100-1-1-1000-1-1-1-1-1-1-1000-12184noway.輸入1：輸出1：輸入2：輸出2：852,185now【上機(jī)練習(xí)】1、面積（area）編程計(jì)算由“*”號(hào)圍成的下列圖形的面積。面積計(jì)算方法是統(tǒng)計(jì)*號(hào)所圍成的閉合曲線(xiàn)中水平線(xiàn)和垂直線(xiàn)交點(diǎn)的數(shù)目。如下圖所示，在10*10的二維數(shù)組中，有“*”圍住了15個(gè)點(diǎn)，因此面積為15。00000000000000***0000000*00*0000000*00*000*000*0*00*0*0*00*00*00**0**000*0000*00000*****000000000000【樣例輸入】area.in0000000000000011100000001001000000010010001000101001010100100100110110001000010000011111000000000000【樣例輸出】area.out15【上機(jī)練習(xí)】1、面積（area）【樣例輸入】area.in【2、營(yíng)救【問(wèn)題描述】

鐵塔尼號(hào)遇險(xiǎn)了！他發(fā)出了求救信號(hào)。距離最近的哥倫比亞號(hào)收到了訊息，時(shí)間就是生命，必須盡快趕到那里。通過(guò)偵測(cè)，哥倫比亞號(hào)獲取了一張海洋圖。這張圖將海洋部分分化成n*n個(gè)比較小的單位，其中用1標(biāo)明的是陸地，用0標(biāo)明是海洋。船只能從一個(gè)格子，移到相鄰的四個(gè)格子。為了盡快趕到出事地點(diǎn)，哥倫比亞號(hào)最少需要走多遠(yuǎn)的距離。【輸入格式】第一行為n,下面是一個(gè)n*n的0、1矩陣，表示海洋地圖最后一行為四個(gè)小于n的整數(shù)，分別表示哥倫比亞號(hào)和鐵塔尼號(hào)的位置?！据敵龈袷健扛鐐惐葋喬?hào)到鐵塔尼號(hào)的最短距離，答案精確到整數(shù)?！据斎霕永縮ave.in30011011001133【數(shù)據(jù)范圍】N<=1000【輸出樣例】save.out42、營(yíng)救【輸出樣例】save.out3、最少轉(zhuǎn)彎問(wèn)題（TURN）【問(wèn)題描述】

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

第3行地形描述為：0010100……第n+2行：x1y1x2y2（分別為起點(diǎn)、終點(diǎn)坐標(biāo)）【輸出格式】s（即最少的拐彎次數(shù)）【輸入輸出樣例】（見(jiàn)圖）：TURN.INTURN.OUT571000010001010000001010110000000011013175【輸入格式】TURN.INTURN.OUT5754.麻將游戲【題目描述】

在一種"麻將"游戲中，游戲是在一個(gè)有W＊H格子的矩形平板上進(jìn)行的。每個(gè)格子可以放置一個(gè)麻將牌，也可以不放（如圖所示）。玩家的目標(biāo)是將平板上的所有可通過(guò)一條路徑相連的兩張相同的麻將牌，從平板上移去。最后如果能將所有牌移出平板，則算過(guò)關(guān)。

這個(gè)游戲中的一個(gè)關(guān)鍵問(wèn)題是：兩張牌之間是否可以被一條路徑所連接，該路徑滿(mǎn)足以下兩個(gè)特性：

1.

它由若干條線(xiàn)段組成，每條線(xiàn)段要么是水平方向，要么是垂直方向。

2.這條路徑不能橫穿任何一個(gè)麻將牌(但允許路徑暫時(shí)離開(kāi)平板)。

這是一個(gè)例子：

在（1，3）的牌和在(4,4)的牌可以被連接。(2,

3)和(3,4)不能被連接。

你的任務(wù)是編一個(gè)程序，檢測(cè)兩張牌是否能被一條符合以上規(guī)定的路徑所連接。

4.麻將游戲【輸入】

第一行有兩個(gè)整數(shù)w，h

（1<=w，h<=75），表示平板的寬和高。接下來(lái)h行描述平板信息，每行包含w個(gè)字符，如果某格子有一張牌，則這個(gè)格子上有個(gè)'X'，否則是一個(gè)空格。平板上最左上角格子的坐標(biāo)為（1，1），最右下角格子的坐標(biāo)為（w,h）。接下來(lái)的若干行，每行有四個(gè)數(shù)x1，

y1，x2，y2

，且滿(mǎn)足1<=x1,x2<=w，1<=y1,y2<=h，表示兩張牌的坐標(biāo)（這兩張牌的坐標(biāo)總是不同的）。如果出現(xiàn)連續(xù)四個(gè)0，則表示輸入結(jié)束。

【輸出】

對(duì)于每一對(duì)牌輸出占一行，為連接這一對(duì)牌的路徑最少包含的線(xiàn)段數(shù)。如果不存在路徑則輸出0。

【輸入樣例】【輸出樣例】

544

XXXXX3

XX0

XXX

X

XXX

2353

1344

2334

0000

【輸入】

第一行有兩個(gè)整數(shù)w，h

（1<=w，h<=75）第八章廣度優(yōu)先搜索第八章廣度優(yōu)先搜索廣度優(yōu)先搜索的過(guò)程

廣度優(yōu)先搜索算法（又稱(chēng)寬度優(yōu)先搜索）是最簡(jiǎn)便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹(shù)算法都采用了和寬度優(yōu)先搜索類(lèi)似的思想。廣度優(yōu)先算法的核心思想是：從初始節(jié)點(diǎn)開(kāi)始，應(yīng)用算符生成第一層節(jié)點(diǎn)，檢查目標(biāo)節(jié)點(diǎn)是否在這些后繼節(jié)點(diǎn)中，若沒(méi)有，再用產(chǎn)生式規(guī)則將所有第一層的節(jié)點(diǎn)逐一擴(kuò)展，得到第二層節(jié)點(diǎn)，并逐一檢查第二層節(jié)點(diǎn)中是否包含目標(biāo)節(jié)點(diǎn)。若沒(méi)有，再用算符逐一擴(kuò)展第二層的所有節(jié)點(diǎn)……，如此依次擴(kuò)展，檢查下去，直到發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)為止。即⒈從圖中的某一頂點(diǎn)V0開(kāi)始，先訪(fǎng)問(wèn)V0；⒉訪(fǎng)問(wèn)所有與V0相鄰接的頂點(diǎn)V1，V2，......，Vt；⒊依次訪(fǎng)問(wèn)與V1，V2，......，Vt相鄰接的所有未曾訪(fǎng)問(wèn)過(guò)的頂點(diǎn)；⒋循此以往，直至所有的頂點(diǎn)都被訪(fǎng)問(wèn)過(guò)為止。這種搜索的次序體現(xiàn)沿層次向橫向擴(kuò)展的趨勢(shì)，所以稱(chēng)之為廣度優(yōu)先搜索。廣度優(yōu)先搜索的過(guò)程廣度優(yōu)先搜索算法（又稱(chēng)寬廣度優(yōu)先搜索算法描述：intbfs(){初始化，初始狀態(tài)存入隊(duì)列；隊(duì)列首指針head=0;尾指針tail=1；do{

指針head后移一位，指向待擴(kuò)展結(jié)點(diǎn)；

for(inti=1;i<=max;++i)//max為產(chǎn)生子結(jié)點(diǎn)的規(guī)則數(shù)

{if(子結(jié)點(diǎn)符合條件){tail指針增1，把新結(jié)點(diǎn)存入列尾；

if(新結(jié)點(diǎn)與原已產(chǎn)生結(jié)點(diǎn)重復(fù))刪去該結(jié)點(diǎn)（取消入隊(duì)，tail減1）;elseif(新結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn))輸出并退出；

}}}while(head<tail);//隊(duì)列為空}廣度優(yōu)先搜索算法描述：intbfs()廣度優(yōu)先搜索注意事項(xiàng)：1、每生成一個(gè)子結(jié)點(diǎn)，就要提供指向它們父親結(jié)點(diǎn)的指針。當(dāng)解出現(xiàn)時(shí)候，通過(guò)逆向跟蹤，找到從根結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的一條路徑。當(dāng)然不要求輸出路徑，就沒(méi)必要記父親。

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)用”（如：路徑長(zhǎng)度）成正比，那么，找到的第一個(gè)解即為最優(yōu)解，這時(shí)，搜索速度比深度搜索要快些，在求最優(yōu)解時(shí)往往采用廣度優(yōu)先搜索；如果結(jié)點(diǎn)的“費(fèi)用”不與深度成正比時(shí)，第一次找到的解不一定是最優(yōu)解。

4、廣度優(yōu)先搜索的效率還有賴(lài)于目標(biāo)結(jié)點(diǎn)所在位置情況，如果目標(biāo)結(jié)點(diǎn)深度處于較深層時(shí)，需搜索的結(jié)點(diǎn)數(shù)基本上以指數(shù)增長(zhǎng)。

下面我們看看怎樣用寬度優(yōu)先搜索來(lái)解決八數(shù)碼問(wèn)題。例如圖8-1給出廣度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時(shí)所生成的搜索樹(shù)。搜索樹(shù)上的所有結(jié)點(diǎn)都標(biāo)記它們所對(duì)應(yīng)的狀態(tài)，每個(gè)結(jié)點(diǎn)旁邊的數(shù)字表示結(jié)點(diǎn)擴(kuò)展的順序。粗線(xiàn)條路徑表明求得的一個(gè)解。從圖中可以看出，擴(kuò)展第２６個(gè)結(jié)點(diǎn)，總共生成４６個(gè)結(jié)點(diǎn)之后，才求得這個(gè)解。此外，直接觀(guān)察此圖表明，不存在有更短走步序列的解。廣度優(yōu)先搜索注意事項(xiàng)：1、每生成一個(gè)子結(jié)點(diǎn)，廣度優(yōu)先搜索課件【例8.1】圖8-2表示的是從城市A到城市H的交通圖。從圖中可以看出，從城市A到城市H要經(jīng)過(guò)若干個(gè)城市。現(xiàn)要找出一條經(jīng)過(guò)城市最少的一條路線(xiàn)。圖8-2【例8.1】圖8-2表示的是從城市A到城市H的交通圖。從圖中【算法分析】看到這圖很容易想到用鄰接距陣來(lái)表示，0表示能走，1表示不能走。如圖。

首先想到的是用隊(duì)列的思想。a數(shù)組是存儲(chǔ)擴(kuò)展結(jié)點(diǎn)的隊(duì)列，a[i]記錄經(jīng)過(guò)的城市,b[i]記錄前趨城市，這樣就可以倒推出最短線(xiàn)路。具體過(guò)程如下：（1）將城市A入隊(duì)，隊(duì)首為0、隊(duì)尾為1。（2）將隊(duì)首所指的城市所有可直通的城市入隊(duì)（如果這個(gè)城市在隊(duì)列中出現(xiàn)過(guò)就不入隊(duì)，可用一布爾數(shù)組s[i]來(lái)判斷），將入隊(duì)城市的前趨城市保存在b[i]中。然后將隊(duì)首加1，得到新的隊(duì)首城市。重復(fù)以上步驟，直到搜到城市H時(shí)，搜索結(jié)束。利用b[i]可倒推出最少城市線(xiàn)路?！舅惴ǚ治觥渴紫认氲降氖怯藐?duì)列的思想。a數(shù)組是【參考程序】#include<iostream>#include<cstring>usingnamespacestd;intju[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,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}};inta[101],b[101];bools[9];//初始化intout(intd)//輸出過(guò)程{cout<<char(a[d]+64);while(b[d]){d=b[d];cout<<"--"<<char(a[d]+64);}cout<<endl;}【參考程序】voiddoit(){inthead,tail,i;head=0;tail=1;//隊(duì)首為0、隊(duì)尾為1a[1]=1;//記錄經(jīng)過(guò)的城市

b[1]=0;//記錄前趨城市

s[1]=1;//表示該城市已經(jīng)到過(guò)

do//步驟2{head++;//隊(duì)首加一，出隊(duì)

for(i=1;i<=8;i++)//搜索可直通的城市

if((ju[a[head]][i]==0)&&(s[i]==0))//判斷城市是否走過(guò)

{tail++;//隊(duì)尾加一，入隊(duì)

a[tail]=i;

b[tail]=head;s[i]=1;if(i==8){out(tail);head=tail;break;//第一次搜到H城市時(shí)路線(xiàn)最短

}}}while(head<tail);}intmain()//主程序{memset(s,false,sizeof(s));doit();//進(jìn)行Bfs操作

return0;}voiddoit()【例8.2】一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細(xì)胞,細(xì)胞的定義為沿細(xì)胞數(shù)字上下左右還是細(xì)胞數(shù)字則為同一細(xì)胞,求給定矩形陣列的細(xì)胞個(gè)數(shù)。如:陣列4100234500067103456050020456006710000000089有4個(gè)細(xì)胞?！舅惴ǚ治觥竣艔奈募凶x入m*n矩陣陣列，將其轉(zhuǎn)換為boolean矩陣存入bz數(shù)組中；

⑵沿bz數(shù)組矩陣從上到下，從左到右，找到遇到的第一個(gè)細(xì)胞；

⑶將細(xì)胞的位置入隊(duì)h，并沿其上、下、左、右四個(gè)方向上的細(xì)胞位置入隊(duì)，入隊(duì)后的位置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ù)。

【例8.2】一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細(xì)胞,【參考程序】#include<cstdio>usingnamespacestd;intdx[4]={-1,0,1,0},

dy[4]={0,1,0,-1};intbz[100][100],num=0,n,m;voiddoit(intp,intq){intx,y,t,w,i;inth[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ì)頭指針加1for(i=0;i<=3;i++)//沿細(xì)胞的上下左右四個(gè)方向搜索細(xì)胞

{x=h[t][1]+dx[i];y=h[t][2]+dy[i];

if((x>=0)&&(x<m)&&(y>=0)&&(y<n)&&(bz[x][y]))//判斷該點(diǎn)是否可以入隊(duì)

{w++;h[w][1]=x;h[w][2]=y;bz[x][y]=0;

}//本方向搜索到細(xì)胞就入隊(duì)

}}while(t<w);//直至隊(duì)空為止}【參考程序】intmain(){inti,j;chars[100],ch;scanf("%d%d\n",&m,&n);

for(i=0;i<=m-1;i++)for(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<=m-1;i++)for(j=0;j<=n-1;j++)if(bz[i][j])doit(i,j);//在矩陣中尋找細(xì)胞

printf("NUMBERofcells=%d",num);return0;}intmain()【例8.3】最短路徑（1995年高中組第4題）如下圖所示，從入口（1）到出口（17）的可行路線(xiàn)圖中，數(shù)字標(biāo)號(hào)表示關(guān)卡?，F(xiàn)將上面的路線(xiàn)圖，按記錄結(jié)構(gòu)存儲(chǔ)如下圖6：請(qǐng)?jiān)O(shè)計(jì)一種能從存儲(chǔ)數(shù)據(jù)中求出從入口到出口經(jīng)過(guò)最少關(guān)卡路徑的算法?！纠?.3】最短路徑（1995年高中組第4題）現(xiàn)將上面的路【算法分析】

該題是一個(gè)路徑搜索問(wèn)題，根據(jù)圖示，從入口（1）到出口（17）可能有多條途徑，其中最短的路徑只有一條，那么如何找最短路徑呢？根據(jù)題意，用數(shù)組no存儲(chǔ)各關(guān)卡號(hào)，用數(shù)組per存儲(chǔ)訪(fǎng)問(wèn)到某關(guān)卡號(hào)的前趨關(guān)卡號(hào)。其實(shí)本題是一個(gè)典型的圖的遍歷問(wèn)題，我們可以采用圖的廣度優(yōu)先遍歷，并利用隊(duì)列的方式存儲(chǔ)頂點(diǎn)之間的聯(lián)系。從入口（1）開(kāi)始先把它入隊(duì)，然后把（1）的所有關(guān)聯(lián)頂點(diǎn)都入隊(duì)，即訪(fǎng)問(wèn)一個(gè)頂點(diǎn)，將其后繼頂點(diǎn)入隊(duì)，并存儲(chǔ)它的前趨頂點(diǎn)，……，直到訪(fǎng)問(wèn)到出口（17）。最后，再?gòu)某隹诘年P(guān)卡號(hào)（17）開(kāi)始回訪(fǎng)它的前趨關(guān)卡號(hào)，……，直到入口的關(guān)卡號(hào)（1），則回訪(fǎng)的搜索路徑便是最短路徑。從列表中可以看出出口關(guān)卡號(hào)（17）的被訪(fǎng)問(wèn)路徑最短的是：（17）←（16）←（19）←（18）←（1）由此，我們得到廣度優(yōu)先遍歷求最短路徑的基本方法如下：假設(shè)用鄰接矩陣存放路線(xiàn)圖（a[i][j]=1表示I與j連通，a[i][j]=0表示i與j不連通）。再設(shè)一個(gè)隊(duì)列和一個(gè)表示拓展到哪個(gè)頂點(diǎn)的指針變量pos。（1）從入口開(kāi)始，先把（1）入隊(duì)，并且根據(jù)鄰接矩陣，把（1）的后繼頂點(diǎn)全部入隊(duì)，并存儲(chǔ)這些后繼頂點(diǎn)的前趨頂點(diǎn)為（1）；再把pos后移一個(gè)，繼續(xù)拓展它，將其后繼頂點(diǎn)入隊(duì)，并存儲(chǔ)它們的前趨頂點(diǎn)，……，直到拓展到出口（目的地（17））；

【算法分析】

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

i=1；

while(no[i]!=17)++i;do{cout<<"("<<no[i]<<")";

cout<<"←";i=pre[i];}while(I!=0)；【參考程序】留給同學(xué)們完成，文件名ex8_3.cpp。注意后繼頂點(diǎn)入隊(duì)前，必須要檢查這個(gè)頂點(diǎn)是否已【例8.4】迷宮問(wèn)題如下圖所示，給出一個(gè)N*M的迷宮圖和一個(gè)入口、一個(gè)出口。編一個(gè)程序，打印一條從迷宮入口到出口的路徑。這里黑色方塊的單元表示走不通（用-1表示），白色方塊的單元表示可以走（用0表示）。只能往上、下、左、右四個(gè)方向走。如果無(wú)路則輸出“noway.”。入口→0-1000000-10000-1000-1-100000-1-1-100-1-100000→出口0000000-1-1【算法分析】只要輸出一條路徑即可，所以是一個(gè)經(jīng)典的回溯算法問(wèn)題，本例給出了回溯（深搜）程序和廣搜程序。實(shí)現(xiàn)見(jiàn)參考程序。【例8.4】迷宮問(wèn)題入口→0-1000000-10000-1【深搜參考程序】#include<iostream>usingnamespacestd;intn,m,desx,desy,soux,souy,totstep,a[51],b[51],map[51][51];boolf;intmove(intx,inty,intstep){map[x][y]=step;//走一步，作標(biāo)記，把步數(shù)記下來(lái)

a[step]=x;b[step]=y;//記路徑

if((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+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);//往上

}}【深搜參考程序】intmain(){inti,j;cin>>n>>m;//n行m列的迷宮

for(i=1;i<=n;i++)//讀入迷宮，0表示通，-1表示不通

for(j=1;j<=m;j++)cin>>map[i][j];

cout<<"inputtheenter:";cin>>soux>>souy;//入口

cout<<"inputtheexit:";cin>>desx>>desy;//出口

f=0;//f=0表示無(wú)解；f=1表示找到了一個(gè)解

move(soux,souy,1);if(f){for(i=1;i<=totstep;i++)//輸出直迷宮的路徑

cout<<a[i]<<","<<b[i]<<endl;}elsecout<<"noway."<<endl;return0;}intmain()【廣搜參考程序】#include<iostream>usingnamespacestd;intu[5]={0,0,1,0,-1},w[5]={0,1,0,-1,0};intn,m,i,j,desx,desy,soux,souy,head,tail,x,y,a[51],b[51],pre[51],map[51][51];boolf;intprint(intd){if(pre[d]!=0)print(pre[d]);//遞歸輸出路徑

cout<<a[d]<<","<<b[d]<<endl;}intmain(){inti,j;cin>>n>>m;//n行m列的迷宮

for(i=1;i<=n;i++)//讀入迷宮，0表示通，-1表示不通

for(j=1;j<=m;j++)cin>>map[i][j];

cout<<"inputtheenter:";cin>>soux>>souy;//入口

cout<<"inputtheexit:";cin>>desx>>desy;//出口

head=0;

tail=1;【廣搜參考程序】

f=0;map[soux][souy]=-1;a[tail]=soux;b[tail]=souy;pre[tail]=0;while(head!=tail)//隊(duì)列不為空

{head++;for(i=1;i<=4;i++)//4個(gè)方向

{x=a[head]+u[i];y=b[head]+w[i];

if((x>0)&&(x<=n)&&(y>0)&&(y<=m)&&(map[x][y]==0)){//本方向上可以走

tail++;a[tail]=x;b[tail]=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(!f)cout<<"noway."<<endl;return0;}

f=0;輸入1：輸出1：輸入2：輸出2：85-1-1-1-1-10000-1-1-1-10-1-1000-1-100-1-1-1000-1-1-1-10-1-1000-121842,12,22,32,43,44,44,35,36,385-1-1-1-1-10000-1-1-1-10-1-1000-1-100-1-1-1000-1-1-1-1-1-1-1000-12184noway.輸入1：輸出1：輸入2：輸出2：852,185now【上機(jī)練習(xí)】1、面積（area）編程計(jì)算由“*”號(hào)圍成的下列圖形的面積。面積計(jì)算方法是統(tǒng)計(jì)*號(hào)所圍成的閉合曲線(xiàn)中水平線(xiàn)和垂直線(xiàn)交點(diǎn)的數(shù)目。如下圖所示，在10