【正文】 (ed)。 //加入最小生成樹 u = 。 Vmst[u] = true。 //u加入生成樹頂點集合 count++。 break。 } } } while (count n)。 }。 14687 ? 例子 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 H = {(0,5,10), (0,1,28)} ed = (0, 5, 10) Vmst = {t, f, f, f, f, f, f} Vmst = {t, f, f, f, f, t, f} 14688 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 H = {(5,4,25), (0,1,28)} ed = (5, 4, 25) Vmst = {t, f, f, f, f, t, f} Vmst = {t, f, f, f, t, t, f} 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 H = {(4,3,22), (4,6,24), (0,1,28)} ed = (4, 3, 22) Vmst = {t, f, f, f, t, t, f} Vmst = {t, f, f, t, t, t, f} 14689 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 H = {(3,2,12), (3,6,18), (4,6,24), (0,1,28)} ed = (3, 2, 12) Vmst = {t, f, f, t, t, t, f} Vmst = {t, f, t, t, t, t, f} 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 H = {(2,1,16), (3,6,18), (4,6,24), (0,1,28)} ed = (2, 1, 16) Vmst = {t, f, t, t, t, t, f} Vmst = {t, t, t, t, t, t, f} 14690 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 12 H = {(1,6,14), (3,6,18), (4,6,24), (0,1,28)} ed = (1, 6, 14) Vmst = {t, t, t, t, t, t, f} Vmst = {t, t, t, t, t, t, t} ? 最小生成樹中邊集合里存入的各條邊為： (0, 5, 10), (5, 4, 25), (4, 3, 22), (3, 2, 12), (2, 1, 16), (1, 6, 14) 14691 ? prim算法適用于邊稠密的網(wǎng)絡。 ? Kruskal算法不僅適合于邊稠密的情形，也適合于邊稀疏的情形。 ? 注意：當各邊有相同權值時，由于選擇的隨意性，產(chǎn)生的生成樹可能不唯一。 14692 最短路徑 (Shortest Path) ? 最短路徑問題： 如果從圖中某一頂點（稱為源點）另一頂點（稱為終點）的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權值總和達到最小 。 ? 問題解法 ? 邊上權值非負情形的單源最短路徑問題 — Dijkstra算法 ? (僅講此算法 ) ? 邊上權值為任意值的單源最短路徑問題 — Bellman和 Ford算法 ? (不講 ) ? 所有頂點之間的最短路徑 — Floyd算法 ? (不講 ) 14693 邊上權值非負情形的 單源最短路徑問題 ? 問題的提法： 給定一個帶權有向圖 D與源點 v，求從 v到 D中其他頂點的最短路徑。 限定各邊上的權值大于或等于 0。 ? 為求得這些最短路徑 , Dijkstra提出按路徑長度的遞增次序 , 逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點 v到其它各頂點的最短路徑全部求出為止。 14694 Dijkstra逐步求解的過程 源點 終點 最短路徑 路徑長度 v0 v1 (v0,v1) 10 v2 (v0,v1,v2) (v0,v3,v2) ?,60,50 v3 (v0,v3) 30 v4 (v0,v4) (v0,v3,v4) (v0,v3,v2 ,v4) 100,90,60 1 0 4 3 2 10 100 30 50 20 60 10 14695 ? 引入輔助數(shù)組 dist。它的每一個分量 dist[i]表示當前找到的從源點 v0 到終點 vi 的最短路徑的長度。初始狀態(tài)： ? 若從 v0到頂點 vi有邊 , 則 dist[i]為該邊的權值； ? 若從 v0到頂點 vi無邊 , 則 dist[i]為 ? 。 ? 假設 S是已求得的最短路徑的終點的集合，則可證明：下一條最短路徑必然是 從 v0 出發(fā)，中間只經(jīng)過 S中的頂點便可到達的那些頂點 vx (vx?VS )的路徑中的一條。 ? 每次求得一條最短路徑后 , 其終點 vk 加入集合 S，然后對所有的 vi ?VS，修改其 dist[i]值。 14696 Dijkstra算法可描述如下： ① 初始化： S?{v0}。 dist[j]?Edge[0][j], j = 1, 2, …, n1。 // n為圖中頂點個數(shù) ② 求出最短路徑的長度： dist[k]?min {dist[i]}, i?VS 。 S?S∪ {k}。 ③ 修改： dist[i]?min{dist[i], dist[k]+Edge[k][i]}, 對于每一個 i?VS 。 ④ 判斷：若 S = V, 則算法結束，否則轉 ② 。 14697 計算從單個頂點到其他各頂點 最短路徑的算法 void ShortestPath (GraphT, Eamp。 G, T v, E dist[], int path[]) { //Graph是一個帶權有向圖 。 dist[j], 0≤jn, 是當前 //求到的從頂點 v到頂點 j的最短路徑長度 , path[j], //0≤jn, 存放求到的最短路徑。 int n = ()。 bool *S = new bool[n]。 //最短路徑頂點集 int i, j, k。 E w, min。 for (i = 0。 i n。 i++) { dist[i] = (v, i)。 14698 S[i] = false。 if (i != v amp。amp。 dist[i] maxValue) path[i] = v。 else path[i] = 1。 } S[v] = true。 dist[v] = 0。 //頂點 v加入頂點集合 for (i = 0。 i n1。 i++) { //求解各頂點最短路徑 min = maxValue。 int u = v。 //選不在 S中具有最短路徑的頂點 u for (j = 0。 j n。 j++) if (!S[j] amp。amp。 dist[j] min) { u = j。 min = dist[j]。} S[u] = true。 //將頂點 u加入集合 S 14699 for (k = 0。 k n。 k++) { //修改 w = (u, k)。 if (!S[k] amp。amp。 w maxValue amp。amp。 dist[u]+w dist[k]) { //頂點 k未加入 S dist[k] = dist[u]+w。 path[k] = u。 //修改到 k的最短路徑 } } } }。 146100 Dijkstra算法中各輔助數(shù)組的最終結果 從表中讀取源點 0到終點 v的最短路徑的方法 : 舉頂點 4為例 path[4] = 2 path[2] = 3 path[3] = 0，反過來排列，得到路徑 0, 3, 2, 4，這就是源點 0到終點 4的最短路徑。 0 4 1 2 3 10 50 10 20 60 30 100 序號 頂點 1 頂點 2 頂點 3 頂點 4 Dist 10 50 30 60 path 0 3 0 2 146115 活動網(wǎng)絡 (Activity Network) ? 計劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個叫做“活動”的子工程。完成了這些活動，這個工程就可以完成了。 ? 例如，計算機專業(yè)學生的學習就是一個工程，每一門課程的學習就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領先關系，有的課程可以并行地學習。 用頂點表示活動的網(wǎng)絡 (AOV網(wǎng)絡 ) 146116 C1 高等數(shù)學 C2 程序設計基礎 C3 離散數(shù)學 C1, C2 C4 數(shù)據(jù)結構 C3, C2 C5 高級語言程序設計 C2 C6 編譯方法 C5, C4 C7 操作系統(tǒng) C4, C9 C8 普通物理 C1 C9 計算機原理 C8 146117 學生課程學習工程圖 C8 C3 C5 C4 C9 C6 C7 C1 C2 146118 ? 可以用 有向圖 表示一個工程。在這種有向圖中， 用頂點表示活動 ， 用有向邊 Vi, Vj表示活動 Vi 必須先于活動 Vj 進行 。這種有向圖叫做頂點表示活動的 AOV網(wǎng)絡 (Activity On Vertices)。 ? 在 AOV網(wǎng)絡中不能出現(xiàn)有向回路 , 即有向環(huán)。如果出現(xiàn)了有向環(huán)，則意味著某項活動應以自己作為先決條件。 ? 因此，對給定的 AOV網(wǎng)絡，必須先判斷它是否存在有向環(huán)。 146119 ? 檢測有向環(huán)的一種方法是對 AOV網(wǎng)絡