數(shù)據(jù)結(jié)構(gòu)：第5章 圖2

1、1數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 第五章第五章 圖圖5.1 基本概念基本概念5.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)5.3 圖的遍歷圖的遍歷5.4 拓?fù)渑判蛲負(fù)渑判?.5 關(guān)鍵路徑關(guān)鍵路徑 5.6 最短路徑最短路徑5.7 最小支撐樹(shù)最小支撐樹(shù)5.8 圖的應(yīng)用圖的應(yīng)用2數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-75.5.1 基本概念基本概念 邊表示活動(dòng)邊表示活動(dòng)(Activity) 邊的權(quán)值表示活動(dòng)的持續(xù)時(shí)間邊的權(quán)值表示活動(dòng)的持續(xù)時(shí)間(Duration) 頂點(diǎn)表示入邊的活動(dòng)已完成，出邊的活動(dòng)可以開(kāi)始的狀頂點(diǎn)表示入邊的活動(dòng)已完成，出邊的活動(dòng)可以開(kāi)始的狀態(tài)，也稱(chēng)為事件態(tài)，也稱(chēng)為事件(Event) 這樣的這

2、樣的有向無(wú)環(huán)的帶權(quán)圖有向無(wú)環(huán)的帶權(quán)圖叫做叫做AOE (Activity On Edges)網(wǎng)。網(wǎng)。3數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7例例 某工程某工程l源點(diǎn)：源點(diǎn)：表示整個(gè)工程的開(kāi)始（入度為零）。表示整個(gè)工程的開(kāi)始（入度為零）。l匯點(diǎn)：匯點(diǎn)：表示整個(gè)工程的結(jié)束（出度為零）。表示整個(gè)工程的結(jié)束（出度為零）。l完成整個(gè)工程至少需要多少時(shí)間？完成整個(gè)工程至少需要多少時(shí)間？l為縮短工程的時(shí)間，應(yīng)當(dāng)加快哪些活動(dòng)？為縮短工程的時(shí)間，應(yīng)當(dāng)加快哪些活動(dòng)？325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)匯點(diǎn)源點(diǎn)源點(diǎn)4數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程20

3、21-12-7l從源點(diǎn)到各頂點(diǎn)的路徑可能不止一條，路徑長(zhǎng)度也可能不同。只從源點(diǎn)到各頂點(diǎn)的路徑可能不止一條，路徑長(zhǎng)度也可能不同。只有各條路徑上所有活動(dòng)都完成了，整個(gè)工程才算完成。有各條路徑上所有活動(dòng)都完成了，整個(gè)工程才算完成。l因此，因此，完成整個(gè)工程所需的時(shí)間取決于從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑完成整個(gè)工程所需的時(shí)間取決于從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑長(zhǎng)度長(zhǎng)度，即在這條路徑上所有活動(dòng)的持續(xù)時(shí)間之和。，即在這條路徑上所有活動(dòng)的持續(xù)時(shí)間之和。這條路徑長(zhǎng)度這條路徑長(zhǎng)度最長(zhǎng)的路徑就叫做關(guān)鍵路徑。最長(zhǎng)的路徑就叫做關(guān)鍵路徑。l路徑長(zhǎng)度路徑長(zhǎng)度：指路徑上的各邊權(quán)值之和。：指路徑上的各邊權(quán)值之和。l關(guān)鍵活動(dòng)關(guān)鍵活動(dòng)：關(guān)鍵路徑

4、上的活動(dòng)：關(guān)鍵路徑上的活動(dòng)。3 32 25 51 14 40 08 86 67 7a1=6a8=7a7=9a6=2a4=1a a5 5=1=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)匯點(diǎn)源點(diǎn)源點(diǎn)5數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 關(guān)鍵活動(dòng)有關(guān)的量：關(guān)鍵活動(dòng)有關(guān)的量： 事件事件vj的最早發(fā)生時(shí)間的最早發(fā)生時(shí)間ve(j): 從源點(diǎn)從源點(diǎn)v0到到vj的最長(zhǎng)路徑長(zhǎng)度。的最長(zhǎng)路徑長(zhǎng)度。 事件事件vj的最遲發(fā)生時(shí)間的最遲發(fā)生時(shí)間vl(j):保證匯點(diǎn)的最早發(fā)生時(shí)間不推遲的前提下，事件保證匯點(diǎn)的最早發(fā)生時(shí)間不推遲的前提下，事件vj允許的最遲允許的最遲開(kāi)始時(shí)間，等于開(kāi)始時(shí)間，等于ve(n-1)減去

5、從減去從vj到到vn-1最長(zhǎng)路徑長(zhǎng)度。最長(zhǎng)路徑長(zhǎng)度。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)匯點(diǎn)源點(diǎn)源點(diǎn)6數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 ve(0)=0ve(1)= 6ve(2)= 4ve(3)= 5ve(4)= 7ve(5)= 7ve(6)= 16ve(7)= 14ve(8)= 18vl(8)= 18vl(7)= 14vl(6)= 16vl(5)= 10vl(4)= 7vl(3)= 8vl(2)= 6vl(1)= 6vl(0)= 07數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 關(guān)鍵活動(dòng)有關(guān)的量：關(guān)鍵活動(dòng)有關(guān)的量：

6、活動(dòng)活動(dòng)ai的最早開(kāi)始時(shí)間的最早開(kāi)始時(shí)間e(i): 設(shè)活動(dòng)設(shè)活動(dòng)ai在有向邊在有向邊上上, e(i)是從源是從源 點(diǎn)點(diǎn)v0到到vj的最長(zhǎng)路徑長(zhǎng)度。因此的最長(zhǎng)路徑長(zhǎng)度。因此e(i)=ve(j)。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)匯點(diǎn)源點(diǎn)源點(diǎn)8數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 關(guān)鍵活動(dòng)有關(guān)的量：關(guān)鍵活動(dòng)有關(guān)的量： 活動(dòng)活動(dòng)ai的最遲開(kāi)始時(shí)間的最遲開(kāi)始時(shí)間l(i): l(i) 是在不會(huì)引起時(shí)間延誤的前提下，該活動(dòng)允許的是在不會(huì)引起時(shí)間延誤的前提下，該活動(dòng)允許的最遲開(kāi)始時(shí)間。設(shè)活動(dòng)最遲開(kāi)始時(shí)間。設(shè)活動(dòng)ai在有向邊在有

