關(guān)于圖的遍歷參考模板

1、圖的遍歷圖的遍歷算法是球截圖的連通性問題、拓?fù)涑绦蚝颓箨P(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è)計方法。一般的，當(dāng)搜索深度較小、問題遞歸方式比較明顯時，用遞歸方法設(shè)計好，它可以使得程序結(jié)構(gòu)更簡捷易懂。當(dāng)搜索深度較大時，當(dāng)數(shù)據(jù)量較大時，由于系統(tǒng)堆棧容量的限制，遞歸容易產(chǎn)生溢出，用非遞歸方法設(shè)計比較好。（3）深度優(yōu)先搜索方法有廣義和狹義兩種理

2、解。廣義的理解是，只要最新產(chǎn)生的結(jié)點（即深度最大的結(jié)點）先進(jìn)行擴展的方法，就稱為深度優(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ù)就是深度值，因此它占用的空間較少，所以，當(dāng)搜索樹的結(jié)點較多，用其他方法易產(chǎn)生內(nèi)存溢出時，深度優(yōu)先搜索不失為一種

3、有效的算法。（5）從輸出結(jié)果可看出，深度優(yōu)先搜索找到的第一個解并不一定是最優(yōu)解.如果要求出最優(yōu)解的話，一種方法將是后面要介紹的動態(tài)規(guī)劃法，另一種方法是修改原算法：把原輸出過程的地方改為記錄過程，即記錄達(dá)到當(dāng)前目標(biāo)的路徑和相應(yīng)的路程值，并與前面已記錄的值進(jìn)行比較，保留其中最優(yōu)的，等全部搜索完成后，才把保留的最優(yōu)解輸出。算法：1 / 5Boolean visitedMAX; /訪問標(biāo)志數(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; /訪問標(biāo)志數(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）當(dāng)結(jié)點到跟結(jié)點的費用（有的書稱為耗散值）和結(jié)點的深度成正比時，特別是當(dāng)每一結(jié)點到根結(jié)點的費用等于深度時，用廣度優(yōu)先法得到的解是最優(yōu)解，但如果不成正比，則得到的解不一定是最優(yōu)

6、解。這一類問題要求出最優(yōu)解，一種方法是使用后面要介紹的其他方法求解，另外一種方法是改進(jìn)前面深度（或廣度）優(yōu)先搜索算法：找到一個目標(biāo)后，不是立即退出，而是記錄下目標(biāo)結(jié)點的路徑和費用，如果有多個目標(biāo)結(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和訪問標(biāo)志數(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;