【文章內(nèi)容簡介】 (d) (e) (f)5046132102212504612102514221612325221250n 在構(gòu)造過程中，還設(shè)置了兩個(gè)輔助數(shù)組：u lowcost[ ] 存放生成樹頂點(diǎn)集合內(nèi)頂點(diǎn)到生成樹外各頂點(diǎn)的各邊上的當(dāng)前最小權(quán)值；u nearvex[ ] 記錄生成樹頂點(diǎn)集合外各頂點(diǎn)距離集合內(nèi)哪個(gè)頂點(diǎn)最近 (即權(quán)值最小 )。n 例子50461322810251424221618 1251n 若選擇從頂點(diǎn) 0出發(fā)，即 u0 = 0， 則兩個(gè)輔助數(shù)組的初始狀態(tài)為：n 然后反復(fù)做以下工作：u 在 lowcost [ ]中選擇 nearvex[i] ? 1 amp。amp。 lowcost[i]最小的邊 , 用 v 標(biāo)記它。則選中的權(quán)值最小的邊為 (nearvex[v], v), 相應(yīng)的權(quán)值為 lowcost[v]。 0 28 ? ? ? 10 ? 1 0 0 0 0 0 0 lowcostnearvex0 1 2 3 4 5 652u 將 nearvex[v] 改為 1, 表示它已加入生成樹頂點(diǎn)集合。u 將邊 (nearvex[v], v, lowcost[v] ) 加入生成樹的邊集合。u 取 lowcost[i] = min{ lowcost[i], Edge[v][i] }， 即用生成樹頂點(diǎn)集合外各頂點(diǎn) i 到剛加入該集合的新頂點(diǎn) v 的距離 Edge[v][i] 與原來它們到生成樹頂點(diǎn)集合中頂點(diǎn)的最短距離 lowcost[i] 做比較, 取距離近的作為這些集合外頂點(diǎn)到生成樹頂點(diǎn)集合內(nèi)頂點(diǎn)的最短距離。53u 如果生成樹頂點(diǎn)集合外頂點(diǎn) i 到剛加入該集合的新頂點(diǎn) v 的距離比原來它到生成樹頂點(diǎn)集合中頂點(diǎn)的最短距離還要近，則修改 nearvex[i] : nearvex[i] = v。 表示生成樹外頂點(diǎn) i到生成樹內(nèi)頂點(diǎn) v當(dāng)前距離最近。 0 28 ? ? ? 10 ? 1 0 0 0 0 0 0 lowcostnearvex0 1 2 3 4 5 6選 v=5 選邊 (0,5)54頂點(diǎn) v=5加入生成樹頂點(diǎn)集合：0 28 ? ? 25 10 ? 1 0 0 0 5 1 0 lowcostnearvex0 1 2 3 4 5 6選 v=4 選邊 (5,4)50461322810251424221618原圖 邊 (0,5,10) 加入生成樹1204613210255550 1 2 3 4 5 6頂點(diǎn) v=4加入生成樹頂點(diǎn)集合：0 28 ? 22 25 10 24 1 0 0 4 1 1 4 lowcostnearvex選 v=3 選邊 (4,3)50461322810251424221618原圖 邊 (5,4,25) 加入生成樹12504613210252256頂點(diǎn) v=3加入生成樹頂點(diǎn)集合：0 28 12 22 25 10 18 1 0 3 1 1 1 3 lowcostnearvex0 1 2 3 4 5 6選 v=2 選邊 (3,2)50461322810251424221618原圖 邊 (4,3,22) 加入生成樹1250461321025221257lowcostnearvex0 1 2 3 4 5 6頂點(diǎn) v=2加入生成樹頂點(diǎn)集合：0 16 12 22 25 10 18 1 2 1 1 1 1 3 選 v=1 選邊 (2,1)50461322810251424221618原圖 邊 (3,2,12) 加入生成樹12504132102522161258頂點(diǎn) v=1加入生成樹頂點(diǎn)集合：0 16 12 22 25 10 14 1 1 1 1 1 1 1 lowcostnearvex0 1 2 3 4 5 6選 v=6 選邊 (1,6)50461322810251424221618原圖 邊 (2,1,16) 加入生成樹12504613210251422161259lowcostnearvex0 1 2 3 4 5 6頂點(diǎn) v=6加入生成樹頂點(diǎn)集合：0 16 12 22 25 10 14 1 1 1 1 1 1 1 50461322810251424221618原圖 邊 (1,6,14) 加入生成樹12504613210251422161260最后生成樹中邊集合里存入得各條邊為：(0, 5, 10), (5, 4, 25), (4, 3, 22),(3, 2, 12), (2, 1, 16), (1, 6, 14)利用普里姆算法建立最小生成樹void Prim ( Graph G, MSTamp。 T, int u ) { float * lowcost = new float[NumVertices]。 int * nearvex = new int[NumVertices]。 for ( int i = 0。 i NumVertices。 i++ ) { lowcost[i] = [u][i]。 //Vu到各點(diǎn)代價(jià) nearvex[i] = u。 //及最短帶權(quán)路徑 }61 nearvex[u] = 1。 //加到生成樹頂點(diǎn)集合 int k = 0。 //存放最小生成樹結(jié)點(diǎn)的變量 for ( i = 0。 i 。 i++ ) if ( i != u ) { //循環(huán) n1次 , 加入 n1條邊 EdgeData min = MaxValue。 int v = 0。 for ( int j = 0。 j NumVertices。 j++ ) if ( nearvex[j] != 1 amp。amp。 // =1不參選 lowcost[j] min ) { v = j。 min = lowcost[j]。 } //求生成樹外頂點(diǎn)到生成樹內(nèi)頂點(diǎn)具有最 //小權(quán)值的邊 , v是 當(dāng)前具最小權(quán)值的邊 62 if ( v ) { //v=0表示再也找不到要求頂點(diǎn) T[k].tail = nearvex[v]。 //選邊加入生成樹 T[k].head = v。 T[k++].cost = lowcost[v]。 nearvex[v] = 1。 //該邊加入生成樹標(biāo)記 for ( j = 0。 j 。 j++ ) if ( nearvex[j] != 1 amp。amp。 [v][j] lowcost[j] ) { lowcost[j] = [v][j]。 //修改 nearvex[j] = v。 } } 63 } //循環(huán) n1次 , 加入 n1條邊}n 分析以上算法 , 設(shè)連通網(wǎng)絡(luò)有 n 個(gè)頂點(diǎn) , 則該算法的時(shí)間復(fù)雜度為 O(n2), 它適用于邊稠密的網(wǎng)絡(luò)。n 注意：當(dāng)各邊有相同權(quán)值時(shí)，由于選擇的隨意性，產(chǎn)生的生成樹可能不唯一。當(dāng)各邊的權(quán)值不相同時(shí)，產(chǎn)生的生成樹是唯一 的。 64活動(dòng)網(wǎng)絡(luò) (Activity Network)n 計(jì)劃、施工過程、生產(chǎn)流程、程序流程等都是 “工程 ”。除了很小的工程外，一般都把工程分為若干個(gè)叫做 “活動(dòng) ”的子工程。完成了這些活動(dòng)，這個(gè)工程就可以完成了。n 例如，計(jì)算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門課程的學(xué)習(xí)就是整個(gè)工程的一些活動(dòng)。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學(xué)習(xí)。用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò) (AOV網(wǎng)絡(luò) )65 C1 高等數(shù)學(xué) C2 程序設(shè)計(jì)基礎(chǔ) C3 離散數(shù)學(xué) C1, C2 C4 數(shù)據(jù)結(jié)構(gòu) C3, C2 C5 高級(jí)語言程序設(shè)計(jì) C2 C6 編譯方法 C5, C4 C7 操作系統(tǒng) C4, C9 C8 普通物理 C1 C9 計(jì)算機(jī)原理 C8 課程代號(hào) 課程名稱 先修課程66學(xué)生課程學(xué)習(xí)工程圖