廣度優(yōu)先搜索

廣度優(yōu)先搜索第一頁(yè)，共二十四頁(yè)，2022年，8月28日廣度優(yōu)先搜索的過(guò)程

廣度優(yōu)先搜索算法（又稱寬度優(yōu)先搜索）是最簡(jiǎn)便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。Dijkstra單源最短路徑算法和Prim最小生成樹(shù)算法都采用了和寬度優(yōu)先搜索類似的思想。廣度優(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)始，先訪問(wèn)V0；⒉訪問(wèn)所有與V0相鄰接的頂點(diǎn)V1，V2，......，Vt；⒊依次訪問(wèn)與V1，V2，......，Vt相鄰接的所有未曾訪問(wèn)過(guò)的頂點(diǎn)；⒋循此以往，直至所有的頂點(diǎn)都被訪問(wèn)過(guò)為止。這種搜索的次序體現(xiàn)沿層次向橫向擴(kuò)展的趨勢(shì)，所以稱之為廣度優(yōu)先搜索。第二頁(yè)，共二十四頁(yè)，2022年，8月28日廣度優(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è)，共二十四頁(yè)，2022年，8月28日廣度優(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)先搜索的效率還有賴于目標(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ò)展的順序。粗線條路徑表明求得的一個(gè)解。從圖中可以看出，擴(kuò)展第２６個(gè)結(jié)點(diǎn)，總共生成４６個(gè)結(jié)點(diǎn)之后，才求得這個(gè)解。此外，直接觀察此圖表明，不存在有更短走步序列的解。第四頁(yè)，共二十四頁(yè)，2022年，8月28日第五頁(yè)，共二十四頁(yè)，2022年，8月28日【例8.1】圖8-2表示的是從城市A到城市H的交通圖。從圖中可以看出，從城市A到城市H要經(jīng)過(guò)若干個(gè)城市?，F(xiàn)要找出一條經(jīng)過(guò)城市最少的一條路線。圖8-2第六頁(yè)，共二十四頁(yè)，2022年，8月28日【算法分析】看到這圖很容易想到用鄰接距陣來(lái)表示，0表示能走，1表示不能走。如圖。

首先想到的是用隊(duì)列的思想。a數(shù)組是存儲(chǔ)擴(kuò)展結(jié)點(diǎn)的隊(duì)列，a[i]記錄經(jīng)過(guò)的城市,b[i]記錄前趨城市，這樣就可以倒推出最短線路。具體過(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]可倒推出最少城市線路。第七頁(yè)，共二十四頁(yè)，2022年，8月28日【參考程序】#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;}第八頁(yè)，共二十四頁(yè)，2022年，8月28日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í)路線最短

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

return0;}第九頁(yè)，共二十四頁(yè)，2022年，8月28日【例8.2】一矩形陣列由數(shù)字0到9組成,數(shù)字1到9代表細(xì)胞,細(xì)胞的定義為沿細(xì)胞數(shù)字上下左右還是細(xì)胞數(shù)字則為同一細(xì)胞,求給定矩形陣列的細(xì)胞個(gè)數(shù)。如:陣列4100234500067103456050020456006710000000089有4個(gè)細(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ù)。

第十頁(yè)，共二十四頁(yè)，2022年，8月28日【參考程序】#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ì)空為止}第十一頁(yè)，共二十四頁(yè)，2022年，8月28日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;}第十二頁(yè)，共二十四頁(yè)，2022年，8月28日【例8.3】最短路徑（1995年高中組第4題）如下圖所示，從入口（1）到出口（17）的可行路線圖中，數(shù)字標(biāo)號(hào)表示關(guān)卡?，F(xiàn)將上面的路線圖，按記錄結(jié)構(gòu)存儲(chǔ)如下圖6：請(qǐng)?jiān)O(shè)計(jì)一種能從存儲(chǔ)數(shù)據(jù)中求出從入口到出口經(jīng)過(guò)最少關(guān)卡路徑的算法。第十三頁(yè)，共二十四頁(yè)，2022年，8月28日【算法分析】

該題是一個(gè)路徑搜索問(wèn)題，根據(jù)圖示，從入口（1）到出口（17）可能有多條途徑，其中最短的路徑只有一條，那么如何找最短路徑呢？根據(jù)題意，用數(shù)組no存儲(chǔ)各關(guān)卡號(hào)，用數(shù)組per存儲(chǔ)訪問(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ì)，即訪問(wèn)一個(gè)頂點(diǎn)，將其后繼頂點(diǎn)入隊(duì)，并存儲(chǔ)它的前趨頂點(diǎn)，……，直到訪問(wèn)到出口（17）。最后，再?gòu)某隹诘年P(guān)卡號(hào)（17）開(kāi)始回訪它的前趨關(guān)卡號(hào)，……，直到入口的關(guān)卡號(hào)（1），則回訪的搜索路徑便是最短路徑。從列表中可以看出出口關(guān)卡號(hào)（17）的被訪問(wèn)路徑最短的是：（17）←（16）←（19）←（18）←（1）由此，我們得到廣度優(yōu)先遍歷求最短路徑的基本方法如下：假設(shè)用鄰接矩陣存放路線圖（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））；

第十四頁(yè)，共二十四頁(yè)，2022年，8月28日

注意后繼頂點(diǎn)入隊(duì)前，必須要檢查這個(gè)頂點(diǎn)是否已在隊(duì)列中，如果已經(jīng)在了就不要入隊(duì)了；這一步可稱為圖的遍歷或拓展；（2）從隊(duì)列的最后一個(gè)關(guān)卡號(hào)（出口（17））開(kāi)始，依次回訪它的前驅(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。第十五頁(yè)，共二十四頁(yè)，2022年，8月28日【例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)參考程序。第十六頁(yè)，共二十四頁(yè)，2022年，8月28日【深搜參考程序】#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);//往上

}}第十七頁(yè)，共二十四頁(yè)，2022年，8月28日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;}第十八頁(yè)，共二十四頁(yè)，2022年，8月28日【廣搜參考程序】#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;第十九頁(yè)，共二十四頁(yè)，2022年，8月28日

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;}

第二十頁(yè)，共二十四頁(yè)，2022年，8月28日輸入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.第二十一頁(yè)，共二十四頁(yè)，2022年，8月28日【上機(jī)練習(xí)】1、面積（area）編程計(jì)算由“*”號(hào)圍成的下列圖形的面積。面積計(jì)算方法是統(tǒng)計(jì)*號(hào)所圍成的閉合曲線中水平線和垂直線交點(diǎn)的數(shù)目。如下圖所示，在10*10的二維數(shù)組中，有“*”圍住了15個(gè)點(diǎn)，因此面積為15。00000000000000***0000000*00*