圖的遍歷

　　圖的遍歷和樹的遍歷類似，希望從圖中某一頂點(diǎn)出發(fā)訪遍圖中其余頂點(diǎn)，且使每一個(gè)頂點(diǎn)僅被訪問(wèn)一次，這一過(guò)程就叫圖的遍歷。

　　對(duì)于圖的遍歷來(lái)說(shuō)，如何避免因回路陷入死循環(huán)，就需要科學(xué)地設(shè)計(jì)遍歷方案，通過(guò)有兩種遍歷次序方案：深度優(yōu)先遍歷和廣度優(yōu)先遍歷。

　　2.1 深度優(yōu)先遍歷

　　深度優(yōu)先遍歷，也有稱為深度優(yōu)先搜索，簡(jiǎn)稱DFS。其實(shí)，就像是一棵樹的前序遍歷。

　　它從圖中某個(gè)結(jié)點(diǎn)v出發(fā)，訪問(wèn)此頂點(diǎn)，然后從v的未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問(wèn)到。若圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中的所有頂點(diǎn)都被訪問(wèn)到為止。

　　我們用鄰接矩陣的方式，則代碼如下所示。

　　如果使用的是鄰接表存儲(chǔ)結(jié)構(gòu)，其DFSTraverse函數(shù)的代碼幾乎是相同的，只是在遞歸函數(shù)中因?yàn)閷��?shù)組換成了鏈表而有不同，代碼如下。

　　對(duì)比兩個(gè)不同的存儲(chǔ)結(jié)構(gòu)的深度優(yōu)先遍歷算法，對(duì)于n個(gè)頂點(diǎn)e條邊的圖來(lái)說(shuō)，鄰接矩陣由于是二維數(shù)組，要查找某個(gè)頂點(diǎn)的鄰接點(diǎn)需要訪問(wèn)矩陣中的所有元素，因?yàn)樾枰狾(n2)的時(shí)間。而鄰接表做存儲(chǔ)結(jié)構(gòu)時(shí)，找鄰接點(diǎn)所需的時(shí)間取決于頂點(diǎn)和邊的數(shù)量，所以是O(n+e)。顯然對(duì)于點(diǎn)多邊少的稀疏圖來(lái)說(shuō)，鄰接表結(jié)構(gòu)使得算法在時(shí)間效率上大大提高。