【正文】 點的鄰接點都被訪問到。 圖的遍歷 例如，圖 G6的廣度優(yōu)先搜索遍歷的過程如圖 。 因此，圖 G6的廣度優(yōu)先搜索遍歷序列為 a、 b、 c、 d、 e、 f、 g、h、 i。初始時，將圖中的所有頂點的標志數(shù)組 visited[vi]都初始化為 0，表示頂點未被訪問。然后將 v0入隊，當隊列不為空時，將隊頭元素（頂點）出隊，依次訪問該頂點的所有鄰接點，同時將標志數(shù)組對應位置為1，并將其鄰接點依次入隊。 圖的遍歷 圖的廣度優(yōu)先搜索遍歷的算法實現(xiàn)如下。 ArcNode *p。 /*定義一個隊列 Q*/ front=rear=1。v。 v=0。 /*設置訪問標志為 1，表示已經(jīng)被訪問過 */ Visit([v].data)。 圖的遍歷 queue[rear]=v。 v=queue[front]。 while(p!=NULL) /*遍歷序號為 v的所有鄰接點 */ { if(visited[padjvex]==0) /*如果該頂點未被訪問過 */ { visited[padjvex]=1。 rear=(rear+1)%MaxSize。 } p=pnextarc。 圖的連通性問題 無向圖的連通分量與最小生成樹 在對無向圖進行遍歷時，對于連通圖，僅需從圖的任何一個頂點出發(fā)，進行深度優(yōu)先搜索或廣度優(yōu)先搜索，就可訪問到圖中的所有頂點。 圖的連通性問題 圖 G3的鄰接表如圖 。對圖 G3進行深度遍歷，經(jīng)過 3次遞歸調用得到的 3個序列分別為：（ 1） a、 b、c、 d、 m、 e、 f；（ 2） g、 h；（ 3） i、 j、 k、 l。 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） 是遍歷圖過程中經(jīng)過的邊的集合 ， B（ G） 是剩余邊的集合 。 由深度優(yōu)先搜索得到的為深度優(yōu)先生成樹對于連通圖 ， 由廣度優(yōu)先搜索得到的為廣度優(yōu)先生成樹 。 adbgcefhi圖 G6的 深 度 優(yōu) 先 生 成 樹adbgcefhi圖 G6的 廣 度 優(yōu) 先 生 成 樹 圖的連通性問題 對于非連通圖 ， 從某一個頂點出發(fā) ， 對圖進行深度優(yōu)先搜索遍歷或者廣度優(yōu)先搜遍歷 ， 按照訪問路徑會得到若干棵生成樹 ， 這些生成樹放在一起就構成了森林 。 a bd cfmjikeglh 圖的連通性問題 最小生成樹 許多應用問題都是一個求無向連通圖的最小生成樹問題。 在每兩個城市之間都可以鋪設光纜， n個城市之間，最多可能鋪設 n(n1)/2條光纜，但鋪設光纜的費用很高，且各個城市之間鋪設光纜的費用不同，那么，如何在這些可能的線路中選擇 n1條，以使總的費用最少呢？ 圖的連通性問題 用連通網(wǎng)來表示 n個城市及 n個城市間可能鋪設的光纜，其中網(wǎng)的頂點表示城市，邊表示兩個城市之間的光纜線路，賦予邊的權值表示相應的造價?，F(xiàn)在，我們要選擇一條這樣一棵生成樹，也就是使總的造價最少。其中一棵生成樹的代價就是樹上所有邊的代價之和。 最小生成樹有多種算法，其中大多數(shù)算法都利用了最小生成樹的簡稱為 MST性質： 假設一個連通網(wǎng) N=(V,E)， V是頂點的集合， E是邊的集合， V有一個非空子集 U。 圖的連通性問題 下面用反證法證明以上 MST性質。設 T是連通網(wǎng) N中的一棵最小生成樹，如果將邊 (u,v)加入到 T中，根據(jù)生成樹的定義， T一定出現(xiàn)包含 (u,v)的回路。 T’是包含邊 (u,v)的最小生成樹，這與假設矛盾。 圖的連通性問題 普里姆（ prim）算法和克魯斯卡爾（ kruskal）算法就是利用MST性質構造的最小生成樹算法。執(zhí)行以下操作： （ 1）初始時，令 U={u0}(u0∈ V)， TE=。 （ 3）重復執(zhí)行步驟（ 2），直到 U=V為止。 圖的連通性問題 例如，圖 。 只有一個元素 a∈ U， 將 a從 U中取出 ， 比較頂點 a與集合 VU中頂點構成的代價最小邊 ， 在 (a,b)、 (a,c)、 (a,d)中 ， (a,c)的權值最小 ，故將頂點 c加入到集合 U中 ， 邊 (a,c)加入到 TE中 ， 此時有 U={a,c}，VU={b,d,e,f}， TE=={(a,c)}。 依次類推 ， 直到所有的頂點都加入到 U中 。對于每個頂點 v∈ VU，在輔助數(shù)組中存在一個相應分量 closeedge[v]，它包括兩個域 adjvex和lowcost，其中， adjvex域用來表示該邊中屬于 U中的頂點，lowcost域存儲該邊對應的權值。 分析：主要考察普里姆算法生成網(wǎng)的最小生成樹算法。其中， adjvex域用來存放依附于集合 U的頂點， lowcost域用來存放數(shù)組下標對應的頂點到頂點 (adjvex中的值 )的最小權值。依次類推，直到所有的頂點都加入到集合 U中。在 MiniSpanTree_PRIM算法中，先確定集合 U的元素，即出發(fā)頂點，代碼如下： k=LocateVex(G,u)。例如，當u=’a’時，有 k=0，初始化后， closedge數(shù)組的值如圖 (1)所示，代碼如下。j。 closedge[j].lowcost=[k][j].adj。 // 初始時 ,U={u} 圖的連通性問題 調用函數(shù) MiniNum求代價最小的邊， k為終結點的序號，例如，圖 N第一條代價最小的邊為 (a,c)，則有 k=2，所以 closedge[2].adjvex為 ’ a’， [2]為 ’ c’，輸出 (a,c)，并將第 k個頂點加入 U集。 for(i=1。++i) { // 選擇其余 k=MiniNum(closedge,G)。 // 輸出生成樹的邊 closedge[k].lowcost=0。 for(j=0。++j) if([k][j].adjclosedge[j].lowcost) { // 新頂點并入 U集后重新選擇最小邊 strcpy(closedge[j].adjvex,[k])。 } } 圖的連通性問題 數(shù)組 closedge的 adjvex域和 lowcost域的變化情況如圖 。在 E中選擇代價最小的邊，若該邊依附的頂點落在 T中不同的連通分量中，則將此邊加入到 T中，否則舍去此邊而選擇下一條代價最小的邊。 例如，圖 N利用卡魯斯卡爾算法構造最小生成樹的過程如圖 。若用圖的頂點表示活動，用弧表示活動之間的優(yōu)先關系的有向無環(huán)圖稱為 AOV網(wǎng)（ activity on vertex work），即頂點表示活動的網(wǎng)。若 vi,vj是有向網(wǎng)的一條弧，則稱頂點 vi是頂點 vj的直接前驅，頂點 vj是頂點 vi的直接后繼。這些先決條件定義了課程之間的優(yōu)先次序。 表 軟件工程專業(yè)課程關系表 課 程 編 號課 程 名 稱先 修 課 程 編 號C1C2C3C4C5C6C7C8高 等 數(shù) 學程 序 設 計 基 礎離 散 數(shù) 學數(shù) 據(jù) 結 構算 法 設 計 與 分 析普 通 物 理計 算 機 組 成 原 理操 作 系 統(tǒng)編 譯 原 理線 性 代 數(shù)C9C1 0無無C1C2, C3C4, C7C6C1C1, C2C4, C5C2, C4 有向無環(huán)圖 這些課程之間的關系用有向圖可以更清楚的表示 ， 如圖 示 。 C2C3C5C4C9C7C8C6C1 0C1 有向無環(huán)圖 2．拓撲排序 拓撲排序的方法如下： （ 1）在有向圖中任意選擇一個沒有前驅的頂點即頂點入度為零，將該頂點輸出； （ 2）從圖中刪除該頂點和所有以它為尾的??； （ 3）重復執(zhí)行步驟（ 1）和（ 2），直至所有頂點均已被輸出，或者當前 圖中不存在無前驅的頂點為止（說明有向圖中存在環(huán)）。其拓撲序列為： VV V V V V6。如整個工程的最短完成時間、各個子工程影響整個工程的程度、每個子工程的最短完成時間和最長完成時間，都需要利用 AOE網(wǎng)的相關知識來解決，通過研究事件與活動之間的關系，從而可以確定整個工程的最短完成時間，明確活動之間的相互影響，確保整個工程的順利進行。 AOE網(wǎng)是一個帶權的有向無環(huán)圖，其中，頂點表示事件（ event），弧表示活動，權表示活動持續(xù)的時間，權值表示子工程的活動需要的時間。 有向無環(huán)圖 圖 11個活動的 AOE網(wǎng) ， 其中 v1， v2， … ， v9表示 9個事件 ， v1,v2， v1,v3， … ， v8,v9表示 11個活動 ，a1， a2， … ， a11表示活動的執(zhí)行時間 。 頂點 v1表示整個工程的開始 ， v9表示整個工程的結束 。 完成活動 a1和活動 a2分別需要6天和 4天 。最長的路徑就是關鍵路徑（ critical path）。關鍵路徑表示了完成工程的最短工期。求解 ve(i)可以從源點 ve(0)=0開始，按照拓撲排序規(guī)則根據(jù)遞推得到： ve(i)=Max{ve(k)+dut(k,i)|k,i∈ T,1≤i≤n1} 其中， T是所有以第 i個頂點為弧頭的弧的集合， dut(k,i)表示弧 k,i對應的活動的持續(xù)時間。如圖。在求解事件 vi的最早發(fā)生時間 ve(i)的前提 vl(n1)=ve(n1)下，從匯點開始，向源點推進得到 vl(i)： vl(i)=Min{vl(k)dut(i,k)|i,k∈ S,0≤i≤n2} 其中， S是所有以第 i個頂點為弧尾的弧的集合， dut(i,k)表示弧 i,k對應的活動的持續(xù)時間。因此，事件 vk的最早發(fā)生時間也就是活動 ai的最早開始時間，即 e(i)=ve(k)。 如果弧 vk,vj表示活動 ai，持續(xù)時間為 dut(k,j)， 則活動 ai的最晚開始時間 l(i)=vl(j)dut(k,j)。 如圖 。 V1V2V3V5V4V8a1= 6a2= 4a3= 5a4= 1a5= 1a6= 2a8= 7V6a9= 4最 晚 開 始 時 間 為 1 4活 動 a8的 持 續(xù) 時 間 為 7a8的 最 晚 開 始 時 間 為 1 4 7 = 7 有向無環(huán)圖 求關鍵路徑的算法如下： （ 1）對網(wǎng)中的頂點進行拓撲排序，如果得到的拓撲序列頂點個數(shù)小于網(wǎng)中頂點數(shù)，則說明網(wǎng)中有環(huán)存在，不能求關鍵路徑，終止算法。 （ 2）從匯點 vn出發(fā) vl(n1)=ve(n1)，按照逆拓撲序列求其它頂點的最晚發(fā)生時間 vl(i)。 （ 4）找出所有滿足條件 e(i)=l(i)的活動 ai， ai即是關鍵活動。 V7a7= 9a1 0= 2 頂 點 v e v l 活 動 e l l ev1v2v3v4v5v6v