7、向邊上上, 則則 l(i)= vl(k)-weight()325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)匯點(diǎn)源點(diǎn)源點(diǎn)9數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 aie(i)l(i) 0 0 0 6 4 5 7 7 7 0 0 0 6 4 5 7 7 7 16 14 16 14 0 2 3 6 6 8 7 7 0 2 3 6 6 8 7 7 1010 16 14 16 14 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 10數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 關(guān)鍵活動(dòng)：關(guān)鍵活動(dòng)： l(i) e(i) 表

8、示活動(dòng)表示活動(dòng)ak 是沒(méi)有時(shí)間余量的關(guān)鍵活是沒(méi)有時(shí)間余量的關(guān)鍵活動(dòng)。動(dòng)。325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)匯點(diǎn)源點(diǎn)源點(diǎn)為找出關(guān)鍵活動(dòng)為找出關(guān)鍵活動(dòng), 需要求各個(gè)活動(dòng)的需要求各個(gè)活動(dòng)的 e(i) 與與 l(i)，以判，以判別是否別是否 l(i) e(i) 為求得為求得e(i) 與與 l(i)，需要先求得從源點(diǎn)，需要先求得從源點(diǎn)V0到各個(gè)頂點(diǎn)到各個(gè)頂點(diǎn)Vj 的的 ve(j) 和和 vl(j)。11數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7求關(guān)鍵活動(dòng)算法求關(guān)鍵活動(dòng)算法求關(guān)鍵活動(dòng)的基本步驟：求關(guān)鍵活動(dòng)的基本步驟：對(duì)對(duì)AOE網(wǎng)進(jìn)

9、行拓?fù)渑判颍赐負(fù)浯涡蚯蟪龈黜旤c(diǎn)事件的最早網(wǎng)進(jìn)行拓?fù)渑判?，按拓?fù)浯涡蚯蟪龈黜旤c(diǎn)事件的最早發(fā)生時(shí)間發(fā)生時(shí)間ve，若網(wǎng)中有回路，則終止算法；，若網(wǎng)中有回路，則終止算法； 按拓?fù)湫蛄械哪嫘蚯蟾黜旤c(diǎn)事件的最遲發(fā)生時(shí)間按拓?fù)湫蛄械哪嫘蚯蟾黜旤c(diǎn)事件的最遲發(fā)生時(shí)間vl;根據(jù)根據(jù)ve和和vl的值，求各活動(dòng)的最早開(kāi)始時(shí)間的值，求各活動(dòng)的最早開(kāi)始時(shí)間e(i)與最遲開(kāi)始時(shí)與最遲開(kāi)始時(shí)間間l(i)，若，若e(i)=l(i)，則，則i是是關(guān)鍵活動(dòng)關(guān)鍵活動(dòng)。12數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 例例 求關(guān)鍵活動(dòng)求關(guān)鍵活動(dòng) 第1步ve(k)ve(0)0 k=0maxve(j)+ weight() E(G), k=1,

10、 2, , n-1325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)匯點(diǎn)源點(diǎn)源點(diǎn)13數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 ve(0)=0ve(1)= ve(0)+weight()=0+6=6ve(2)= ve(0)+weight()=0+4=4ve(3)= ve(0)+weight()=0+5=5ve(4)= maxve(1)+ weight()， ve(2)+ weight()=max6+1,4+1=7ve(5)= ve(3)+weight()=5+2=7ve(6)= ve(4)+weight()=7+9=16ve(7)= m

11、axve(4)+ weight()， ve(5)+ weight()=max7+7,7+4=14ve(8)= maxve(6)+ weight()， ve(7)+ weight()=max16+2,14+4=1814數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 例例 求關(guān)鍵活動(dòng)求關(guān)鍵活動(dòng) 第2步vl(j)ve(n-1) j=n-1minvl(k)- weight() E(G), j= n-2, n-3,0325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)匯點(diǎn)源點(diǎn)源點(diǎn)15數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 vl(8)= ve(8)=1

12、8vl(7)= vl(8)-weight()=18-4=14vl(6)= vl(8)-weight()=18-2=16vl(5)= vl(7)-weight()=14-4=10vl(4)= minvl(7)- weight()， vl(6)- weight() =min14-7,16-9=7vl(3)= vl(5)-weight()=10-2=8vl(2)= vl(4)-weight()=7-1=6vl(1)= vl(4)-weight()=7-1=6vl(0)= minvl(1)- weight()， vl(2)- weight(), vl(3)- weight() = min6-6,6-4

13、,8-5=016數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 aie(i)l(i)li-ei 0 0 0 6 4 5 7 7 7 0 0 0 6 4 5 7 7 7 16 14 16 14 0 2 3 6 6 8 7 7 0 2 3 6 6 8 7 7 1010 16 14 16 14 0 0 2 3 2 3 0 0 2 3 2 3 0 0 0 0 3 3 0 0 0 0 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 325140867a1=6a8=7a7=9a6=2a4=1a5=1a3=5a2=4a9=4a11=4a10=2匯點(diǎn)匯點(diǎn)源點(diǎn)源點(diǎn)17數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-

