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

1、第五章 圖 5.1 基本概念 5.2 圖的存儲結(jié)構(gòu) 5.3 圖的遍歷 5.4 拓?fù)渑判?5.5 關(guān)鍵路徑 5.6 最短路徑 5.7 最小支撐樹,5.6 最短路徑問題 兩頂點(diǎn)間可能存在多條路徑，每條路徑經(jīng)過的邊數(shù)不同，每條路徑的各邊權(quán)值之和也不同。 從一個(gè)指定的頂點(diǎn)到達(dá)另一指定頂點(diǎn)的路徑上各邊權(quán)值之和最小的路徑被稱為最短路徑，這類問題亦稱為最短路徑問題。,單源(由一個(gè)指定頂點(diǎn)到其他頂點(diǎn))最短路徑 無權(quán)最短路徑 正權(quán)最短路徑 每對頂點(diǎn)之間的最短路徑問題,5.6.2 正權(quán)最短路徑問題 給定一個(gè)帶權(quán)圖D與源點(diǎn)v，求從v到D中其它頂點(diǎn)的最短路徑, 限定各邊的權(quán)值為正實(shí)數(shù)。,Dijkstra算法思想 按路

2、徑長度非遞減的次序，逐步產(chǎn)生最短路徑的算法，解決正權(quán)單源最短路徑問題。 首先求出從源點(diǎn)v出發(fā)，長度最短的一條最短路徑；再參照它求出長度次短的一條最短路徑；依此類推，直到求出從頂點(diǎn)v到其它各頂點(diǎn)的最短路徑為止。,Dijkstra算法描述 初始時(shí)（S為初始頂點(diǎn)）, Ds=0且 i S，有Di =。 在未訪問頂點(diǎn)中選擇Dv最小的頂點(diǎn)v，訪問v，令 Sv=1。 依次考察v的鄰接頂點(diǎn)w，若 Dv+weight() 。 重復(fù) ，直至所有頂點(diǎn)被訪問。 為了找到最短路徑，使用path 存儲從S到 i 的最短路徑上最后一個(gè)經(jīng)歷的頂點(diǎn)。,例,在未訪問頂點(diǎn)中選擇Dv最小的頂點(diǎn)v，訪問v，令 Sv=1。 依次考察v的

