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

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

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

寬度優(yōu)先搜索的偽代碼實現

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

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在例圖上的搜索過程。黑色邊是由BFS產生的樹 枝。每個節(jié)點u內的值為d[u]，圖中所示的隊列Q是第9-18行while循環(huán)中每次迭代起始時的隊列。隊列中每個結點下面是該結點與源結點的距離。

圖1 BFS在一個無向圖上的執(zhí)行過程

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

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

7.3實現寬度優(yōu)先搜索

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

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

BFS算法過程

?為了跟蹤頂點的加入過程，并避免重復頂點，要為頂點增加3個屬性

1.距離distance：從起始頂點到此頂點路徑長度；

2.前驅頂點predecessor：可反向追溯到起點；

3.顏色color：標識了此頂點是尚未發(fā)現（白色）、已經發(fā)現（灰色）、還是已經完成探索（黑色）

?還需要用一個隊列Queue來對已發(fā)現的頂點進行排列

決定下一個要探索的頂點（隊首頂點）

?從起始頂點s開始，作為剛發(fā)現的頂點，標注為灰色，距離為0，前驅為None，加入隊列，接下來是個循環(huán)迭代過程：

從隊首取出一個頂點作為當前頂點；遍歷當前頂點的鄰接頂點，如果是尚未發(fā)現的白

色頂點，則將其顏色改為灰色（已發(fā)現），距離增加1，前驅頂點為當前頂點，加入到隊列中遍歷完成后，將當前頂點設置為黑色（已探索過），循環(huán)回到步驟1的隊首取當前頂點

算法分析

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

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

詞梯問題還包括兩個部分算法

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

網站名稱：寬度優(yōu)先搜索代碼java,廣度優(yōu)先搜索代碼
文章起源：http://chinadenli.net/article30/hsihpo.html

成都網站建設公司_創(chuàng)新互聯，為您提供動態(tài)網站、網站策劃、品牌網站制作、網站營銷、網站建設、靜態(tài)網站

廣告

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