14、12-7算法算法CriticalPath ()/* 圖的關(guān)鍵路徑算法圖的關(guān)鍵路徑算法 */CPath1計(jì)算事件的最早發(fā)生時(shí)間計(jì)算事件的最早發(fā)生時(shí)間 FOR i = 1 TO n DO ve i 0. FOR i = 1 TO n1 DO/*（1）按頂點(diǎn)的拓?fù)湫蛄杏?jì)算）按頂點(diǎn)的拓?fù)湫蛄杏?jì)算各事件的最早發(fā)生時(shí)間各事件的最早發(fā)生時(shí)間*/ (padjacent(Head i) . WHILE p DO(k VerAdj (p) .IF (vei + cost (p) vek ) THENvek vei + cost (p) .plink(p)18數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7CPath2計(jì)算事

15、件的最遲發(fā)生時(shí)間計(jì)算事件的最遲發(fā)生時(shí)間 FOR i = 1 TO n DO vli ven . FOR i = n1 TO 1 STEP 1 DO /*（2）按拓?fù)洌┌赐負(fù)淠嫘蛴?jì)算事件的最遲發(fā)生時(shí)間逆序計(jì)算事件的最遲發(fā)生時(shí)間*/ (padjacent (Headi) .WHILE p DO(kVerAdj(p) .IF (vlk cost (p) vli ) THENvli vlk cost(p) .plink(p)19數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7CPath3求諸活動(dòng)的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間求諸活動(dòng)的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間 FOR i = 1 TO n DO (padjace

16、nt (Head i) .WHILE p DO(kVerAdj (p) .evei .lvlk cost(p) .IF l = e THEN PRINT is Critical Activity! plink(p) 20數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7時(shí)間復(fù)雜性：時(shí)間復(fù)雜性： 對(duì)定點(diǎn)進(jìn)行拓?fù)渑判虻臅r(shí)間復(fù)雜性為對(duì)定點(diǎn)進(jìn)行拓?fù)渑判虻臅r(shí)間復(fù)雜性為O(n+e), 以拓?fù)渑判蚯笠酝負(fù)渑判蚯髒ei和以拓?fù)淠嫘蚯蠛鸵酝負(fù)淠嫘蚯髒li時(shí)時(shí), 所需所需時(shí)間為均為時(shí)間為均為O(e), 求各個(gè)活動(dòng)的求各個(gè)活動(dòng)的ek和和lk的時(shí)間的時(shí)間復(fù)雜度為復(fù)雜度為O(e), 整個(gè)算法的時(shí)間復(fù)雜性是整個(gè)算法的時(shí)間復(fù)雜性是O(

17、n+e)。21數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 第五章第五章 圖圖5.1 基本概念基本概念5.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)5.3 圖的遍歷圖的遍歷5.4 拓?fù)渑判蛲負(fù)渑判?.5 關(guān)鍵路徑關(guān)鍵路徑 5.6 最短路徑最短路徑5.7 最小支撐樹(shù)最小支撐樹(shù)5.8 圖的應(yīng)用圖的應(yīng)用22數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-75.6 最短路徑問(wèn)題最短路徑問(wèn)題l 兩頂點(diǎn)間可能存在多條路徑，每條路徑經(jīng)過(guò)的兩頂點(diǎn)間可能存在多條路徑，每條路徑經(jīng)過(guò)的邊數(shù)邊數(shù)不同，不同，每條路徑的每條路徑的各邊權(quán)值之和各邊權(quán)值之和也不同。也不同。l 從一個(gè)指定的頂點(diǎn)到達(dá)另一指定頂點(diǎn)的路徑上從一個(gè)指定的頂點(diǎn)到達(dá)另一指定頂點(diǎn)的路徑上

18、各邊權(quán)值之各邊權(quán)值之和最小的路徑和最小的路徑被稱(chēng)為最短路徑，這類(lèi)問(wèn)題亦稱(chēng)為被稱(chēng)為最短路徑，這類(lèi)問(wèn)題亦稱(chēng)為最短路徑問(wèn)最短路徑問(wèn)題題。 23數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7l單源單源( (由一個(gè)指定頂點(diǎn)到其他頂點(diǎn)由一個(gè)指定頂點(diǎn)到其他頂點(diǎn)) )最短路徑最短路徑 無(wú)權(quán)最短路徑無(wú)權(quán)最短路徑 正權(quán)最短路徑正權(quán)最短路徑 負(fù)權(quán)最短路徑負(fù)權(quán)最短路徑l每對(duì)頂點(diǎn)之間的最短路徑問(wèn)題每對(duì)頂點(diǎn)之間的最短路徑問(wèn)題24數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-75.6.1 無(wú)權(quán)最短路徑問(wèn)題無(wú)權(quán)最短路徑問(wèn)題無(wú)權(quán)無(wú)權(quán)所有邊的權(quán)值都為所有邊的權(quán)值都為1 1l源點(diǎn)到各頂點(diǎn)的路徑所經(jīng)歷的源點(diǎn)到各頂點(diǎn)的路徑所經(jīng)歷的邊的數(shù)目邊的數(shù)目就是路

19、徑的就是路徑的長(zhǎng)度長(zhǎng)度l相對(duì)于源點(diǎn)相對(duì)于源點(diǎn)由近及遠(yuǎn)由近及遠(yuǎn)依次求各頂點(diǎn)的最短路徑依次求各頂點(diǎn)的最短路徑25數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7算法思想：算法思想：設(shè)設(shè)Di為源點(diǎn)為源點(diǎn)S到頂點(diǎn)到頂點(diǎn) i 的最短路徑長(zhǎng)度的最短路徑長(zhǎng)度訪問(wèn)初始頂點(diǎn)訪問(wèn)初始頂點(diǎn)S，即令，即令DS=0。從從S出發(fā)，找最短路徑為出發(fā)，找最短路徑為1的頂點(diǎn)，即的頂點(diǎn)，即S的所有鄰接頂點(diǎn)的所有鄰接頂點(diǎn)w，令，令Dw=DS+1從上步訪問(wèn)的頂點(diǎn)從上步訪問(wèn)的頂點(diǎn)w出發(fā)，找最短路徑為出發(fā)，找最短路徑為2的頂點(diǎn)，即的頂點(diǎn)，即w未被未被訪問(wèn)的鄰接頂點(diǎn)訪問(wèn)的鄰接頂點(diǎn)v，令，令Dv=Dw+1繼續(xù)上述過(guò)程，直至處理完所有頂點(diǎn)。繼續(xù)上述過(guò)程

