【文章內容簡介】 遍歷（ traversing graph）。 圖的深度優(yōu)先搜索 1．什么是圖的深度搜索 圖的深度優(yōu)先搜索（ depth_first search）遍歷類似于樹的先根遍歷，是樹的先根遍歷的推廣。圖的深度優(yōu)先遍歷的思想是：假設初始狀態(tài)是圖中所有頂點未曾被訪問，從圖中某個頂點 v0出發(fā)，訪問頂點 v0。然后依次從 v0的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和 v0有路徑相通的頂點都被訪問到；若此時圖中還有頂點未被訪問，則另選圖中一個未被訪問的頂點作為起始點，重復執(zhí)行上述過程，直到圖中所有的頂點都被訪問過。 圖的遍歷 圖的深度優(yōu)先搜索遍歷過程如圖 。 實箭頭表示訪問頂點的方向 ， 虛箭頭表示回溯 ， 數字表示訪問或回溯的次序 。 adbg無 向 圖 G6cefhiadbgcefhi1234567891 01 31 41 11 21 51 6圖 G6的 深 度 優(yōu) 先 遍 歷 過 程 圖的遍歷 2．圖的深度優(yōu)先搜索遍歷的算法實現 圖的深度優(yōu)先遍歷（鄰接表實現）的算法描述如下。 int visited[MaxSize]。 /* 訪問標志數組 */ void DFSTraverse(AdjGraph G) /*從第 1個頂點起，深度優(yōu)先搜索遍歷圖 G*/ { int v。 for(v=0。v。v++) visited[v]=0。 /*訪問標志數組初始化為未被訪問 */ for(v=0。v。v++) if(!visited[v]) DFS(G,v)。 /*對未訪問的頂點 v進行深度優(yōu)先搜索遍歷 */ printf(\n)。 } 圖的遍歷 void DFS(AdjGraph G,int v) /*從頂點 v出發(fā)遞歸深度優(yōu)先搜索遍歷圖 G*/ { int w。 visited[v]=1。 /*訪問標志設置為已訪問 */ Visit([v].data)。 /*訪問第 v個頂點 */ for(w=FirstAdjVertex(G,[v].data)。w=0。w=NextAdjVertex(G,[v].data,[w].data)) if(!visited[w]) DFS(G,w)。 /*遞歸調用 DFS對 v的尚未訪問的序號為 w的鄰接頂點 */ } 圖的遍歷 如果該圖是一個無向連通圖或者該圖是一個強連通圖 ， 則只需要調用一次 DFS(G,v)就可以遍歷整個圖 ， 否則需要多次調用DFS(G,v)。 在遍歷圖時 ， 對圖中的每個頂點至多調用一次 DFS(G,v)函數 ， 因為一旦某個頂點被標志為已被訪問 ， 就不再從它出發(fā)進行搜索 。 因此 ， 遍歷圖的過程實質上是對每個頂點查找其鄰接點的過程 。 其時間耗費取決于所采用的存儲結構 。 當用二維數組表示鄰接矩陣作為圖的存儲結構時 ， 查找每個頂點的鄰接點所需時間為O(n2)， 其中 n為圖中的頂點數 。 當以鄰接表作為圖的存儲結構時 ，查找鄰接點的時間為 O(e)， 其中 ， e為無向圖邊的數目或有向圖弧的數目 。 由此 ， 當以鄰接表作為存儲結構時 ， 深度優(yōu)先搜索遍歷圖的時間復雜度為 O(n+e)。 圖的遍歷 另一種寫法是： void DFS(AdjGraph G,int v) /*從頂點 v出發(fā)遞歸深度優(yōu)先搜索遍歷圖 G*/ { ArcNode *p。 visited[v]=1。 /*訪問標志設置為已訪問 */ Visit([v].data)。 /*訪問第 v個頂點 */ p=[v].firstarc。 /*取 v的邊表頭指針， p指向 v的鄰接點 */ while(p) /*依次搜索 v的鄰接點 */ { if(!visited[padjvex]) /*若 v尚未被訪問 */ DFS(G,padjvex)。/*以 v的鄰接點縱深搜索 */ p=pnextarc。 /*找 v的下一個鄰接點 */ } } 圖的遍歷 以鄰接表作為存儲結構，查找 v的第一個鄰接點的算法實現如下。 int FirstAdjVertex(AdjGraph G,VertexType v) /*返回頂點 v的第一個鄰接頂點的序號 */ { ArcNode *p。 int v1。 v1=LocateVertex(G,v)。 /*v1為頂點 v在圖 G中的序號*/ p=[v1].firstarc。 if(p) /*如果頂點 v的第一個鄰接點存在，返回鄰接點的序號，否則返回 1 */ return padjvex。 else return 1。 } 圖的遍歷 以鄰接表作為存儲結構，查找 v的相對于 w的下一個鄰接點的算法實現如下。 int NextAdjVertex(AdjGraph G,VertexType v,VertexType w) /*返回 v的相對于 w的下一個鄰接頂點的序號 */ { ArcNode *p,*next。 int v1,w1。 v1=LocateVertex(G,v)。 /*v1為頂點 v在圖 G中的序號 */ w1=LocateVertex(G,w)。 /*w1為頂點 w在圖 G中的序號 */ for(next=[v1].firstarc。next。) if(nextadjvex!=w1) next=nextnextarc。 p=next。 /*p指向頂點 v的鄰接頂點 w的結點 */ if(!p||!pnextarc) /*如果 w不存在或 w是最后一個鄰接點，則返回 1*/ return 1。 else return pnextarcadjvex。 /*返回 v的相對于 w的下一個鄰接點的序號 */ } 圖的遍歷 圖的廣度優(yōu)先搜索 1．什么是圖的廣度優(yōu)先搜索遍歷 圖的廣度優(yōu)先搜索 (breadth_first search)遍歷類似于樹的層次遍歷過程。圖的廣度優(yōu)先搜索遍歷的思想是：從圖的某個頂點 v出發(fā)，在訪問了 v之后依次訪問 v的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發(fā)依次訪問他們的鄰接點，并使 “ 先被訪問的頂點的鄰接點 ” 先于 “ 后被訪問的頂點的鄰接點 ” 被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中還有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作為起始點，重復上述過程，直至圖中的所有頂點都被訪問到為止。 圖的遍歷 例如，圖 G6的廣度優(yōu)先搜索遍歷的過程如圖 。其中，箭頭表示廣度遍歷的方向，旁邊的數字表示遍歷的次序。 因此，圖 G6的廣度優(yōu)先搜索遍歷序列為 a、 b、 c、 d、 e、 f、 g、h、 i。 adbgcefhi14523687 圖的遍歷 2．圖的廣度優(yōu)先遍歷的算法實現 與深度優(yōu)先搜索類似，在圖的廣度優(yōu)先的遍歷過程中也需要一個訪問標志數組 visited[MaxSize]，用來表示頂點是否被訪問過。初始時，將圖中的所有頂點的標志數組 visited[vi]都初始化為 0，表示頂點未被訪問。從第 1個頂點 v0出發(fā)，訪問該頂點并將標志數組置為 1。然后將 v0入隊，當隊列不為空時，將隊頭元素（頂點）出隊，依次訪問該頂點的所有鄰接點，同時將標志數組對應位置為1，并將其鄰接點依次入隊。依次類推，直到圖中的所有頂點都已被訪問過。 圖的遍歷 圖的廣度優(yōu)先搜索遍歷的算法實現如下。 void BFSTraverse(AdjGraph G) /*從第 1個頂點出發(fā)，按廣度優(yōu)先非遞歸遍歷圖 G*/ { int v,front,rear。 ArcNode *p。 int queue[MaxSize]。 /*定義一個隊列 Q*/ front=rear=1。 /*初始化隊列 Q*/ for(v=0。v。v++) /*初始化標志位 */ visited[v]=0。 v=0。 visited[v]=1。 /*設置訪問標志為 1，表示已經被訪問過 */ Visit([v].data)。 rear=(rear+1)%MaxSize。 圖的遍歷 queue[rear]=v。 /*v入隊列 */ while(frontrear) /*如果隊列不空 */ { front=(front+1)%MaxSize。 v=queue[front]。 /*隊頭元素出隊賦值給 v*/ p=[v].firstarc。 while(p!=NULL) /*遍歷序號為 v的所有鄰接點 */ { if(visited[padjvex]==0) /*如果該頂點未被訪問過 */ { visited[padjvex]=1。 Visit([padjvex].data)。 rear=(rear+1)%MaxSize。 queue[rear]=padjvex。 } p=pnextarc。 /*p指向下一個鄰接點 */ } } } 圖的遍歷 圖的遍歷應用舉例 【 例 10_3】 編寫一個算法，要求對圖 G6進行深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷（假設圖采用鄰接表存儲）。 圖的連通性問題 無向圖的連通分量與最小生成樹 在對無向圖進行遍歷時，對于連通圖，僅需從圖的任何一個頂點出發(fā)，進行深度優(yōu)先搜索或廣度優(yōu)先搜索，就可訪問到圖中的所有頂點。對于非連通圖，則需從多個頂點出發(fā)進行搜索，而每一次從一個新的起始點出發(fā)進行搜索過程中得到的頂點訪問序列恰為其各個連通分量中的頂點集。 圖的連通性問題 圖 G3的鄰接表如圖 。圖 G3是非連通圖且有3個連通分量，因此在對圖 G3進行深度優(yōu)先遍歷時，需要從圖的至少 3個頂點（頂點 a、頂點 g和頂點 i）出發(fā)，才能完成對圖中的每個頂點的訪問。對圖 G3進行深度遍歷，經過 3次遞歸調用得到的 3個序列分別為：（ 1） a、 b、c、 d、 m、 e、 f；（ 2） g、 h；（ 3） i、 j、 k、 l。這 3個頂點集分別加上依附于這些頂點的邊，就構成了非連通圖 G3的兩個連通分量，如圖 （ b）所示。 a bd c( a ) 無 向 圖 G3fmjikeghl( b ) 無 向 圖 G3的 鄰 接 表 1 3 ^ 1 3 0 abcd0123efghi45678 0 2 4 1 2 ^ 8 ^ 2 7 0 ^ 9 1 0 ^ 0 ^ 6 ^jklm91 01 11 21 2 ^^ 8 1 0 ^ 8 9 1 1 ^1 0 ^ 2 3 ^ 圖的連通性問題 設 E（ G） 為連通圖 G中所有邊的集合 ， 則從圖中任一頂點出發(fā)遍歷圖時 ，必定將 E(G)分成兩個集合 T（ G） 和 B（ G） ， 其中 T（ G） 是遍歷圖過程中經過的邊的集合 ， B（ G） 是剩余邊的集合 。 顯然 ， T（ G） 和圖 G中所有頂點一起構成連通圖 G的極小連通子圖 ， 根據 ， 它是連通圖的一棵生成樹 。 由深度優(yōu)先搜索得到的為深度優(yōu)先生成樹對于連通圖 ， 由廣度優(yōu)先搜索得到的為廣度優(yōu)先生成樹 。 圖 G6的深度優(yōu)先生成樹和廣度優(yōu)先生成樹 。 adbgcefhi圖 G6的 深 度 優(yōu) 先 生 成 樹adbgcefhi圖 G6的 廣 度 優(yōu) 先 生 成 樹 圖的連通性問題 對于非連通圖 ， 從某一個頂點出發(fā) ， 對圖進行深度優(yōu)先搜索遍歷或者廣度優(yōu)先搜遍歷 ， 按照訪問路徑會得到若干棵生成樹 ， 這些生成樹放在一起就構成了森林 。 對圖 G3進行深度優(yōu)先搜索得到的森林如圖 。 a