寬度優(yōu)先搜索算法(pascal)

以走迷宮為例,就是一群人一起出發(fā),然后遇到叉路口就分開(kāi)走,只要有一個(gè)人走出就把所有人帶走

目前創(chuàng)新互聯(lián)已為上千多家的企業(yè)提供了網(wǎng)站建設(shè)、域名、雅安服務(wù)器托管、網(wǎng)站托管運(yùn)營(yíng)、企業(yè)網(wǎng)站設(shè)計(jì)、南明網(wǎng)站維護(hù)等服務(wù)，公司將堅(jiān)持客戶(hù)導(dǎo)向、應(yīng)用為本的策略，正道將秉承"和諧、參與、激情"的文化，與客戶(hù)和合作伙伴齊心協(xié)力一起成長(zhǎng)，共同發(fā)展。

寬度優(yōu)先搜索的偽代碼實(shí)現(xiàn)

下面的寬度優(yōu)先搜索過(guò)程BFS假定輸入圖G=(V,E)采用鄰接表表示，對(duì)于圖中的每個(gè)頂點(diǎn)還采用了幾種附加的數(shù)據(jù)結(jié)構(gòu)，對(duì)每個(gè)頂點(diǎn)u∈V，其色彩存儲(chǔ)于變量color[u]中，結(jié)點(diǎn)u的父母存于變量π[u]中。如果u沒(méi)有父母(例如u=s或u還沒(méi)有被檢索到)，則 π[u]=NIL，由算法算出的源點(diǎn)s和頂點(diǎn)u之間的距離存于變量d[u]中，算法中使用了一個(gè)先進(jìn)先出隊(duì)列Q來(lái)存放灰色節(jié)點(diǎn)集合。其中head[Q]表示隊(duì)列Q的隊(duì)頭元素，Enqueue(Q,v)表示將元素v入隊(duì)， Dequeue(Q)表示對(duì)頭元素出隊(duì)；Adj[u]表示圖中和u相鄰的節(jié)點(diǎn)集合。

BFS(G,S)

foreachu∈V[G]-{s}

do

color[u]←White;

d[u]←∞;

π[u]←NIL;

end;

color[s]←Gray;

d[s]←0;

π[s]←NIL;

Q←{s}

while(Q≠φ)

do

u←head[Q];

for each v∈Adj[u]

do

if(color[v]=White)

then

color[v]←Gray;

d[v]←d[u]+1;

π[v]←u;

Enqueue(Q,v);

end;

Dequeue(Q);

color[u]←Black;

end;

end;

end;

圖1展示了用BFS在例圖上的搜索過(guò)程。黑色邊是由BFS產(chǎn)生的樹(shù) 枝。每個(gè)節(jié)點(diǎn)u內(nèi)的值為d[u]，圖中所示的隊(duì)列Q是第9-18行while循環(huán)中每次迭代起始時(shí)的隊(duì)列。隊(duì)列中每個(gè)結(jié)點(diǎn)下面是該結(jié)點(diǎn)與源結(jié)點(diǎn)的距離。

圖1 BFS在一個(gè)無(wú)向圖上的執(zhí)行過(guò)程

過(guò)程BFS按如下方式執(zhí)行，第1-4行置每個(gè)結(jié)點(diǎn)為白色，置d[u]為無(wú)窮大，每個(gè)結(jié)點(diǎn)的父母置為NIL，第5行置源結(jié)點(diǎn)S為灰色，即意味著過(guò)程開(kāi)始時(shí)源結(jié)點(diǎn)已被發(fā)現(xiàn)。第6行初始化d[s]為0，第7行置源結(jié)點(diǎn)的父母結(jié)點(diǎn)為NIL，第8行初始化隊(duì)列0，使其僅含源結(jié)點(diǎn)s，以后Q隊(duì)列中僅包含灰色結(jié)點(diǎn)的集合。

程序的主循環(huán)在9-18行中，只要隊(duì)列Q中還有灰色結(jié)點(diǎn)，即那些已被發(fā)現(xiàn)但還沒(méi)有完全搜索其鄰接表的結(jié)點(diǎn)，循環(huán)將一直進(jìn)行下去。第10行確定隊(duì)列頭的灰色結(jié)點(diǎn)為u。第11-16行的循環(huán)考察u的鄰接表中的每一個(gè)頂點(diǎn)v。如果v是白色結(jié)點(diǎn)，那么該結(jié)點(diǎn)還沒(méi)有被發(fā)現(xiàn)過(guò)，算法通過(guò)執(zhí)行第13-16行發(fā)現(xiàn)該結(jié)點(diǎn)。首先它被置為灰色，距離d[v]置為d[u]+1，而后u被記為該節(jié)點(diǎn)的父母，最后它被放在隊(duì)列Q的隊(duì)尾。當(dāng)結(jié)點(diǎn)u的鄰接表中的所有結(jié)點(diǎn)都被檢索后，第17 -18行使u彈出隊(duì)列并置成黑色。