20、，直至處理完所有頂點(diǎn)。1V12V63V51V32V43V20SV026數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7V1V6V5V3V4V21122330SV027數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7l上述過(guò)程中，訪問(wèn)頂點(diǎn)的次序與對(duì)圖進(jìn)行上述過(guò)程中，訪問(wèn)頂點(diǎn)的次序與對(duì)圖進(jìn)行廣度優(yōu)先遍歷廣度優(yōu)先遍歷的次序是一致的的次序是一致的;l初始時(shí)，令初始時(shí)，令Dw=-1，當(dāng)，當(dāng)Dw由由-1變成一個(gè)正整數(shù)時(shí)，表示變成一個(gè)正整數(shù)時(shí)，表示從源點(diǎn)到從源點(diǎn)到w的最短路徑已求完，的最短路徑已求完，Dw值就是最短路徑長(zhǎng)度值就是最短路徑長(zhǎng)度,實(shí)現(xiàn)時(shí)使用數(shù)組實(shí)現(xiàn)時(shí)使用數(shù)組dist 存儲(chǔ)存儲(chǔ);l為了找到最短路徑，使用為了找到最短路

21、徑，使用path 存儲(chǔ)從源點(diǎn)到頂點(diǎn)存儲(chǔ)從源點(diǎn)到頂點(diǎn) i 的的最短路徑上最短路徑上最后一個(gè)最后一個(gè)經(jīng)歷的頂點(diǎn)。經(jīng)歷的頂點(diǎn)。28數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7算法算法ShortestPath(v, n)/* 計(jì)算從頂點(diǎn)計(jì)算從頂點(diǎn)v到其他各頂點(diǎn)的最短路徑到其他各頂點(diǎn)的最短路徑*/SPath1初始化初始化 CREATQ(Q) . /* 創(chuàng)建一個(gè)隊(duì)列創(chuàng)建一個(gè)隊(duì)列 */ FOR i = 1 TO n DO (pathi -1. disti -1.) distv 0 . Qv.29數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7SPath2求從頂點(diǎn)求從頂點(diǎn)v到其他各頂點(diǎn)的最短路徑到其他各頂點(diǎn)的最短路徑 WHI