3、鄰接頂點(diǎn)w，若 Dv+weight() 。 重復(fù) ，直至所有頂點(diǎn)被訪問。,Dijkstra算法: 按照非遞減順序依次得到各頂點(diǎn)的最小路徑長度。,正權(quán)單源最短路徑問題的 Dijkstra 算法： 算法DShortestPath(n, v) /* 計(jì)算v到其他各頂點(diǎn)的最短路徑 */ DSPath1初始化 FOR i = 1 TO n DO ( pathi-1. disti max. si 0. )/ 數(shù)組si記錄i是否被訪問過 distv 0. sv 1. p adjacent (Headv) . u v. / u為即將訪問的頂點(diǎn),DSPath1初始化 FOR i = 1 TO n DO ( pa

4、thi-1. disti max. si 0. ) distv 0. sv 1. p adjacent (Headv) . u v. / u為即將訪問的頂點(diǎn),DSPath2求從初始頂點(diǎn)v到其他各頂點(diǎn)的最短路徑 算法DSPath2第1部分 FOR j = 1 TO n-1 DO / 求從v到其他各頂點(diǎn)的最短路徑 (WHILE p DO /修改u鄰接頂點(diǎn)的path值和dist值 ( kVerAdj (p) . IF ( sk 1 AND distu + cost(p) distk ) THEN ( distk distu + cost(p) . pathk u. ) p link(p) ) /確定

5、即將被訪問的頂點(diǎn)u,算法DSPath2第2部分 ldist max. FOR i = 0 TO n-1 DO IF ( disti 0 AND disti ldist AND si = 0 ) THEN (ldist disti . u i. ) su 1./ 訪問u p adjacent (Headu) ) ,算法DSPath2第1部分 FOR j = 1 TO n-1 DO / 求從v到其他各頂點(diǎn)的最短路徑 (WHILE p DO ( kVerAdj (p) . IF ( sk 1 AND distu + cost(p) distk ) THEN ( distk distu + cost(

6、p) . pathk u. ) p link(p) ),算法DSPath2第1部分 FOR j = 1 TO n-1 DO / 求從v到其他各頂點(diǎn)的最短路徑 (WHILE p DO ( kVerAdj (p) . IF ( sk 1 AND distu + cost(p) distk ) THEN ( distk distu + cost(p) . pathk u. ) p link(p) ),算法DSPath2第2部分 ldist max. FOR i = 1 TO n DO IF ( disti 0 AND disti ldist AND si = 0 ) THEN (ldist dist

7、i . u i. ) su 1./ 訪問u p adjacent (Headu) ) ,算法DSPath2第1部分 FOR j = 1 TO n-1 DO / 求從v到其他各頂點(diǎn)的最短路徑 (WHILE p DO ( kVerAdj (p) . IF ( sk 1 AND distu + cost(p) distk ) THEN ( distk distu + cost(p) . pathk u. ) p link(p) ),算法DSPath2第2部分 ldist max. FOR i = 1 TO n DO IF ( disti 0 AND disti ldist AND si = 0 )

8、THEN (ldist disti . u i. ) su 1./ 訪問u p adjacent (Headu) ) ,3,算法DSPath2第1部分 FOR j = 1 TO n-1 DO / 求從v到其他各頂點(diǎn)的最短路徑 (WHILE p DO ( kVerAdj (p) . IF ( sk 1 AND distu + cost(p) distk ) THEN ( distk distu + cost(p) . pathk u. ) p link(p) ),算法DSPath2第2部分 ldist max. FOR i = 1 TO n DO IF ( disti 0 AND disti l

9、dist AND si = 0 ) THEN (ldist disti . u i. ) su 1./ 訪問u p adjacent (Headu) ) ,該算法的時(shí)間復(fù)雜性為O(n2+e)，也可認(rèn)為是O(n2),4,5.6.3 每對頂點(diǎn)間的最短路徑 問題：已知一個(gè)各邊權(quán)值均大于0的帶權(quán)有向圖，對每一對頂點(diǎn) vi vj，求vi 與vj間的最短路徑和最短路徑長度。 可依次把每個(gè)頂點(diǎn)作為源點(diǎn)，執(zhí)行n次Dijkstra算法。 Floyd算法： 定義一個(gè)n階方陣序列： A(-1), A(0), , A(n-1).,Floyd算法的基本思想： 設(shè)鄰接矩陣存儲圖，定義初始矩陣A(-1) ij = Edge

10、ij； 1、求A(0),即從vi到vj 經(jīng)由頂點(diǎn)可以是v0的最短路徑長度； 2、求A(1),即從vi 到vj 經(jīng)由頂點(diǎn)可以是v0, v1的最短路徑長度； n、求A(n-1),即從vi 到vj 經(jīng)由頂點(diǎn)可以是v0, v1,vn-1的最短路徑長度； 經(jīng)過n次運(yùn)算后，最后求得的就是從vi-vj的最短路徑。 其中 A(k) ij = min A(k-1)ij， A(k-1)ik + A(k-1)kj , k = 0,1, n-1,例 求下圖中每對頂點(diǎn)之間的最短路徑。,A(k)ij = minA(k-1)ij, A(k-1)ik+ A(k-1)kj|0 k n-1,當(dāng)i=j時(shí)，公式變?yōu)椋?A(k)ij

