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

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

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

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

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

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

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

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