22、LE NOT(ISEMTQ(Q) DO ( u Q . /* 隊(duì)頭頂點(diǎn)隊(duì)頭頂點(diǎn)u出隊(duì)出隊(duì) */ p adjacent (Headu) . /* p為為u的邊鏈表的頭指針的邊鏈表的頭指針 */ WHILE p DO ( k VerAdj (p) . IF (distk = -1) THEN ( Q k. / 將將u的未訪問(wèn)的鄰接頂點(diǎn)入隊(duì)的未訪問(wèn)的鄰接頂點(diǎn)入隊(duì) distk distu + 1. /修改其修改其path值和值和dist值值 pathk u)p link(p) . ) ) 1V12V63V51V32V43V20SV030數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 在最短路徑的計(jì)算中，一個(gè)頂

23、點(diǎn)入隊(duì)出隊(duì)在最短路徑的計(jì)算中，一個(gè)頂點(diǎn)入隊(duì)出隊(duì)各一次，時(shí)間復(fù)雜性為各一次，時(shí)間復(fù)雜性為O(n)，而對(duì)每個(gè)頂點(diǎn)，而對(duì)每個(gè)頂點(diǎn)，都要對(duì)它的邊鏈表進(jìn)行遍歷，其遍歷鄰接，都要對(duì)它的邊鏈表進(jìn)行遍歷，其遍歷鄰接表的開(kāi)銷(xiāo)為表的開(kāi)銷(xiāo)為O(e)，于是整個(gè)算法的時(shí)間復(fù)雜，于是整個(gè)算法的時(shí)間復(fù)雜性為性為O(n+e)。 31數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-75.6.2 正權(quán)最短路徑問(wèn)題正權(quán)最短路徑問(wèn)題l給定一個(gè)帶權(quán)圖給定一個(gè)帶權(quán)圖D與源點(diǎn)與源點(diǎn)v，求從，求從v到到D中其它頂點(diǎn)的中其它頂點(diǎn)的最短路徑最短路徑, 限定各邊的權(quán)值為正實(shí)數(shù)限定各邊的權(quán)值為正實(shí)數(shù)。l正權(quán)最短路徑問(wèn)題不能采用無(wú)權(quán)最短路徑算法。正權(quán)最短路徑問(wèn)題

24、不能采用無(wú)權(quán)最短路徑算法。v0v1v228332數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 Dijkstra算法思想算法思想l 按按路徑長(zhǎng)度非遞減路徑長(zhǎng)度非遞減的次序，逐步產(chǎn)生最短路徑的算法，解的次序，逐步產(chǎn)生最短路徑的算法，解決正權(quán)單源最短路徑問(wèn)題。決正權(quán)單源最短路徑問(wèn)題。l 首先求出從源點(diǎn)首先求出從源點(diǎn)v出發(fā)，長(zhǎng)度最短的一條最短路徑；再參照出發(fā)，長(zhǎng)度最短的一條最短路徑；再參照它求出長(zhǎng)度次短的一條最短路徑；依此類(lèi)推，直到求出從頂點(diǎn)它求出長(zhǎng)度次短的一條最短路徑；依此類(lèi)推，直到求出從頂點(diǎn)v到其它各頂點(diǎn)的最短路徑為止。到其它各頂點(diǎn)的最短路徑為止。33數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7l把圖中所有頂

25、點(diǎn)分成兩組，把圖中所有頂點(diǎn)分成兩組，第一組：第一組：已求完最短路徑的頂點(diǎn)；已求完最短路徑的頂點(diǎn)；第二組：第二組：未求完最短路徑的頂點(diǎn)。按未求完最短路徑的頂點(diǎn)。按最短路徑長(zhǎng)度遞增的順序最短路徑長(zhǎng)度遞增的順序逐個(gè)把第二組的頂點(diǎn)加到第一組中。逐個(gè)把第二組的頂點(diǎn)加到第一組中。l為了求最短路徑，引入輔助數(shù)組為了求最短路徑，引入輔助數(shù)組dist，disti表示當(dāng)前找到的源表示當(dāng)前找到的源點(diǎn)點(diǎn)v0到到vi的最短路徑長(zhǎng)度。的最短路徑長(zhǎng)度。l初始時(shí)：初始時(shí)： S = ，dist0=0，disti=+ S V-S34數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7l設(shè)設(shè)S是已求得最短路徑的頂點(diǎn)集合，則：是已求得最短路徑的頂

26、點(diǎn)集合，則：下一條最短路徑必然是下一條最短路徑必然是從源點(diǎn)從源點(diǎn)v0出發(fā)，中間只經(jīng)過(guò)出發(fā)，中間只經(jīng)過(guò)S中的頂點(diǎn)便可到達(dá)的那些頂點(diǎn)中的頂點(diǎn)便可到達(dá)的那些頂點(diǎn)vx (vx V-S )的路徑中的一條。的路徑中的一條。l每次求最短路徑，也就是在每次求最短路徑，也就是在V-S中找具有最小中找具有最小dist值的頂點(diǎn)值的頂點(diǎn)vk，將，將vk加入集合加入集合S，然后對(duì)，然后對(duì)vi V-S，修改，修改disti值。值。 l經(jīng)第一次操作，經(jīng)第一次操作，S=v0，若從源點(diǎn)，若從源點(diǎn)v0到到vi有邊，則有邊，則disti為該邊上為該邊上的權(quán)值；若從的權(quán)值；若從v0到到vi 無(wú)邊，則無(wú)邊，則disti仍為仍為+ 。

27、S V-S35數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7l Dijkstra算法描述算法描述初始時(shí)（初始時(shí)（S為初始頂點(diǎn)）為初始頂點(diǎn)）, Ds=0且且 i S，有，有Di =。在未訪問(wèn)頂點(diǎn)中選擇在未訪問(wèn)頂點(diǎn)中選擇Dv最小的頂點(diǎn)最小的頂點(diǎn)v，訪問(wèn)，訪問(wèn)v，令，令 Sv=1。依次考察依次考察v的鄰接頂點(diǎn)的鄰接頂點(diǎn)w，若，若 Dv+weight() Dw ， 則改變則改變Dw的值，使的值，使Dw = Dv + weight() 。重復(fù)重復(fù) ，直至所有頂點(diǎn)被訪問(wèn)。，直至所有頂點(diǎn)被訪問(wèn)。l為了找到最短路徑，使用為了找到最短路徑，使用path 存儲(chǔ)從存儲(chǔ)從S到到 i 的最短路徑上的最短路徑上最后一個(gè)經(jīng)歷的頂點(diǎn)

28、。最后一個(gè)經(jīng)歷的頂點(diǎn)。36數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 例例 13258102045301202340123402431051 34303 82 254 100 202 44 1237數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 spathdist0000003421 01325810204530120234在未訪問(wèn)頂點(diǎn)中選擇在未訪問(wèn)頂點(diǎn)中選擇Dv最小的頂點(diǎn)最小的頂點(diǎn)v，訪問(wèn)訪問(wèn)v，令，令 Sv=1。依次考察依次考察v的鄰接頂點(diǎn)的鄰接頂點(diǎn)w，若，若 Dv+weight() Dw ，則改變則改變Dw的值，使的值，使Dw = Dv + weight() 。重復(fù)重復(fù) ，直至所有頂點(diǎn)被訪問(wèn)。，直至

29、所有頂點(diǎn)被訪問(wèn)。38數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7133023431325810204530120234spathdist10000034210303v0v039數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7spathdist100010342103028311v0v0v1v13258330234302811132581020453012023440數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 03421spathdist1100103028311v0 v1v1 v013258102045301202343124158324231141數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-703421spathdis

30、t1100102315311v0v3v1v313258102045301202343124158324231142數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7120415813234231131325810204530120234spathdist1100102315311v0v3v1v343數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7spathdist111110342102315311v0v3v1v3Dijkstra算法算法: 按照非遞減順序依次得到各頂點(diǎn)的最小路按照非遞減順序依次得到各頂點(diǎn)的最小路徑長(zhǎng)度。徑長(zhǎng)度。12041581323423113132581020453012023444數(shù)據(jù)結(jié)構(gòu)國(guó)家

31、精品課程2021-12-7定理定理5.4 Dijkstra算法可以按照非遞減次序依次算法可以按照非遞減次序依次得到各頂點(diǎn)的最小路徑長(zhǎng)度。得到各頂點(diǎn)的最小路徑長(zhǎng)度。證明：歸納法證明：歸納法算法得到的路徑值是各頂點(diǎn)的算法得到的路徑值是各頂點(diǎn)的最小路徑長(zhǎng)度。最小路徑長(zhǎng)度。算法得到的路徑值是按算法得到的路徑值是按非遞減次序非遞減次序得到的。得到的。45數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7算法算法DShortestPath(n, v)/* 計(jì)算計(jì)算v到其他各頂點(diǎn)的最短路徑到其他各頂點(diǎn)的最短路徑 */DSPath1初始化初始化 FOR i = 1 TO n DO ( pathi-1. disti max

32、. si 0. )/ 數(shù)組數(shù)組si記錄記錄i是否被訪問(wèn)過(guò)是否被訪問(wèn)過(guò) distv 0. sv 1. p adjacent (Headv) . u v. / u為即將訪問(wèn)的頂點(diǎn)為即將訪問(wèn)的頂點(diǎn)46數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7DSPath2求從初始頂點(diǎn)求從初始頂點(diǎn)v到其他各頂點(diǎn)的最短路徑到其他各頂點(diǎn)的最短路徑 FOR j = 1 TO n-1 DO / 求從求從v到其他各頂點(diǎn)的最短路徑到其他各頂點(diǎn)的最短路徑 (WHILE p DO /修改修改u鄰接頂點(diǎn)的鄰接頂點(diǎn)的path值和值和dist值值 ( kVerAdj (p) . IF ( sk 1 AND distu + cost(p) 0

33、AND disti ldist AND si = 0 ) THEN( ldist disti . u i. ) su 1./ 訪問(wèn)訪問(wèn)u p adjacent (Headu) ) / p為為u的邊鏈表的頭指針的邊鏈表的頭指針該算法的時(shí)間復(fù)雜性為該算法的時(shí)間復(fù)雜性為O(n2+e)，也可認(rèn)為是，也可認(rèn)為是O(n2)47數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-75.6.3 每對(duì)頂點(diǎn)間的最短路徑每對(duì)頂點(diǎn)間的最短路徑l問(wèn)題：?jiǎn)栴}：已知一個(gè)各邊權(quán)值均大于已知一個(gè)各邊權(quán)值均大于0的帶權(quán)有向圖，對(duì)每一對(duì)頂?shù)膸?quán)有向圖，對(duì)每一對(duì)頂點(diǎn)點(diǎn) vi vj，求，求vi 與與vj間的最短路徑和最短路徑長(zhǎng)度。間的最短路徑和最短路

