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

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

廣度優(yōu)先搜索算法是最簡(jiǎn)便的圖的搜索算法之一，這一算法也是很多重要的圖的算法的原型。如Dijkstra單源最短路徑和Prim最小生成樹算法都采用了廣度優(yōu)先搜索的思想。核心思想：從初始節(jié)點(diǎn)開始，應(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)為止。即：1、從圖中的某一頂點(diǎn)v0開始，先訪問(wèn)v0；2、訪問(wèn)所有與v0相鄰接的頂點(diǎn)v1、v2…；3、依次訪問(wèn)與v1、v2…vt相鄰接的所有未曾訪問(wèn)過(guò)的頂點(diǎn)；4、循此以往，直到所有的頂點(diǎn)都被訪問(wèn)過(guò)為止。這種搜索的次序體現(xiàn)了沿層次向橫向擴(kuò)展的趨勢(shì)，所以稱之為廣度優(yōu)先搜索。

【模塊1】Programbfs;初始化，初始狀態(tài)存入隊(duì)列；隊(duì)列首指針head:=0;尾指針tail:=1;whilehead<taildobegininc（head）；指針head后移一位，指向待擴(kuò)展節(jié)點(diǎn)；fori:=1tomaxdobeginif新節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)then輸出并退出；if新節(jié)點(diǎn)符合條件，并且新節(jié)點(diǎn)與原已產(chǎn)生的節(jié)點(diǎn)不重復(fù)thentail指針加1，把新節(jié)點(diǎn)加入到隊(duì)尾；end；end；算法描述模塊（運(yùn)用了隊(duì)列的結(jié)構(gòu)）

【模塊2】Programbfs;初始化，初始狀態(tài)存入隊(duì)列；隊(duì)列首指針head:=0;尾指針tail:=1;repeatinc（head）；指針head后移一位，指向待擴(kuò)展節(jié)點(diǎn)；fori:=1tomaxdobeginif新節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)then輸出并退出；if新節(jié)點(diǎn)符合條件，并且新節(jié)點(diǎn)與原已產(chǎn)生的節(jié)點(diǎn)不重復(fù)thentail指針加1，把新節(jié)點(diǎn)加入到隊(duì)尾；end；untilhead=tail；end；【廣度優(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)必要記住父親節(jié)點(diǎn)）；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)解?！舅惴ǚ治觥靠磮D很容易想到用鄰接矩陣來(lái)存儲(chǔ)頂點(diǎn)之間的關(guān)系，0表示有通路，即有邊；1表示沒(méi)有通路，即沒(méi)有邊存在。定義一個(gè)a數(shù)組，充當(dāng)存儲(chǔ)擴(kuò)展節(jié)點(diǎn)的隊(duì)列，a[i].city記錄經(jīng)過(guò)的城市，a[i].pre記錄前驅(qū)城市，這樣就可以倒推出最短線路了，具體過(guò)程如下：1、將城市A入隊(duì)，隊(duì)首指針為0，隊(duì)尾指針為1；2、將隊(duì)首所指相連的城市依次入隊(duì)（注意的是該城市在隊(duì)列中未曾出現(xiàn)過(guò)），同時(shí)將入隊(duì)城市的pre指向隊(duì)首位置。然后將隊(duì)首指針加1，得到新的隊(duì)首城市。重復(fù)以上操作步驟，直到搜到H城市。利用pre可以倒推出最少城市線路。

例1如圖是從城市A到城市H的交通圖。從圖中可以看出，從城市A到城市H要經(jīng)過(guò)若干個(gè)城市?，F(xiàn)在要找出一條經(jīng)過(guò)城市最少的一條路線。ABDCGHFE10001111H01100111G01111100F00111011E10111010D11100110C11011110B11010001AHGFEDCBA矩陣存儲(chǔ)頂點(diǎn)關(guān)系【參考程序】Programex_1;constju:array[1..8,1..8]of0..1=((1,0,0,0,1,0,1,1),(0,1,1,1,1,0,1,1),(0,1,1,0,0,1,1,1),(0,1,0,1,1,1,0,1),(1,1,0,1,1,1,0,0),(0,0,1,1,1,1,1,0),(1,1,1,0,0,1,1,0),(1,1,1,1,0,0,0,1));typenode=recordcity:char;pre:integer;end;varhead,tail,i:integer;a:array[1..100]ofnode;s:array[‘A’..’H’]ofboolean;procedureprint(d:integer);beginwrite(a[d].city);repeatd:=a[d].pre;write(‘--------’,a[d].city);untila[d].pre=0;end;Proceduredoit;beginfillchar(s,sizeof(s),true);head:=0;tail:=1;a[1].city:=‘A’;a[1].pre:=0;s[a[1].city]:=false;repeatinc(head);fori:=1to8doif(ju[ord(a[head].city)-64,i]=0)and(s[chr(i+64)]=true)thenbegininc(tail);a[tail].city:=chr(i+64);a[tail].pre:=head;s[a[tail].city]:=false;ifa[tail].city=‘H’thenbeginprint(tail);break;end;end;untilhead=tail;end;Begindoit;End.【算法分析】1、讀入m*n矩陣陣列，將其轉(zhuǎn)換成為boolean矩陣存入bz數(shù)組中；2、沿bz數(shù)組矩陣從上到下、從左到右，找到遇到的第一個(gè)細(xì)胞；3、將細(xì)胞的位置入隊(duì)h，并沿其上、下、左、右四個(gè)方向上的細(xì)胞位置入隊(duì)，入隊(duì)后的位置bz數(shù)組置為false；4、將h隊(duì)頭出隊(duì)，沿其上、下、左、右四個(gè)方向上的細(xì)胞位置入隊(duì)，入隊(duì)后的位置bz數(shù)組置為false；5、重復(fù)4，直到h隊(duì)空為止，則此時(shí)找到了一個(gè)細(xì)胞；6、重復(fù)2，直至矩陣找不到細(xì)胞；7、輸出找到的細(xì)胞個(gè)數(shù)。

