【正文】 ?假設(shè)初始狀態(tài)是圖中所有頂點未曾被訪問，則深度優(yōu)先搜索可從圖中某個頂點 v出發(fā)，訪問此頂點，然后依次從 v的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和 v有路徑相通的頂點都被訪問到； ?若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。 A C D E G B F I H A C D E G B F I H 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 前進 回退 深度優(yōu)先搜索過程 深度優(yōu)先生成樹 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 7章 圖 圖的遍歷 ?圖的深度優(yōu)先搜索算法 ? Boolean visited [MAX]； //訪問標志數(shù)組 Status(*VisitFunc)(int v)； //函數(shù)變量 void DFSTraverse(Graph G， Status(*Visit)(int v)){ //對圖 G作 深度優(yōu)先遍歷。 //使用全局變量 VisitFunc，使 DFS不必設(shè)函數(shù) 指針參數(shù) for(v=0； v； ++v) visited[v]=FALSE。 w。 ?假設(shè)從圖中某頂點 v出發(fā)，在訪問 v之后依次訪問 v的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使 “ 先被訪問的頂點的鄰接點 ” 先于 “ 后被訪問的頂點的鄰接點 ” 被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 7章 圖 圖的遍歷 ?圖的廣度優(yōu)先搜索 A C D E G B F I H A C D E G B F H 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹 I 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 7章 圖 圖的遍歷 ?圖的廣度優(yōu)先搜索算法 ? void BFSTraverse(Graph G， Status(*Visit)(int v)){ //按廣度優(yōu)先非遞歸遍歷圖 G 使用輔助隊列 Q和訪問標志數(shù)組 visited for(v=0； v； ++v) visited[v]=FALSE； InitQueue(Q)； //置空的輔助隊列 Q for(v=0； v； ++v) if(!visited[v] ) { //v尚未訪問 visited[v]=TRUE； visit(v)； EnQueue(Q， v)； //v入隊列 while(!QueueEmpty(Q)) { DeQueue(Q， u)； //隊頭元素出隊并置為 u for(w=FirstAdjVex(G,u)。 w=NextAdjVex(G, u, w)) if(!visited[w]) { //w為 u的尚未訪問的鄰接頂點 visited[w]=TURE。 EnQueue(Q,w)。 ? void DFSearch( int v, int s, char *PATH) { // 從第 v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖 G， // 求得一條從 v到 s的簡單路徑，并記錄在 PATH中 visited[v] = TRUE。 //將第 v個頂點添加到路徑 PATH上 for (w=FirstAdjVex(v)。amp。 w=NextAdjVex(v) ) if (w=s) { found = TRUE。 } else if (!visited[w]) DFSearch(w, LP)。 //刪除路徑上最后一個頂點 } 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?利用遍歷圖的算法求解圖的連通性問題 ?最小代價生成樹 ?最小代價生成樹與通信網(wǎng)絡(luò)的經(jīng)濟性 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?無向圖的連通分量和生成樹 ?在對無向圖進行遍歷時 , 對于連通圖，僅需從圖中任一頂點出發(fā)，進行深度優(yōu)先搜索或廣度優(yōu)先搜索，便可訪問到圖中所有頂點。 ?例如，圖 G3是非連通圖，按照其鄰接表進行深度優(yōu)先搜索遍歷，三次調(diào)用 DFS過程 (分別從頂點 A、 D和 G出發(fā) )得到的頂點訪問序列為：ALMJBFC DE GKHI 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?無向圖的連通分量和生成樹 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?生成樹 (a)G4的深度優(yōu)先生成樹 (b)G4的廣度優(yōu)先生成樹 (c)G4 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?非連通圖的生成森林 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?生成非連通圖的深度優(yōu)先生成森林算法 ? void DFSForest (Graph G， CSTree amp。 T=NULL； for( v=0； v； ++v) visited[v]=FALSE； for( v=0； v； ++v) if ( !visited[v]){ //第 v頂點為新的生成樹的根結(jié)點 p=(CSTree)malloc(sizeof(CSNode)) //分配根結(jié)點 *p={ GetVex(G， v)， NULL， NULL }； //給該結(jié)點賦值 if(!T) T = p； //是第一棵生成樹的根 (T的根 ) else q— nextsibling = p 。 //q指示當前生成樹的根 DFSTree(G,v,p)。 ?如何在最節(jié)省經(jīng)費的前提下建立這個通信網(wǎng)。 ?n個城市之間，最多可能設(shè)置 n(n1)/2條線路，那么，如何在這些可能的線路中選擇 n1條，以使總的耗費最少呢 ? 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?最小生成樹 ?分析問題（建立模型） ?可以用連通網(wǎng)來表示 n個城市以及 n個城市間可能設(shè)置的通信線路，其中網(wǎng)的頂點表示城市，邊表示兩城市之間的線路，賦于邊的權(quán)值表示相應(yīng)的代價。 ?要選擇這樣一棵生成樹，也就是使總的耗費最少。 ?一棵生成樹的代價就是樹上各邊的代價之和。其中多數(shù)算法利用了最小生成樹的下列一種簡稱為 MST（ Minimum Spanning Tree）的性質(zhì)： ? 假設(shè) N=(V， {E})是一個連通網(wǎng)， U是頂點集 V的一個非空子集。 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?最小生成樹 ?MST性質(zhì)的證明（反證法） ?假設(shè)網(wǎng) N的任何一棵最小生成樹都不包含 (u ,v)。 ?另一方面，由于 T是生成樹，則在 T上必存在另一條邊 (u’,v’)，其中 u’∈U ， v’∈V U，且 u和 u’之間， v和v’之間均有路徑相通。 ?因為 (u， v)的代價不高 (u’， v’)，則 T’的代價亦不高于 T， T’是包含 (u， v)的一棵最小生成樹。 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?最小生成樹 ?解決方案 ?普里姆 (Prim)算法 ?克魯斯卡爾 (Kruskal)算法 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 7章 圖 圖的連通性問題 ?普里姆 (Prim)算法 求最小生成樹 ?基本思想： ?從連通網(wǎng)絡(luò) N = { V, E }中的某一頂點 u0 出發(fā) , 選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊 ( u0, v ), 將其頂點加入到生成樹頂點集合 U中。如此繼續(xù)下去 , 直到網(wǎng)絡(luò)中的所有頂點都加入到生成樹頂點集合 U 中為止。 k =LocateVex(G， u)； for(j=0； j； ++j) if(j!=k) closedge[j] ={u ,[k][j].adj}。//輸出生成樹的邊 closedge[k].lowcost=0。 j。 }//for }//MiniSpanTree ?普里姆算法的時間復(fù)雜度為 O(n2)，與網(wǎng)中的邊數(shù)無關(guān)，因此適用于求邊 稠密 的網(wǎng)的最小生成樹。 ?在 E中選擇代價最小的邊，若該邊依附的頂點落在 T中不同的連通分量上，則將此邊加入到 T中，否則舍去此邊而選擇下一條代價最小的邊。 ?存儲表示： ?利用最小堆 (MinHeap)和并查集 (DisjointSets) 實現(xiàn)。 ?克魯斯卡爾算法的時間復(fù)雜度為 O(eloge)(e為網(wǎng)中邊的數(shù)目 )，因此它相對于普里姆算法而言，適合于求邊 稀疏 的網(wǎng)的最小生成樹。 ?沒有關(guān)節(jié)點的連通圖叫做 重連通圖 。 ?一個連通圖 G如果不是重連通圖，那么它可以包括幾個重連通分量。 ?在圖中各 頂點旁標明的深度優(yōu)先數(shù) , 給出進行深度優(yōu)先搜索時各頂點訪問的次序。 ?其它頂點 u 是關(guān)節(jié)點的充要條件是它至少有一個子女 w, 從 w 出發(fā) , 不能通過 w、 w 的子孫及一條回邊所組成的路徑到達 u 的祖先。 DAG圖是一類較有向樹更一般的特殊有向圖。 ?幾乎所有的工程 (project)都可分為若干個稱作活動 (activity)的子工程，而這些子工程之間，通常受著一定條件的約束，如其中某些子工程的開始必須在另一些子工程完成之后。 ?偏序： 若集合 X上的關(guān)系 R是自反的、反對稱的和傳遞的，則稱只是集合 X上的偏序關(guān)系。 偏序 ：集合中僅有部分成員之間可比較 全序 ：集合中全體成員之間均可比較 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 7章 圖 有向無環(huán)圖及其應(yīng)用 —— 拓撲排序 ?AOV網(wǎng) (Activity On Vertex Network) ?實際問題： 一個表示偏序的有向圖可用來表示一個流程圖。圖中每一條有向邊表示兩個子工程之間的次序關(guān)系 (領(lǐng)先關(guān)系 )。其中有些課程要求先修課程，有些則不要求。 南昌航空大學(xué)計算機學(xué)院 /軟件學(xué)院 第 7章 圖 有向無環(huán)圖及其應(yīng)用 —— 拓撲排序 C1 高等數(shù)學(xué) C2 程序設(shè)計基礎(chǔ) C3 離散數(shù)學(xué) C C2 C4 數(shù)據(jù)結(jié)構(gòu) C C2 C5 高級語言程序設(shè)計 C2 C6 編譯方法 C C4 C7 操作系統(tǒng)