34、徑長(zhǎng)度。l可依次把每個(gè)頂點(diǎn)作為源點(diǎn)，執(zhí)行可依次把每個(gè)頂點(diǎn)作為源點(diǎn)，執(zhí)行n次次Dijkstra算法。算法。lFloyd算法：算法：定義一個(gè)定義一個(gè)n階方陣序列：階方陣序列： A(-1), A(0), , A(n-1).48數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7lFloyd算法的基本思想：算法的基本思想：設(shè)鄰接矩陣存儲(chǔ)圖，定義初始矩陣設(shè)鄰接矩陣存儲(chǔ)圖，定義初始矩陣A(-1) ij = Edgeij；1、求、求A(0),即即從從vi到到vj 經(jīng)由頂點(diǎn)可以是經(jīng)由頂點(diǎn)可以是v0的最短路徑長(zhǎng)度；的最短路徑長(zhǎng)度；2、求、求A(1),即即從從vi 到到vj 經(jīng)由頂點(diǎn)可以是經(jīng)由頂點(diǎn)可以是v0, v1的最短路徑長(zhǎng)

35、度；的最短路徑長(zhǎng)度； n、求、求A(n-1),即即從從vi 到到vj 經(jīng)由頂點(diǎn)可以是經(jīng)由頂點(diǎn)可以是v0, v1,vn-1的最短路徑長(zhǎng)度；的最短路徑長(zhǎng)度； 其中其中 A(k) ij = min A(k-1)ij， A(k-1)ik + A(k-1)kj , k = 0,1, n-1 49數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-750數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-751數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7算法算法 AllLength ( n )/* 求每對(duì)頂點(diǎn)間的最短路徑求每對(duì)頂點(diǎn)間的最短路徑 */ALength1初始化初始化 FOR i=0 TO n-1 DO / 矩陣矩陣A和和path初始

36、化初始化FOR j=0 TO n-1 DO( Aij edgeij . / 初始化的初始化的A即即A(-1) IF ( i j AND Aij max ) THENpathiji . ELSEpathij -1.)52數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7ALength2求圖中任意兩頂點(diǎn)的最短路徑求圖中任意兩頂點(diǎn)的最短路徑 FOR k=0 TO n-1 DO /從從A(-1)開(kāi)始針對(duì)每個(gè)開(kāi)始針對(duì)每個(gè)k逐步構(gòu)造逐步構(gòu)造A(n-1) FOR i=0 TO n-1 DOIF (i k) THEN FOR j=0 TO n-1 DO IF(j k AND j i AND Aikmax AND Akjm

37、ax AND Aik+AkjAij) THEN ( Aij Aik + Akj . pathijpathkj .) 53數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 Floyd算法的時(shí)間復(fù)雜度為算法的時(shí)間復(fù)雜度為O(n3)，與調(diào)用，與調(diào)用n次次Dijkstra算法求每對(duì)頂點(diǎn)的最短路徑的時(shí)間復(fù)雜算法求每對(duì)頂點(diǎn)的最短路徑的時(shí)間復(fù)雜度相同。度相同。 但但Dijkstra算法僅針對(duì)正權(quán)圖，而算法僅針對(duì)正權(quán)圖，而Floyd算法算法允許圖中有帶負(fù)權(quán)值的邊，但不許有包含帶負(fù)權(quán)允許圖中有帶負(fù)權(quán)值的邊，但不許有包含帶負(fù)權(quán)值的邊組成的回路；且值的邊組成的回路；且Floyd算法更簡(jiǎn)單易于理算法更簡(jiǎn)單易于理解。解。54數(shù)據(jù)

38、結(jié)構(gòu)國(guó)家精品課程2021-12-7本章給出的求解最短路徑的算法，不僅適本章給出的求解最短路徑的算法，不僅適用于帶權(quán)有向圖，對(duì)帶權(quán)無(wú)向圖也可以適用。用于帶權(quán)有向圖，對(duì)帶權(quán)無(wú)向圖也可以適用。因?yàn)閹?quán)無(wú)向圖可以看作是有往返二重邊的因?yàn)閹?quán)無(wú)向圖可以看作是有往返二重邊的有向圖。有向圖。55數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 第五章第五章 圖圖5.1 基本概念基本概念5.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)5.3 圖的遍歷圖的遍歷5.4 拓?fù)渑判蛲負(fù)渑判?.5 關(guān)鍵路徑關(guān)鍵路徑 5.6 最短路徑最短路徑5.7 最小支撐樹(shù)最小支撐樹(shù)5.8 圖的應(yīng)用圖的應(yīng)用56數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 5.7 最