例2一矩形陣列由數(shù)字0-9組成，數(shù)字1-9代表細(xì)胞，細(xì)胞的定義是沿細(xì)胞數(shù)字上、下、左、右如果還是細(xì)胞數(shù)字則為同一細(xì)胞，求給定矩形陣列的細(xì)胞個(gè)數(shù)。如陣列：100234500067103456050020456006710000000089【參考程序】programcell;constdx:array[1..4]of-1..1=(-1,0,1,0);dy:array[1..4]of-1..1=(0,1,0,-1);varname,s:string;n,m,i,j,num:integer;pic:array[1..50,1..50]ofinteger;bz:array[1..50,1..50]ofboolean;h:array[1..1000,1..2]ofinteger;proceduredoit(p,q:integer);vari,t,w,x,y:integer;begininc(num);bz[p,q]:=false;t:=1;w:=1;h[1,1]:=p;h[1,2]:=q;repeatfori:=1to4dobeginx:=h[t,1]+dx[i];y:=h[t,2]+dy[i];if(x>0)and(x<=m)and(y>0)and(y<=n)and(bz[x,y])thenbegininc(w);h[w,1]:=x;h[w,2]:=y;bz[x,y]:=false;end;end;inc(t);untilt>w;end;beginfillchar(bz,sizeof(bz),true);num:=0;readln(m,n);fori:=1tomdobeginreadln(s);forj:=1tondobeginpic[i,j]:=ord(s[j])-48;ifpic[i,j]=0thenbz[i,j]:=false;end;end;fori:=1tomdoforj:=1tondoifbz[i,j]thendoit(i,j);writeln(num);end.上機(jī)練習(xí)1、最短路徑如圖，從入口（1）到出口（17）的可行路線圖中，數(shù)字標(biāo)號(hào)表示關(guān)卡。請(qǐng)編程求從入口到出口經(jīng)過(guò)最少關(guān)卡路徑的算法。11872341258610911141315161719提示：用鄰接矩陣存儲(chǔ)關(guān)卡之間的關(guān)系與前驅(qū)?！据敵鰳永?716191812、迷宮問(wèn)題如圖，給一個(gè)n*m的迷宮圖和一個(gè)入口、一個(gè)出口。編程打印一條從迷宮入口到出口的路徑。這里黑色方塊的單元表示走不通（用-1表示），黃色單元表示可以走（用0表示），只能往上、下、左、右四個(gè)方向走，如果無(wú)路則輸出“Noway！”。（注：只輸出一條就可以了）【提示】本題深搜和廣搜都可以，請(qǐng)同學(xué)們動(dòng)動(dòng)腦子，有條件的可以兩種方法都試試看。-1-10000000出口00000-1-100-1-1-100000-1-1000-10000-1000000-10入口programexp2;constmaxn=50;dx:array[1..4]ofinteger=(1,0,-1,0);dy:array[1..4]ofinteger=(0,1,0,-1);varmap:array[1..maxn,1..maxn]ofinteger;f:boolean;n,m,i,j,desx,desy,soux,souy,head,tail,x,y,k:integer;route:array[1..maxn]ofrecordx,y,pre:integer;end;procedureprint(d:integer);beginifroute[d].pre<>0thenbeginprint(route[d].pre);inc(k);end;write('(',route[d].x,',',route[d].y,')');end;

beginreadln(n,m);fori:=1tondoforj:=1tomdoread(map[i,j]);readln(soux,souy);readln(desx,desy);

f:=false;k:=1;head:=0;tail:=1;route[1].x:=soux;route[1].y:=souy;route[1].pre:=0;map[soux,souy]:=-1;repeatinc(head);fori:=1to4dobeginx:=route[head].x+dx[i];y:=route[head].y+dy[i];if(x>0)and(x<=n)and(y>0)and(y<=m)and(map[x,y]=0)thenbegininc(tail);route[tail].x:=x;route[tail].y:=y;route[tail].pre:=head;map[x,y]:=-1;if(x=desx)and(y=desy)thenbeginf:=true;print(tail);b