11、= minA(k-1)ii, A(k-1)ik+ A(k-1)ki|0 k n-1= 0,A(k)ij = minA(k-1)ij, A(k-1)ik+ A(k-1)kj|0 k n-1,當(dāng)i=k或j=k時(shí)，公式變?yōu)椋?A(k)kj = minA(k-1)kj, A(k-1)kk+ A(k-1)kj | 0 k n-1 A(k)ik = minA(k-1)ik, A(k-1)ik+ A(k-1)kk | 0 k n-1,A(k)ij = minA(k-1)ij, A(k-1)ik+ A(k-1)kj|0 k n-1,A(k)ij = minA(k-1)ij, A(k-1)ik+ A(k-1)k

12、j|0 k n-1,0 1 2 3,0 1 10 3 0 9 2 3 4 0 6 6 0,0 1 2 3,A（1） ,A(k)ij = minA(k-1)ij, A(k-1)ik+ A(k-1)kj|0 k n-1,A(k)ij = minA(k-1)ij, A(k-1)ik+ A(k-1)kj|0 k n-1,求每對頂點(diǎn)之間的最短路徑算法 template void Graph:allLength(const int n), for ( int i = 0; i j /縮短路徑長度, 繞過 k 到 j,for ( int i = 0; i j / i 到 j 無路徑 ,for ( int i

13、 = 0; i j / i 到 j 無路徑 ,for ( int k = 0; k n; k+ ) for ( i = 0; i n; i+ ) for ( j = 0; j n; j+ ) if ( Aik + Akj Aij ) Aij = Aik + Akj; pathij = pathkj; ,for ( int k = 0; k n; k+ ) for ( i = 0; i n; i+ ) for ( j = 0; j n; j+ ) if ( Aik + Akj Aij ) Aij = Aik + Akj; pathij = pathkj; ,for ( int k = 0; k

14、n; k+ ) for ( i = 0; i n; i+ ) for ( j = 0; j n; j+ ) if ( Aik + Akj Aij ) Aij = Aik + Akj; pathij = pathkj; ,for ( int k = 0; k n; k+ ) for ( i = 0; i n; i+ ) for ( j = 0; j n; j+ ) if ( Aik + Akj Aij ) Aij = Aik + Akj; pathij = pathkj; ,從A(3)知，頂點(diǎn)1到0的最短路徑長度為A10 = 11, 其最短路徑看 path10 = 2，path12 = 3，pa

15、th 13 = 1, 表示頂點(diǎn)0 頂點(diǎn)2 頂點(diǎn)3 頂點(diǎn)1;從頂點(diǎn)1到頂點(diǎn)0最短路徑為,。,0,Floyd算法的時(shí)間復(fù)雜度為O(n3)，與調(diào)用n次Dijkstra算法求每對頂點(diǎn)的最短路徑的時(shí)間復(fù)雜度相同。 但Dijkstra算法僅針對正權(quán)圖，而Floyd算法允許圖中有帶負(fù)權(quán)值的邊，但不許有包含帶負(fù)權(quán)值的邊組成的回路；且Floyd算法更簡單易于理解。,本章給出的求解最短路徑的算法，不僅適用于帶權(quán)有向圖，對帶權(quán)無向圖也可以適用。因?yàn)閹?quán)無向圖可以看作是有往返二重邊的有向圖。,第五章 圖 5.1 基本概念 5.2 圖的存儲結(jié)構(gòu) 5.3 圖的遍歷 5.4 拓?fù)渑判?5.5 關(guān)鍵路徑 5.6 最短路徑 5

16、.7 最小支撐樹,5.7 最小支撐樹 1、基本概念 2、生成最小支撐樹算法 Prim算法 Kruskar算法,最小支撐樹基本概念,對于一個(gè)無向網(wǎng)絡(luò)無向加權(quán)連通圖N=(V,E,C)(C表示該圖為權(quán)圖)，其頂點(diǎn)個(gè)數(shù)為|V|=n，圖中邊的個(gè)數(shù)為|E| ，我們可以從它的|E|條邊中選出n-1條邊，使之滿足 （1）這n-1條邊和圖的n個(gè)頂點(diǎn)構(gòu)成一個(gè)連通圖。 （2）該連通圖的代價(jià)是所有滿足條件(1)的連通圖的代價(jià)的最小值。 這樣的連通圖被稱為網(wǎng)絡(luò)的最小支撐樹( Minimum-cost Spanning Tree )。,最小支撐樹的性質(zhì) 最小支撐樹中沒有回路 若MST 的邊集中有回路，顯然可通過去掉回路中