39、小支撐樹(shù)最小支撐樹(shù)1、基本概念、基本概念2、生成最小支撐樹(shù)算法、生成最小支撐樹(shù)算法 Prim算法算法 Kruskar算法算法57數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7最小支撐樹(shù)最小支撐樹(shù)基本概念基本概念 對(duì)于一個(gè)無(wú)向網(wǎng)絡(luò)對(duì)于一個(gè)無(wú)向網(wǎng)絡(luò)無(wú)向加權(quán)連通圖無(wú)向加權(quán)連通圖N=(V,E,C)(C表示該圖為權(quán)圖表示該圖為權(quán)圖)，其頂點(diǎn)個(gè)數(shù)為，其頂點(diǎn)個(gè)數(shù)為|V|=n，圖中邊的個(gè)數(shù)，圖中邊的個(gè)數(shù)為為|E| ，我們可以從它的，我們可以從它的|E|條邊中選出條邊中選出n-1條邊，使之滿(mǎn)條邊，使之滿(mǎn)足足 （1）這）這n-1條邊和圖的條邊和圖的n個(gè)頂點(diǎn)構(gòu)成一個(gè)連通圖。個(gè)頂點(diǎn)構(gòu)成一個(gè)連通圖。 （2）該連通圖的代價(jià)是所有

40、滿(mǎn)足條件）該連通圖的代價(jià)是所有滿(mǎn)足條件(1)的連通圖的連通圖的代價(jià)的最小值。的代價(jià)的最小值。 這樣的連通圖被稱(chēng)為網(wǎng)絡(luò)的這樣的連通圖被稱(chēng)為網(wǎng)絡(luò)的最小支撐樹(shù)最小支撐樹(shù)( Minimum-cost Spanning Tree )。 58數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 最小支撐樹(shù)的性質(zhì)最小支撐樹(shù)的性質(zhì)l最小支撐樹(shù)中沒(méi)有回路最小支撐樹(shù)中沒(méi)有回路 若若MST 的邊集中有回路，顯然可通過(guò)去掉回路中某條的邊集中有回路，顯然可通過(guò)去掉回路中某條邊而得到花銷(xiāo)更小的邊而得到花銷(xiāo)更小的MSTl最小支撐樹(shù)是一棵有最小支撐樹(shù)是一棵有|V| - 1條邊的樹(shù)條邊的樹(shù)l最小支撐樹(shù)的邊集支撐起了圖中所有頂點(diǎn)，且邊集的代價(jià)

41、最小支撐樹(shù)的邊集支撐起了圖中所有頂點(diǎn)，且邊集的代價(jià)最小最小最小支撐樹(shù)的應(yīng)用最小支撐樹(shù)的應(yīng)用l使連接電路板上一系列接頭所需焊接的線路最短使連接電路板上一系列接頭所需焊接的線路最短l在在n個(gè)城市間建立造價(jià)最低的通訊網(wǎng)絡(luò)個(gè)城市間建立造價(jià)最低的通訊網(wǎng)絡(luò)59數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 5.7 最小支撐樹(shù)最小支撐樹(shù)1、基本概念、基本概念2、生成最小支撐樹(shù)算法、生成最小支撐樹(shù)算法 Prim算法算法 Kruskar算法算法60數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7MST性質(zhì)：性質(zhì)：N=(V, E, C)是一個(gè)連通網(wǎng)，是一個(gè)連通網(wǎng)，U是是V的一個(gè)非空子集，若的一個(gè)非空子集，若u, v滿(mǎn)足滿(mǎn)足weig

42、ht(u, v)=min weight(u0, v0) | u0U, v0V-U則必存在則必存在N的一棵最小支撐樹(shù)，該支撐樹(shù)中包括邊的一棵最小支撐樹(shù)，該支撐樹(shù)中包括邊(u, v)。 uv61數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-71、普里姆、普里姆(Prim)算法算法(逐點(diǎn)加入逐點(diǎn)加入) 設(shè)設(shè)N=(V,E,C)為連通網(wǎng)，為連通網(wǎng)，TE是是N的最小支撐樹(shù)的最小支撐樹(shù)MST的邊的的邊的集合，集合，U為為MST頂點(diǎn)集。頂點(diǎn)集。 U=uo(uoV), TE= ； 找到滿(mǎn)足找到滿(mǎn)足weight(u,v)minweight(u1,v1)|u1U, v1V-U, 的邊，把它并入的邊，把它并入TE，同時(shí)，同時(shí)v

43、并入并入U(xiǎn)； 反復(fù)執(zhí)行反復(fù)執(zhí)行 ,直至直至 V=U , 算法結(jié)束。算法結(jié)束。 62數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-74316504535562217 例例 4316504535562217021431650453556221763數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-74316504535562217 4021502164數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-74053221402154316504535562217 65數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-74105352214316504535562217 405322166數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7410535221 4316

44、5045355622174310453522167數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7假設(shè)用鄰接矩陣存儲(chǔ)圖。普里姆算法的實(shí)現(xiàn)需要增設(shè)兩個(gè)輔假設(shè)用鄰接矩陣存儲(chǔ)圖。普里姆算法的實(shí)現(xiàn)需要增設(shè)兩個(gè)輔助數(shù)組助數(shù)組closedgen和和TEn-1 .closedgen的每個(gè)數(shù)組元素由兩個(gè)域構(gòu)成：的每個(gè)數(shù)組元素由兩個(gè)域構(gòu)成：Lowcost和和Vex，其，其定義如下：定義如下：如果如果 ，則，則 = 而而closedgev.Vex存儲(chǔ)的是該邊依附在存儲(chǔ)的是該邊依附在U 中的頂點(diǎn)中的頂點(diǎn)u.如果如果 ，則，則 數(shù)組數(shù)組TEn-1是最小支撐樹(shù)的邊集合，每個(gè)數(shù)組元素是最小支撐樹(shù)的邊集合，每個(gè)數(shù)組元素TEi表示表示

