【正文】 146119 ? 檢測有向環(huán)的一種方法是對 AOV網(wǎng)絡(luò)構(gòu)造它。如果出現(xiàn)了有向環(huán)，則意味著某項活動應(yīng)以自己作為先決條件。這種有向圖叫做頂點表示活動的 AOV網(wǎng)絡(luò) (Activity On Vertices)。 用頂點表示活動的網(wǎng)絡(luò) (AOV網(wǎng)絡(luò) ) 146116 C1 高等數(shù)學(xué) C2 程序設(shè)計基礎(chǔ) C3 離散數(shù)學(xué) C1, C2 C4 數(shù)據(jù)結(jié)構(gòu) C3, C2 C5 高級語言程序設(shè)計 C2 C6 編譯方法 C5, C4 C7 操作系統(tǒng) C4, C9 C8 普通物理 C1 C9 計算機原理 C8 146117 學(xué)生課程學(xué)習(xí)工程圖 C8 C3 C5 C4 C9 C6 C7 C1 C2 146118 ? 可以用 有向圖 表示一個工程。其中有些課程要求先修課程，有些則不要求。完成了這些活動，這個工程就可以完成了。 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)絡(luò) (Activity Network) ? 計劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。 //修改到 k的最短路徑 } } } }。 dist[u]+w dist[k]) { //頂點 k未加入 S dist[k] = dist[u]+w。 w maxValue amp。 if (!S[k] amp。 k n。} S[u] = true。 dist[j] min) { u = j。 j++) if (!S[j] amp。 //選不在 S中具有最短路徑的頂點 u for (j = 0。 i++) { //求解各頂點最短路徑 min = maxValue。 //頂點 v加入頂點集合 for (i = 0。 } S[v] = true。 dist[i] maxValue) path[i] = v。 if (i != v amp。 i++) { dist[i] = (v, i)。 for (i = 0。 //最短路徑頂點集 int i, j, k。 int n = ()。 G, T v, E dist[], int path[]) { //Graph是一個帶權(quán)有向圖 。 ④ 判斷：若 S = V, 則算法結(jié)束，否則轉(zhuǎn) ② 。 S?S∪ {k}。 dist[j]?Edge[0][j], j = 1, 2, …, n1。 ? 每次求得一條最短路徑后 , 其終點 vk 加入集合 S，然后對所有的 vi ?VS，修改其 dist[i]值。初始狀態(tài)： ? 若從 v0到頂點 vi有邊 , 則 dist[i]為該邊的權(quán)值； ? 若從 v0到頂點 vi無邊 , 則 dist[i]為 ? 。 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。 ? 為求得這些最短路徑 , Dijkstra提出按路徑長度的遞增次序 , 逐步產(chǎn)生最短路徑的算法。 ? 問題解法 ? 邊上權(quán)值非負情形的單源最短路徑問題 — Dijkstra算法 ? (僅講此算法 ) ? 邊上權(quán)值為任意值的單源最短路徑問題 — Bellman和 Ford算法 ? (不講 ) ? 所有頂點之間的最短路徑 — Floyd算法 ? (不講 ) 14693 邊上權(quán)值非負情形的 單源最短路徑問題 ? 問題的提法： 給定一個帶權(quán)有向圖 D與源點 v，求從 v到 D中其他頂點的最短路徑。 ? 注意：當(dāng)各邊有相同權(quán)值時，由于選擇的隨意性，產(chǎ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)絡(luò)。 } } } while (count n)。 //u加入生成樹頂點集合 count++。 //加入最小生成樹 u = 。 count n) { (ed)。 14686 } while (!() amp。 (ed)。 = v。 do { //迭代 v = (u)。 Vmst[u] = true。 i n。 //最小堆 14685 bool Vmst = new bool[n]。 //邊數(shù) int u = (u0)。 int n = ()。 MST) { MSTEdgeNodeT, E ed。 14683 25 25 10 5 0 4 6 1 3 2 28 10 25 14 24 22 16 18 5 0 4 6 1 3 2 5 0 4 6 1 3 2 10 原圖 (a) (b) 5 0 4 6 1 3 2 10 (c) (d) (e) (f) 5 0 4 6 1 3 2 10 22 12 5 0 4 6 1 2 10 25 14 22 16 12 3 25 22 12 14684 Prim算法的實現(xiàn) include template class T, class E void Prim (GraphT, Eamp。 將新選出的邊從 E中剔除： E = E{(u, v)}。 E不空 ) { 從 E中選一條邊 (u, v), u?Vmst∩ v?VVmst, 且具有最小代價 (cost)。 while (Vmst包含的頂點少于 n amp。 14682 普里姆 (Prim)的偽代碼描述 選定構(gòu)造最小生成樹的出發(fā)頂點 u0。 以后每一步從一個頂點在集合 U中 , 而另一個頂點不在集合 U中的各條邊中選擇權(quán)值最小的邊 (u, v), 把它的頂點加入到 集合 U中。 //該邊存入 MST count++。 //取兩頂點所在集合的根 u與 v if (u != v) { //不是同一集合 ,不連通 (u, v)。 //退出具最小權(quán)值的邊 u = ()。 } 14679 count = 1。 //插入堆 = (u, v)。 v++) if ((u,v) != maxValue) { = u。 u++) for (v = u+1。 //并查集 for (u = 0。 //邊數(shù) MinHeap MSTEdgeNodeT, E H(m)。 int n = ()。 MST) { Kruskal算法的實現(xiàn) 14