【正文】 ces； int vexnum， arum； //圖的當前頂點數(shù)和弧數(shù) int kind； //圖的種類標志 }ALGraph； 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的存儲結構 ?圖的十字鏈表表示法： ?(Orthogonal List) 可看成將 有向圖 的鄰接表和逆鄰接表結合起來得到的一種鏈表。在某些圖的應用問題中需要對邊進行某種操作，如對已被搜索過的邊作記號或刪除一條邊等，此時需要找到表示同一條邊的兩個結點。 ?圖的遍歷算法是求解圖的連通性問題、拓撲排序和求關鍵路徑等算法的基礎。 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的遍歷 ?圖的深度優(yōu)先搜索 ?(DepthFirst Search)－－類似于樹的先根遍歷； ?假設初始狀態(tài)是圖中所有頂點未曾被訪問，則深度優(yōu)先搜索可從圖中某個頂點 v出發(fā)，訪問此頂點，然后依次從 v的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和 v有路徑相通的頂點都被訪問到； ?若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。 //使用全局變量 VisitFunc，使 DFS不必設函數(shù) 指針參數(shù) for(v=0； v； ++v) visited[v]=FALSE。 ?假設從圖中某頂點 v出發(fā)，在訪問 v之后依次訪問 v的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使 “ 先被訪問的頂點的鄰接點 ” 先于 “ 后被訪問的頂點的鄰接點 ” 被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。 w=NextAdjVex(G, u, w)) if(!visited[w]) { //w為 u的尚未訪問的鄰接頂點 visited[w]=TURE。 ? void DFSearch( int v, int s, char *PATH) { // 從第 v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖 G， // 求得一條從 v到 s的簡單路徑，并記錄在 PATH中 visited[v] = TRUE。amp。 } else if (!visited[w]) DFSearch(w, LP)。 ?例如，圖 G3是非連通圖，按照其鄰接表進行深度優(yōu)先搜索遍歷，三次調(diào)用 DFS過程 (分別從頂點 A、 D和 G出發(fā) )得到的頂點訪問序列為：ALMJBFC DE GKHI 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?無向圖的連通分量和生成樹 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?生成樹 (a)G4的深度優(yōu)先生成樹 (b)G4的廣度優(yōu)先生成樹 (c)G4 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?非連通圖的生成森林 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?生成非連通圖的深度優(yōu)先生成森林算法 ? void DFSForest (Graph G， CSTree amp。 //q指示當前生成樹的根 DFSTree(G,v,p)。 ?n個城市之間，最多可能設置 n(n1)/2條線路，那么，如何在這些可能的線路中選擇 n1條，以使總的耗費最少呢 ? 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?最小生成樹 ?分析問題（建立模型） ?可以用連通網(wǎng)來表示 n個城市以及 n個城市間可能設置的通信線路，其中網(wǎng)的頂點表示城市，邊表示兩城市之間的線路，賦于邊的權值表示相應的代價。 ?一棵生成樹的代價就是樹上各邊的代價之和。 南昌航空大學計算機學院 /軟件學院 第 7章 圖 圖的連通性問題 ?最小生成樹 ?MST性質(zhì)的證明（反證法） ?假設網(wǎng) N的任何一棵最小生成樹都不包含 (u ,v)。 ?因為 (u， v)的代價不高 (u’， v’)，則 T’的代價亦不高于 T， T’是包含 (u， v)的一棵最小生成樹。如此繼續(xù)下去 , 直到網(wǎng)絡中的所有頂點都加入到生成樹頂點集合 U 中為止。//輸出生成樹的邊 closedge[k].lowcost=0。 }//for }//MiniSpanTree ?普里姆算法的時間復雜度為 O(n2)，與網(wǎng)中的邊數(shù)無關，因此適用于求邊 稠密 的網(wǎng)的最小生成樹。 ?存儲表示： ?利用最小堆 (MinHeap)和并查集 (DisjointSets) 實現(xiàn)。 ?沒有關節(jié)點的連通圖叫做 重連通圖 。 ?在圖中各 頂點旁標明的深度優(yōu)先數(shù) , 給出進行深度優(yōu)先搜索時各頂點訪問的次序。 DAG圖是一類較有向樹更一般的特殊有向圖。 ?偏序： 若集合 X上的關系 R是自反的、反對稱的和傳遞的，則稱只是集合 X上的偏序關系。圖中每一條有向邊表示兩個子工程之間的次序關系 (領先關系 )。 南昌航空大學計算機學院 /軟件學院 第 7章 圖 有向無環(huán)圖及其應用 —— 拓撲排序 C1 高等數(shù)學 C2 程序設計基礎 C3 離散數(shù)學 C C2 C4 數(shù)據(jù)結構 C C2 C5 高級語言程序設計 C2 C6 編譯方法 C C4 C7 操作系統(tǒng) C C9 C8 普通物理 C1 C9 計算機原理 C8 課程代號 課程名稱 先修課程 ?AOV網(wǎng) (Activity On Vertex Network) ?計算機專業(yè)學生學習的課程 南昌航空大學計算機學院 /軟件學院 第 7章 圖 有向無環(huán)圖及其應用 —— 拓撲排序 ?AOV網(wǎng) (Activity On Vertex Network) ?計算機專業(yè)學生學習的課程 學生課程學習工程圖 C8 C3 C5 C4 C9 C6 C7 C1 C2 南昌航空大學計算機學院 /軟件學院 第 7章 圖 有向無環(huán)圖及其應用 —— 拓撲排序 ?AOV網(wǎng) (Activity On Vertex Network) ?AOV網(wǎng)： 在有向圖中，用頂點表示活動，用有向邊 Vi, Vj表示活動 Vi必須先于活動 Vj 進行。 ?這種構造 AOV網(wǎng)絡全部頂點的拓撲有序序列的運算就叫做拓撲排序。說明圖中還剩下一些頂點 , 它們都有直接前驅。 ?為了避免重復檢測入度為零的頂點，可另設一棧暫存所有入度為零的頂點。 南昌航空大學計算機學院 /軟件學院 第 7章 圖 有向無環(huán)圖及其應用 —— 關鍵路徑 ?AOE網(wǎng) (Activity On Edge) ?邊表示活動的網(wǎng)。 ?關鍵路徑 (Critical Path)：完成整個工程所需的時間取決于從源點到匯點的最長路徑長度 , 即在這條路徑上所有活動的持續(xù)時間之和。 ?事件 Vi的 最遲允許開始時間 Vl[i]：保證匯點 Vn1在 Ve[n1]時刻完成的前提下，事件 Vi允許的最遲開始時間。 ?時間余量 l[k]e[k]： 表示活動 ak 的最早可能開始時間和最遲允許開始時間的時間余量。 ?求 Ve[i]的遞推公式 ?從 Ve[0] = 0 開始，向前遞推 Vj, Vi ? S2, i = 1, 2, ? , n1 S2 是所有指向 Vi 的有向邊 Vj , Vi 的集合。 南昌航空大學計算機學院 /軟件學院 第 7章 圖 有向無環(huán)圖及其應用 —— 關鍵路徑 Ve Vl 1 2 3 4 5 6 7 8 0 8 12 22 28 40 46 58 0 8 12 22 28 40 46 58 e l 0 0 8 12 12 22 22 28 40 46 0 0 8 12 12 32 22 28 40 46 1 2 3 4 5 6 7 8 9 10 a9=6 1 3 2 4 a1=8 a2=12 5 6 7 8 a10=12 a8=18 a5=28 a6=8 a7=6 a3=14 a4=10 南昌航空大學計算機學院 /軟件學院 第 7章 圖 最短路徑 ?問題背景 ?假若要在計算機上建立一個交通咨詢系統(tǒng)則可以采用圖的結構來表示實際的交通網(wǎng)絡。 ?最短路徑問題： 如果從圖中某一頂點（稱為源點）出發(fā)到達另一頂點（稱為終點）的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊的權值總和達到最小。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點 v到其它各頂點的最短路徑全部求出為止。 ?每次求得一條最短路徑后，其終點 vk加入集合 S，然后對所有的 vi?VS，修改其 dist[i]值。 S ← S U { k }。P，ShortPathTable amp。 for(v=0； v； ++v) { final[v]=FALSE； D[v]=[v0][v]； for(w=0； w； ++w) P[v][w] = FALSE； //設空路徑 if (D[v]INFINITY) { P[v][v0]=TRUE； P[v][v]=TRUE； } }//for 南昌航空大學計算機學院 /軟件學院 第 7章 圖 最短路徑 ?Dijkstra算法 ? D[v0] = 0； final[v0] = TRUE； //初始化， v0頂點屬于 S集 //開始主循環(huán)，每次求得 v0到某個 v頂點的最短路徑，并加 v到 s集。(min+[v][w]D[w])){ //修改 D[w]和 P[w] D[w]=min+[v][w]； P[w]=P[v]； P[w][w]=TRUE； //P[w]=P[v]+[w] }//if }//for }//ShortestPath_DIJ 南昌航空大學計算機學院 /軟件學院 第 7章 圖 最短路徑 ?Dijkstra算法分析 ?第一個 FOR循環(huán)的時間復雜度是 O(n)，第二個 FOR循環(huán)共進行 n1次，每次執(zhí)行的時間是 O(n)。程序加上適當