45、一條邊，一條邊，TEi由三個(gè)域由三個(gè)域head、tail和和cost構(gòu)成，它們分別存放構(gòu)成，它們分別存放邊的始點(diǎn)、終點(diǎn)和權(quán)值。邊的始點(diǎn)、終點(diǎn)和權(quán)值。 Uv .closedge v Lowcost| ),(minUuvuweightUv .0, .1closedge v Lowcostclosedge v Vex 68數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-74 43 32 21 15 56 64 45 52 23 31 14 43 32 26 65 51 15 56 64 45 55 56 62 23 31 17 71 13 31 14 41 13 31 16 64 41 16 64 42 23

46、31 14 42 21 16 64 45 52 23 31 169數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-74 43 32 26 65 51 15 56 64 45 55 56 62 23 31 17 7 Vclosedge123456UV-UVexLowcost-101611151max1max12 ,3 ,4 ,5,64 43 32 26 65 51 15 56 64 45 55 56 62 23 31 17 7 Prim: FOR i = 1 TO n DO ( Lowcost (closedgei)edge1i . Vex (closedgei) 1) Vex (closedge1) -1

47、. count 1.70數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 Vclosedge123 3456UV-UVexLowcost-10161 11 1151max1max12 ,3 ,4 ,5 ,6v 0. / 求當(dāng)前權(quán)值最小的邊和該邊的終點(diǎn)求當(dāng)前權(quán)值最小的邊和該邊的終點(diǎn)vminmax. FOR j = 1 TO n DO IF (vex (closedgej) -1 AND Lowcost(closedgej) min ) ( v j. min Lowcost (closedgej) )71數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 Vclosedge123 3456UV-UVexLowcost-

48、1016-1-10 0151max1max1,3,32, 4 ,5 ,6If v 0 THEN / v加入加入U(xiǎn)中中 ( head(TEcount) Vex (closedgev) . tail (TEcount) v. cost (TEcount) Lowcost(closedgev) . count count +1./ 計(jì)數(shù)器加計(jì)數(shù)器加1 Lowcost (closedgev) 0. / 修改域值修改域值 Vex(closedgev) -1. / 頂點(diǎn)頂點(diǎn)v進(jìn)入集合進(jìn)入集合U72數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 Vclosedge123456UV-UVexLowcost-1035-

49、101535341,32,4 ,5,6 4 43 32 26 65 51 15 56 64 45 55 56 62 23 31 17 7 FOR j = 1 TO n DO /修改某些頂點(diǎn)的值修改某些頂點(diǎn)的值 IF(Vex(closedgej) -1 AND edgevj Lowcost(closedgej) THEN ( Lowcost(closedgej) edgevj . Vex(closedgej) v. ) )73數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7算法算法Prim( )/* 構(gòu)造最小支撐樹(shù)的構(gòu)造最小支撐樹(shù)的Prim算法算法 */Prim1初始化鄰接矩陣初始化鄰接矩陣 FOR i

50、= 1 TO n DO FOR j = 1 TO n DO IF (edgeij = 0) edgeij = max; / max是預(yù)定義常數(shù)是預(yù)定義常數(shù)Prim2以頂點(diǎn)以頂點(diǎn)1為初始頂點(diǎn)，初始化數(shù)組為初始頂點(diǎn)，初始化數(shù)組closedge FOR i = 1 TO n DO ( Lowcost (closedgei)edge1i . Vex (closedgei) 1) Vex (closedge1) -1./ 頂點(diǎn)頂點(diǎn)1進(jìn)入集合進(jìn)入集合U count 1. / 支撐樹(shù)的邊記數(shù)器支撐樹(shù)的邊記數(shù)器count74數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7Prim3構(gòu)造圖的最小支撐樹(shù)構(gòu)造圖的最小支撐樹(shù)

51、FOR i =2 TO n DO / 循環(huán)循環(huán)n-1次次 ( v 0. minmax. / 求當(dāng)前權(quán)值最小的邊和該邊的終點(diǎn)求當(dāng)前權(quán)值最小的邊和該邊的終點(diǎn)v FOR j = 1 TO n DO IF (vex (closedgej) -1 AND Lowcost(closedgej) min ) THEN ( v j. min Lowcost (closedgej) . ) IF v 0 THEN /將該邊加入將該邊加入TE中，點(diǎn)中，點(diǎn)v加入集合加入集合U中中 ( head(TEcount) Vex (closedgev) . tail (TEcount) v. cost (TEcount) L

52、owcost(closedgev) . count count +1./ 計(jì)數(shù)器加計(jì)數(shù)器加1 Lowcost (closedgev) 0. / 修改域值修改域值 Vex(closedgev) -1./ 頂點(diǎn)頂點(diǎn)v進(jìn)入集合進(jìn)入集合U / 修改修改v的鄰接頂點(diǎn)的的鄰接頂點(diǎn)的closedge值值 FOR j = 1 TO n DO IF(Vex(closedgej) -1 AND edgevj Lowcost(closedgej) THEN ( Lowcost(closedgej) edgevj . Vex(closedgej) v. ) ) )普里姆算法的時(shí)間復(fù)雜度為普里姆算法的時(shí)間復(fù)雜度為O(n2) ，適用于求邊稠密網(wǎng)的最小支撐，適用于求邊稠密網(wǎng)的最小支撐樹(shù)。樹(shù)。75數(shù)據(jù)結(jié)構(gòu)國(guó)家精品課程2021-12-7 2、克魯斯卡爾、克魯斯卡爾(Kruskar)算法算法 （逐邊加入）（逐邊加入）設(shè)連通網(wǎng)設(shè)連通網(wǎng)N=(V,E,C)，T為為N的最小支撐樹(shù)。初始時(shí)的最小支撐樹(shù)。初始時(shí)T=V,，即即T中沒(méi)有邊，只有中沒(méi)有邊，只有n個(gè)頂點(diǎn)，也就是個(gè)頂點(diǎn)，也就是n個(gè)連通分量。個(gè)連通分量。在在E中選擇權(quán)值最小的邊，并將此邊從中選擇權(quán)值最小的邊，并將此邊從E中刪除。中刪除。如果此邊的兩個(gè)頂點(diǎn)在如果此邊的兩個(gè)頂點(diǎn)