廣度優(yōu)先搜索和深度優(yōu)先搜索

《廣度優(yōu)先搜索和深度優(yōu)先搜索》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、有兩種常用的方法可用來搜索圖：即深度優(yōu)先搜索和廣度優(yōu)先搜索。它們最終都會(huì)到達(dá)所有連通的頂點(diǎn)。深度優(yōu)先搜索通過棧來實(shí)現(xiàn)，而廣度優(yōu)先搜索通過隊(duì)列來實(shí)現(xiàn)。?深度優(yōu)先搜索：?深度優(yōu)先搜索就是在搜索樹的每一層始終先只擴(kuò)展一個(gè)子節(jié)點(diǎn)，不斷地向縱深前進(jìn)直到不能再前進(jìn)（到達(dá)葉子節(jié)點(diǎn)或受到深度限制）時(shí)，才從當(dāng)前節(jié)點(diǎn)返回到上一級(jí)節(jié)點(diǎn)，沿另一方向又繼續(xù)前進(jìn)。這種方法的搜索樹是從樹根開始一枝一枝逐漸形成的。下面圖中的數(shù)字顯示了深度優(yōu)先搜索頂點(diǎn)被訪問的順序。為了實(shí)現(xiàn)深度優(yōu)先搜索，首先選擇一個(gè)起始頂點(diǎn)并需要遵守三個(gè)規(guī)則：(1)如果可能，訪問一個(gè)鄰接的未訪問頂點(diǎn)，標(biāo)記它，并把它放入棧中。(2)當(dāng)不能

2、執(zhí)行規(guī)則1時(shí)，如果棧不空，就從棧中彈出一個(gè)頂點(diǎn)。(3)如果不能執(zhí)行規(guī)則1和規(guī)則2，就完成了整個(gè)搜索過程。廣度優(yōu)先搜索：在深度優(yōu)先搜索算法中，是深度越大的結(jié)點(diǎn)越先得到擴(kuò)展。如果在搜索中把算法改為按結(jié)點(diǎn)的層次進(jìn)行搜索，本層的結(jié)點(diǎn)沒有搜索處理完時(shí)，不能對(duì)下層結(jié)點(diǎn)進(jìn)行處理，即深度越小的結(jié)點(diǎn)越先得到擴(kuò)展，也就是說先產(chǎn)生的結(jié)點(diǎn)先得以擴(kuò)展處理，這種搜索算法稱為廣度優(yōu)先搜索法。在深度優(yōu)先搜索中，算法表現(xiàn)得好像要盡快地遠(yuǎn)離起始點(diǎn)似的。相反，在廣度優(yōu)先搜索中，算法好像要盡可能地靠近起始點(diǎn)。它首先訪問起始頂點(diǎn)的所有鄰接點(diǎn)，然后再訪問較遠(yuǎn)的區(qū)域。它是用隊(duì)列來實(shí)現(xiàn)的。下面圖中的數(shù)字顯示了廣度優(yōu)先

3、搜索頂點(diǎn)被訪問的順序。實(shí)現(xiàn)廣度優(yōu)先搜索，也要遵守三個(gè)規(guī)則：(1)訪問下一個(gè)未來訪問的鄰接點(diǎn)，這個(gè)頂點(diǎn)必須是當(dāng)前頂點(diǎn)的鄰接點(diǎn)，標(biāo)記它，并把它插入到隊(duì)列中。(2)如果因?yàn)橐呀?jīng)沒有未訪問頂點(diǎn)而不能執(zhí)行規(guī)則1時(shí)，那么從隊(duì)列頭取一個(gè)頂點(diǎn)，并使其成為當(dāng)前頂點(diǎn)。(3)如果因?yàn)殛?duì)列為空而不能執(zhí)行規(guī)則2，則搜索結(jié)束。BFS是一種盲目搜尋法，目的是系統(tǒng)地展開并檢查圖中的所有節(jié)點(diǎn)，以找尋結(jié)果。換句話說，它并不考慮結(jié)果的可能位址，徹底地搜索整張圖，直到找到結(jié)果為止。BFS并不使用經(jīng)驗(yàn)法則算法。從算法的觀點(diǎn)，所有因?yàn)檎归_節(jié)點(diǎn)而得到的子節(jié)點(diǎn)都會(huì)被加進(jìn)一個(gè)先進(jìn)先出的佇列中。一般的實(shí)作里，其鄰居節(jié)點(diǎn)尚

4、未被檢驗(yàn)過的節(jié)點(diǎn)會(huì)被放置在一個(gè)被稱為open的容器中（例如佇列或是鏈表），而被檢驗(yàn)過的節(jié)點(diǎn)則被放置在被稱為closed的容器中。（open-closed表）實(shí)作方法1.首先將根節(jié)點(diǎn)放入佇列中。2.從佇列中取出第一個(gè)節(jié)點(diǎn)，并檢驗(yàn)它是否為目標(biāo)。o如果找到目標(biāo)，則結(jié)束搜尋并回傳結(jié)果。o否則將它所有尚未檢驗(yàn)過的直接子節(jié)點(diǎn)加入佇列中。2.若佇列為空，表示整張圖都檢查過了——亦即圖中沒有欲搜尋的目標(biāo)。結(jié)束搜尋并回傳“找不到目標(biāo)”。3.重復(fù)步驟2。C的實(shí)作廣度優(yōu)先搜索算法：voidBFS(VLinkG[],intv){intw;VISIT(v);/*訪問頂點(diǎn)v*/visited[v]

5、=1;/*頂點(diǎn)v對(duì)應(yīng)的訪問標(biāo)記置為1*/ADDQ(Q,v);while(!EMPTYQ(Q)){v=DELQ(Q);/*退出隊(duì)頭元素v*/w=FIRSTADJ(G,v);/*求v的第1個(gè)鄰接點(diǎn)。無鄰接點(diǎn)則返回-1*/while(w!=-1){if(visited[w]==0){VISIT(w);/*訪問頂點(diǎn)v*/ADDQ(Q,w);/*當(dāng)前被訪問的頂點(diǎn)w進(jìn)隊(duì)*/visited[w]=1;/*頂點(diǎn)w對(duì)應(yīng)的訪問標(biāo)記置為1*/}w=NEXTADJ(G,v);/*求v的下一個(gè)鄰接點(diǎn)。若無鄰接點(diǎn)則返回-1*/}}}對(duì)圖G=(V,E)進(jìn)行廣度優(yōu)先搜索的主算法如下。voidTRAVE

6、L_BFS(VLinkG[],intvisited[],intn){inti;for(i=0;i

7、如果存在正常數(shù)c1、c2和正整數(shù)n0，使得當(dāng)n>=n0時(shí)，0

8、))={f(n)

9、如果存在正常數(shù)c和正整數(shù)n0，使得當(dāng)n>=n0時(shí)，0<=f(n)<=cg(n)恒成立}　　定義三：Ω(g(n))={f(n)

10、如果存在正常數(shù)c和正整數(shù)n0，使得當(dāng)n>=n0時(shí)，0<=cg(n)<=f(n)恒成立}