17、某條邊而得到花銷更小的MST 最小支撐樹是一棵有|V| - 1條邊的樹 最小支撐樹的邊集支撐起了圖中所有頂點(diǎn)，且邊集的代價(jià)最小 最小支撐樹的應(yīng)用 使連接電路板上一系列接頭所需焊接的線路最短 在n個(gè)城市間建立造價(jià)最低的通訊網(wǎng)絡(luò),5.7 最小支撐樹 1、基本概念 2、生成最小支撐樹算法 Prim算法 Kruskar算法,1 普里姆(Prim)算法（逐點(diǎn)加入） 設(shè)為N=(V,E,C)連通網(wǎng)，TE是N的最小支撐樹的邊的集合。 算法開始時(shí)，U= uo(uoV), TE= ； 找到滿足 weight(u,v）minweight(u1,v1）| u1U, v1V-U, 的邊，把它并入集合TE中，v同時(shí)并入U(xiǎn)

18、。 反復(fù)執(zhí)行 ,直至 V=U 時(shí)終止算法。,假設(shè)用鄰接矩陣存儲圖。普里姆算法的實(shí)現(xiàn)需要增設(shè)兩個(gè)輔助數(shù)組closedgen和TEn-1 . closedgen的每個(gè)數(shù)組元素由兩個(gè)域構(gòu)成：Lowcost和Vex，其定義如下： 如果 ，則 = 而closedgev.Vex存儲的是該邊依附在U 中的頂點(diǎn)u. 如果 ，則 數(shù)組TEn-1是最小支撐樹的邊集合，每個(gè)數(shù)組元素TEi表示一條邊，TEi由三個(gè)域head、tail和cost構(gòu)成，它們分別存放邊的始點(diǎn)、終點(diǎn)和權(quán)值。,普里姆算法 /* 利用普里姆算法從頂點(diǎn)v1出發(fā)求出用鄰接 矩陣Edge表示的圖的最小支撐樹，最小支撐樹 的邊集存于數(shù)組TE中*/,算法P

19、rim( ) /* 構(gòu)造最小支撐樹的Prim算法 */ Prim1初始化鄰接矩陣 FOR i = 1 TO n DO FOR j = 1 TO n DO IF (edgeij = 0) THEN edgeij = max; / max是預(yù)定 義常數(shù) Prim2以頂點(diǎn)1為初始頂點(diǎn)，初始化數(shù)組closedge FOR i = 1 TO n DO ( Lowcost (closedgei)edge1i . Vex (closedgei) 1) Vex (closedge1) -1./ 頂點(diǎn)1進(jìn)入集合U count 1. / 支撐樹的邊記數(shù)器count,Prim3構(gòu)造圖的最小支撐樹 FOR i =2

20、TO n DO / 循環(huán)n-1次 ( v 0. minmax. / 求當(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 v0 THEN /將該邊加入TE中，點(diǎn)v加入集合U中 ( head(TEcount) Vex (closedgev) . tail (TEcount) v. cost (TEcount) Lowcost(closedgev) . count count +1./ 計(jì)數(shù)器加

21、1 Lowcost (closedgev) 0. / 修改域值 Vex(closedgev) -1./ 頂點(diǎn)v進(jìn)入集合U / 修改v的鄰接頂點(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ù)雜度為O(n2) ，適用于求邊稠密網(wǎng)的最小支撐樹。,普里姆算法圖示： 算法Prim2部分 Prim2以頂點(diǎn)1為初始頂點(diǎn)，初始化數(shù)組closedge FOR i =

22、 1 TO n DO ( Lowcost (closedgei)edge1i . Vex (closedgei) 1) Vex (closedge1) -1./ 頂點(diǎn)1進(jìn)入集合U count 1. / 支撐樹的邊記數(shù)器count,算法Prim3第1部分 Prim3構(gòu)造圖的最小支撐樹 FOR i =2 TO n DO / 循環(huán)n-1次 ( v 0. minmax. / 求當(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 (clo

23、sedgej) . ),算法Prim3第2部分 IF v0 THEN /將該邊加入TE中，點(diǎn)v加入集合U中 ( head(TEcount) Vex (closedgev) . tail (TEcount) v. cost (TEcount) Lowcost(closedgev) . count count +1. / 計(jì)數(shù)器加1 Lowcost (closedgev) 0. / 修改域值 Vex(closedgev) -1. / 頂點(diǎn)v進(jìn)入集合U,算法Prim3第3部分 / 修改v的鄰接頂點(diǎn)的closedge值 FOR j = 1 TO n DO IF(Vex(closedgej) -1 AN

24、D edgevj Lowcost(closedgej) THEN ( Lowcost(closedgej) edgevj . Vex(closedgej) v. ) ) ),算法Prim3第1部分 Prim3構(gòu)造圖的最小支撐樹 FOR i =2 TO n DO / 循環(huán)n-1次 ( v 0. minmax. / 求當(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) . ),算法Prim3第2部分 IF v

25、0 THEN /將該邊加入TE中，點(diǎn)v加入集合U中 ( head(TEcount) Vex (closedgev) . tail (TEcount) v. cost (TEcount) Lowcost(closedgev) . count count +1. / 計(jì)數(shù)器加1 Lowcost (closedgev) 0. / 修改域值 Vex(closedgev) -1. / 頂點(diǎn)v進(jìn)入集合U,算法Prim3第3部分 / 修改v的鄰接頂點(diǎn)的closedge值 FOR j = 1 TO n DO IF(Vex(closedgej) -1 AND edgevj Lowcost(closedgej)

26、THEN ( Lowcost(closedgej) edgevj . Vex(closedgej) v. ) ) ),算法Prim3第1部分 Prim3構(gòu)造圖的最小支撐樹 FOR i =2 TO n DO / 循環(huán)n-1次 ( v 0. minmax. / 求當(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) . ),算法Prim3第2部分 IF v0 THEN /將該邊加入TE中，點(diǎn)v加入集合U中 (

27、head(TEcount) Vex (closedgev) . tail (TEcount) v. cost (TEcount) Lowcost(closedgev) . count count +1. / 計(jì)數(shù)器加1 Lowcost (closedgev) 0. / 修改域值 Vex(closedgev) -1. / 頂點(diǎn)v進(jìn)入集合U,算法Prim3第3部分 / 修改v的鄰接頂點(diǎn)的closedge值 FOR j = 1 TO n DO IF(Vex(closedgej) -1 AND edgevj Lowcost(closedgej) THEN ( Lowcost(closedgej) ed

28、gevj . Vex(closedgej) v. ) ) ),算法Prim3第1部分 Prim3構(gòu)造圖的最小支撐樹 FOR i =2 TO n DO / 循環(huán)n-1次 ( v 0. minmax. / 求當(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) . ),算法Prim3第2部分 IF v0 THEN /將該邊加入TE中，點(diǎn)v加入集合U中 ( head(TEcount) Vex (closedgev) . tail (TEcount) v. cost (TEcount) Lowcost(closedgev) . count count +1. / 計(jì)數(shù)器加1 Lowcost (closedgev) 0. / 修改域值 Vex(closedgev) -1. / 頂點(diǎn)v進(jìn)入集合U,算法Prim3第3部分 / 修改v的鄰接頂點(diǎn)的closedge值 FOR j = 1 TO n DO IF(Vex(closedgej) -1 AND edgevj Lowcost(closedgej) THEN