關(guān)于圖的遍歷參考模板_第1頁
關(guān)于圖的遍歷參考模板_第2頁
關(guān)于圖的遍歷參考模板_第3頁
關(guān)于圖的遍歷參考模板_第4頁
關(guān)于圖的遍歷參考模板_第5頁
全文預覽已結(jié)束

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1、圖的遍歷圖的遍歷算法是球截圖的連通性問題、拓撲程序和求關(guān)鍵路徑等算法的基礎(chǔ)。通常有兩條遍歷圖的路徑:深度優(yōu)先搜索和廣度優(yōu)先搜索。它它們對無向圖和有向圖都適用。(一)、深度優(yōu)先搜索的特點是(1)無論問題的內(nèi)容和性質(zhì)以及求解要求如何不同,它們的程序結(jié)構(gòu)都是相同的。不相同的僅僅是存儲結(jié)點數(shù)據(jù)結(jié)構(gòu)和產(chǎn)生規(guī)則以及輸出要求。(2)深度優(yōu)先搜索法有遞歸以及非遞歸兩種設(shè)計方法。一般的,當搜索深度較小、問題遞歸方式比較明顯時,用遞歸方法設(shè)計好,它可以使得程序結(jié)構(gòu)更簡捷易懂。當搜索深度較大時,當數(shù)據(jù)量較大時,由于系統(tǒng)堆棧容量的限制,遞歸容易產(chǎn)生溢出,用非遞歸方法設(shè)計比較好。(3)深度優(yōu)先搜索方法有廣義和狹義兩種理

2、解。廣義的理解是,只要最新產(chǎn)生的結(jié)點(即深度最大的結(jié)點)先進行擴展的方法,就稱為深度優(yōu)先搜索方法。在這種理解情況下,深度優(yōu)先搜索算法有全部保留和不全部保留產(chǎn)生的結(jié)點的兩種情況。而狹義的理解是,僅僅只保留全部產(chǎn)生結(jié)點的算法。本書取前一種廣義的理解。不保留全部結(jié)點的算法屬于一般的回溯算法范疇。保留全部結(jié)點的算法,實際上是在數(shù)據(jù)庫中產(chǎn)生一個結(jié)點之間的搜索樹,因此也屬于圖搜索算法的范疇。(4)不保留全部結(jié)點的深度優(yōu)先搜索法,由于把擴展望的結(jié)點從數(shù)據(jù)庫中彈出刪除,這樣,一般在數(shù)據(jù)庫中存儲的結(jié)點數(shù)就是深度值,因此它占用的空間較少,所以,當搜索樹的結(jié)點較多,用其他方法易產(chǎn)生內(nèi)存溢出時,深度優(yōu)先搜索不失為一種

3、有效的算法。(5)從輸出結(jié)果可看出,深度優(yōu)先搜索找到的第一個解并不一定是最優(yōu)解.如果要求出最優(yōu)解的話,一種方法將是后面要介紹的動態(tài)規(guī)劃法,另一種方法是修改原算法:把原輸出過程的地方改為記錄過程,即記錄達到當前目標的路徑和相應(yīng)的路程值,并與前面已記錄的值進行比較,保留其中最優(yōu)的,等全部搜索完成后,才把保留的最優(yōu)解輸出。算法:1 / 5Boolean visitedMAX; /訪問標志數(shù)組Status(*Visitfunc)(int v); /函數(shù)變量Viod DFSTraverse(Graph G,Status(*Visit)(int v); /對圖G作深度優(yōu)先遍歷VisitFunc = Vis

4、it; /使用全局變量Visitfunc,使DFS不必設(shè)函數(shù)指針參數(shù)for(v=0;v<G.vexnum;+v) visitedv = FALSE; /訪問標志數(shù)組初始化for(v=0;v<G.vexnum;+v) if(!visitedv) DFS(G, v); /對尚未訪問的頂點調(diào)用GFS算法:Void DFS(Greph G, int v)/從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖G。Visitedv = TURE; Visitfunc(v); /訪問第v個頂點for (w=FirstAdjVex(G, v); w>=0; w=NextAdjVex(G,v,w) if(!v

5、isitedw) DFS(G, w); /對v的尚未訪問的臨接頂點w遞歸調(diào)用DFS(二)、廣度優(yōu)先搜索法的顯著特點是:(1)在產(chǎn)生新的子結(jié)點時,深度越小的結(jié)點越先得到擴展,即先產(chǎn)生它的子結(jié)點。為使算法便于實現(xiàn),存放結(jié)點的數(shù)據(jù)庫一般用隊列的結(jié)構(gòu)。(2)無論問題性質(zhì)如何不同,利用廣度優(yōu)先搜索法解題的基本算法是相同的,但數(shù)據(jù)庫中每一結(jié)點內(nèi)容,產(chǎn)生式規(guī)則,根據(jù)不同的問題,有不同的內(nèi)容和結(jié)構(gòu),就是同一問題也可以有不同的表示方法。(3)當結(jié)點到跟結(jié)點的費用(有的書稱為耗散值)和結(jié)點的深度成正比時,特別是當每一結(jié)點到根結(jié)點的費用等于深度時,用廣度優(yōu)先法得到的解是最優(yōu)解,但如果不成正比,則得到的解不一定是最優(yōu)

6、解。這一類問題要求出最優(yōu)解,一種方法是使用后面要介紹的其他方法求解,另外一種方法是改進前面深度(或廣度)優(yōu)先搜索算法:找到一個目標后,不是立即退出,而是記錄下目標結(jié)點的路徑和費用,如果有多個目標結(jié)點,就加以比較,留下較優(yōu)的結(jié)點。把所有可能的路徑都搜索完后,才輸出記錄的最優(yōu)路徑。(4)廣度優(yōu)先搜索算法,一般需要存儲產(chǎn)生的所有結(jié)點,占的存儲空間要比深度優(yōu)先大得多,因此程序設(shè)計中,必須考慮溢出和節(jié)省內(nèi)存空間得問題。(5)比較深度優(yōu)先和廣度優(yōu)先兩種搜索法,廣度優(yōu)先搜索法一般無回溯操作,即入棧和出棧的操作,所以運行速度比深度優(yōu)先搜索算法法要快些。 總之,一般情況下,深度優(yōu)先搜索法占內(nèi)存少但速度

7、較慢,廣度優(yōu)先搜索算法占內(nèi)存多但速度較快,在距離和深度成正比的情況下能較快地求出最優(yōu)解。算法:void BFSTraverse(Graph G,Status(*Visit)(int v)/按廣度優(yōu)先非遞歸遍歷圖G。使用輔助隊列Q和訪問標志數(shù)組visited。For (v = 0; v < G.vexnum; +v) visitedv = FALSE;InitQueue(Q); /置空的輔助隊列Qfor (v = 0; v < G.vexnum; +v) if(!visitedv) /v尚未訪問 visitedv=TRUE;Visit(v); EnQueue(Q, v); /v入隊列 while (!QueueEmpty(Q) DeQueue(Q, u); /隊頭元素出隊并置為u for ( w=FirstAdjVex(G, u); w>=0;

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論