7.3實(shí)現(xiàn)寬度優(yōu)先搜索

在單詞關(guān)系圖建立完成以后，需要繼續(xù)在圖中尋找詞梯問(wèn)題的最短序列，需要用到“寬度優(yōu)先搜索Breadth First Search”算法對(duì)單詞關(guān)系圖進(jìn)行搜索

BFS是搜索圖的最簡(jiǎn)單算法之一，也是其它一些重要的圖算法的基礎(chǔ)給定圖G，以及開(kāi)始搜索的起始頂點(diǎn)s。BFS搜索所有從s可到達(dá)頂點(diǎn)的邊而且在達(dá)到更遠(yuǎn)的距離k+1的頂點(diǎn)之前，BFS會(huì)找到全部距離為k的頂點(diǎn)可以想象為以s為根，構(gòu)建一棵樹(shù)的過(guò)程，從頂部向下逐步增加層次寬度優(yōu)先搜索能保證在增加層次之前，添加了所有兄弟節(jié)點(diǎn)到樹(shù)中。

BFS算法過(guò)程

?為了跟蹤頂點(diǎn)的加入過(guò)程，并避免重復(fù)頂點(diǎn)，要為頂點(diǎn)增加3個(gè)屬性

1.距離distance：從起始頂點(diǎn)到此頂點(diǎn)路徑長(zhǎng)度；

2.前驅(qū)頂點(diǎn)predecessor：可反向追溯到起點(diǎn)；

3.顏色color：標(biāo)識(shí)了此頂點(diǎn)是尚未發(fā)現(xiàn)（白色）、已經(jīng)發(fā)現(xiàn)（灰色）、還是已經(jīng)完成探索（黑色）

?還需要用一個(gè)隊(duì)列Queue來(lái)對(duì)已發(fā)現(xiàn)的頂點(diǎn)進(jìn)行排列

決定下一個(gè)要探索的頂點(diǎn)（隊(duì)首頂點(diǎn)）

?從起始頂點(diǎn)s開(kāi)始，作為剛發(fā)現(xiàn)的頂點(diǎn)，標(biāo)注為灰色，距離為0，前驅(qū)為None，加入隊(duì)列，接下來(lái)是個(gè)循環(huán)迭代過(guò)程：

從隊(duì)首取出一個(gè)頂點(diǎn)作為當(dāng)前頂點(diǎn)；遍歷當(dāng)前頂點(diǎn)的鄰接頂點(diǎn)，如果是尚未發(fā)現(xiàn)的白

色頂點(diǎn)，則將其顏色改為灰色（已發(fā)現(xiàn)），距離增加1，前驅(qū)頂點(diǎn)為當(dāng)前頂點(diǎn)，加入到隊(duì)列中遍歷完成后，將當(dāng)前頂點(diǎn)設(shè)置為黑色（已探索過(guò)），循環(huán)回到步驟1的隊(duì)首取當(dāng)前頂點(diǎn)

算法分析

BFS算法主體是兩個(gè)循環(huán)的嵌套

while循環(huán)對(duì)每個(gè)頂點(diǎn)訪(fǎng)問(wèn)一次，所以是O(|V|)，而嵌套在while中的for，由于每條邊只有在其起始頂點(diǎn)u出隊(duì)的時(shí)候才會(huì)被檢查一次，而每個(gè)頂點(diǎn)最多出隊(duì)1次，所以邊最多被檢查1次，一共是O(|E|)綜合起來(lái)BFS的時(shí)間復(fù)雜度為O(V+E)

詞梯問(wèn)題還包括兩個(gè)部分算法

建立BFS樹(shù)之后，回溯頂點(diǎn)到起始頂點(diǎn)的過(guò)程，最多為O(|V|)，創(chuàng)建單詞關(guān)系圖也需要時(shí)間，最多為O(|V|2)

網(wǎng)站名稱(chēng)：寬度優(yōu)先搜索代碼java,廣度優(yōu)先搜索代碼
文章起源：http://jinyejixie.com/article30/hsihpo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供動(dòng)態(tài)網(wǎng)站、網(wǎng)站策劃、品牌網(wǎng)站制作、網(wǎng)站營(yíng)銷(xiāo)、網(wǎng)站建設(shè)、靜態(tài)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀(guān)點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)