亚洲国产区中文,国产精品91高清,亚洲精品中文字幕久久久久,亚洲欧美另类久久久精品能播放

作法

BFS是一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點，以找尋結(jié)果。換句話說，它并不考慮結(jié)果的可能位址，徹底地搜索整張圖，直到找到結(jié)果為止。BFS并不使用經(jīng)驗法則算法。

從算法的觀點，所有因為展開節(jié)點而得到的子節(jié)點都會被加進一個先進先出的隊列中。一般的實現(xiàn)里，其鄰居節(jié)點尚未被檢驗過的節(jié)點會被放置在一個被稱為 open 的容器中（例如佇列或是鏈表），而被檢驗過的節(jié)點則被放置在被稱為 closed 的容器中。（open-closed表）

實現(xiàn)方法

首先將根節(jié)點放入隊列中。

從隊列中取出第一個節(jié)點，并檢驗它是否為目標(biāo)。

若隊列為空，表示整張圖都檢查過了——亦即圖中沒有欲搜尋的目標(biāo)。結(jié)束搜尋并回傳“找不到目標(biāo)”。

重復(fù)步驟2。

C 的實現(xiàn)

/*** ADDQ (Q, p) - p PUSH 入 Q* DELQ (Q) - POP Q 並返回 Q 頂* FIRSTADJ (G,v) - v 的第一個鄰接點，找不到則返回 -1* NEXTADJ (G,v) - v 的下一個鄰接點，找不到則返回 -1* VISIT (v) - 訪問 v* visited [] - 是否已訪問*//* 廣度優(yōu)先搜索算法 */voidBFS(VLinkG[],intv){intw;/* 訪問 v 並入隊 */VISIT(v);visited[v]=1;ADDQ(Q,v);/* 對隊列 Q 的各元素 */while(!EMPTYQ(Q)){v=DELQ(Q);w=FIRSTADJ(G,v);/* 的各鄰接點 */do{/* 進行訪問和入隊 */if(visited[w]==0){VISIT(w);ADDQ(Q,w);visited[w]=1;}}while(w=NEXTADJ(G,v))!=-1)}}/* 對圖G=(V,E)進行廣度優(yōu)先搜索的主算法 */voidTRAVEL_BFS(VLinkG[],boolvisited[],intn){inti;// 清零標(biāo)記數(shù)組for(i=0;i<n;i++)visited[i]=0;for(i=0;i<n;i++)if(visited[i]==0)BFS(G,i);}

C++ 的實現(xiàn)

(這個例子僅針對Binary Search Tree) 定義一個結(jié)構(gòu)體來表達一個節(jié)點的結(jié)構(gòu)：

structnode{intself;//數(shù)據(jù)node*left;//左節(jié)點node*right;//右節(jié)點};

那么，我們在搜索一個樹的時候，從一個節(jié)點開始，能首先獲取的是它的兩個子節(jié)點。例如：

A是第一個訪問的，然后順序是B和C；然后再是B的子節(jié)點，C的子節(jié)點。那么我們怎么來保證這個順序呢？

這里就應(yīng)該用queue數(shù)據(jù)結(jié)構(gòu)，因為queue采用先進先出( first-in-first-out )的順序。

使用C++的STL函式庫，下面的程序能幫助理解：

std::queuevisited,unvisited;nodenodes[9];node*current;unvisited.push(&nodes[0]);//先把root放入unvisited queuewhile(!unvisited.empty())//只有unvisited不空{(diào)current=(unvisited.front());//目前應(yīng)該檢驗的if(current->left!=NULL)unvisited.push(current->left);//把左邊放入queue中if(current->right!=NULL)//右邊壓入。因為QUEUE是一個先進先出的結(jié)構(gòu)構(gòu)，所以即使後面再壓其他東西，依然會先訪問這個。unvisited.push(current->right);visited.push(current);cout<self<<endl;unvisited.pop();}

特性

空間復(fù)雜度

因為所有節(jié)點都必須被儲存，因此BFS的空間復(fù)雜度為O(|V| + |E|)，其中|V|是節(jié)點的數(shù)目，而|E|是圖中邊的數(shù)目。注：另一種說法稱BFS的空間復(fù)雜度為 O ( B M ) {\displaystyle O(B^{M})} ，其中B是最大分支系數(shù)，而M是樹的最長路徑長度。由于對空間的大量需求，因此BFS并不適合解非常大的問題。

時間復(fù)雜度

最差情形下，BFS必須尋找所有到可能節(jié)點的所有路徑，因此其時間復(fù)雜度為O(|V| + |E|)，其中|V|是節(jié)點的數(shù)目，而|E|是圖中邊的數(shù)目。

完全性

廣度優(yōu)先搜索算法具有完全性。這意指無論圖形的種類如何，只要目標(biāo)存在，則BFS一定會找到。然而，若目標(biāo)不存在，且圖為無限大，則BFS將不收斂（不會結(jié)束）。

最佳解

若所有邊的長度相等，廣度優(yōu)先搜索算法是最佳解——亦即它找到的第一個解，距離根節(jié)點的邊數(shù)目一定最少；但對一般的圖來說，BFS并不一定回傳最佳解。這是因為當(dāng)圖形為加權(quán)圖（亦即各邊長度不同）時，BFS仍然回傳從根節(jié)點開始，經(jīng)過邊數(shù)目最少的解；而這個解距離根節(jié)點的距離不一定最短。這個問題可以使用考慮各邊權(quán)值，BFS的改良算法成本一致搜尋法來解決。然而，若非加權(quán)圖形，則所有邊的長度相等，BFS就能找到最近的最佳解。

廣度優(yōu)先搜索算法的應(yīng)用

廣度優(yōu)先搜索算法能用來解決圖論中的許多問題，例如：

尋找圖中所有連接元件（Connected Component）。一個連接元件是圖中的最大相連子圖。

尋找連接元件中的所有節(jié)點。

尋找非加權(quán)圖中任兩點的最短路徑。

測試一圖是否為二分圖。

（Reverse）Cuthill–McKee算法

尋找連接元件

由起點開始，執(zhí)行廣度優(yōu)先搜索算法后所經(jīng)過的所有節(jié)點，即為包含起點的一個連接元件。

測試是否二分圖

BFS可以用以測試二分圖。從任一節(jié)點開始搜尋，并在搜尋過程中給節(jié)點不同的標(biāo)簽。例如，給開始點標(biāo)簽0，開始點的所有鄰居標(biāo)簽1，開始點所有鄰居的鄰居標(biāo)簽0……以此類推。若在搜尋過程中，任一節(jié)點有跟其相同標(biāo)簽的鄰居，則此圖就不是二分圖。若搜尋結(jié)束時這種情形未發(fā)生，則此圖為一二分圖。

應(yīng)用于電腦游戲中平面網(wǎng)格

BFS可用來解決電腦游戲（例如即時策略游戲）中找尋路徑的問題。在這個應(yīng)用中，使用平面網(wǎng)格來代替圖形，而一個格子即是圖中的一個節(jié)點。所有節(jié)點都與它的鄰居（上、下、左、右、左上、右上、左下、右下）相接。

值得一提的是，當(dāng)這樣使用BFS算法時，首先要先檢驗上、下、左、右的鄰居節(jié)點，再檢驗左上、右上、左下、右下的鄰居節(jié)點。這是因為BFS趨向于先尋找斜向鄰居節(jié)點，而不是四方的鄰居節(jié)點，因此找到的路徑將不正確。BFS應(yīng)該先尋找四方鄰居節(jié)點，接著才尋找斜向鄰居節(jié)點1。

參見

先驗算法

深度優(yōu)先搜索

參考資料

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein], Introduction to Algorithms , Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.2: Breadth-first search, pp. 531–539.

免責(zé)聲明：以上內(nèi)容版權(quán)歸原作者所有，如有侵犯您的原創(chuàng)版權(quán)請告知，我們將盡快刪除相關(guān)內(nèi)容。感謝每一位辛勤著寫的作者，感謝每一位的分享。