圖論的matlab算法

1、第六講 圖論初步 6.1 引言圖論是運(yùn)籌學(xué)的一個(gè)經(jīng)典和重要的分支,它起源于歐拉(Euler 對七橋問題的抽象和論證。 1936年, 匈牙利數(shù)學(xué)家柯尼希(Knig出版了圖論的第一部專著有限圖與無限圖理論 ,豎立了圖論發(fā)展的第一 座里程碑。此后,圖論進(jìn)入發(fā)展與突破的快車道,所研究的問題涉及經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸、計(jì) 算機(jī)科學(xué)與信息技術(shù)、通訊與網(wǎng)絡(luò)技術(shù)等諸多領(lǐng)域。近幾十年來,由于計(jì)算機(jī)技術(shù)和科學(xué)的飛速發(fā)展,大 大地促進(jìn)了圖論研究和應(yīng)用,圖論的理論和方法已經(jīng)滲透到物理、化學(xué)、通訊科學(xué)、建筑學(xué)、生物遺傳學(xué)、 心理學(xué)、經(jīng)濟(jì)學(xué)、社會(huì)學(xué)等學(xué)科中。圖論中所謂的“圖”是指某類具體事物和這些事物之間的聯(lián)系。如

2、果我們用點(diǎn)表示這些具體事物,用 連接兩點(diǎn)的線段(直的或曲的表示兩個(gè)事物的特定的聯(lián)系,就得到了描述這個(gè)“圖”的幾何形象。圖論 為任何一個(gè)包含了一種二元關(guān)系的離散系統(tǒng)提供了一個(gè)數(shù)學(xué)模型,借助于圖論的概念、理論和方法,可以 對該模型求解。一名貨柜車司機(jī)奉命在最短的時(shí)間內(nèi)將一車貨物從甲地運(yùn)往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯(cuò), 因此有多種行車路線,這名司機(jī)應(yīng)選擇哪條線路呢?假設(shè)貨柜車的運(yùn)行速度是恒定的,那么這一問題相當(dāng) 于需要找到一條從甲地到乙地的最短路。一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件。如何為他(她設(shè)計(jì)一條最短的投遞路線(從郵局出發(fā),經(jīng)過 投遞區(qū)內(nèi)每條街道至少一次,最后返回郵局?由于這一問題是我國管

3、梅谷教授 1960年首先提出的,所 以國際上稱之為中國郵遞員問題。一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他(她設(shè)計(jì)一條最短的旅行路線(從駐地出發(fā),經(jīng) 過每個(gè)城市恰好一次,最后返回駐地?這一問題的研究歷史十分悠久,通常稱之為旅行商問題。一家公司經(jīng)理準(zhǔn)備安排 N 名員工去完成 N 項(xiàng)任務(wù),每人一項(xiàng)。由于各員工的特點(diǎn)不同,不同的員工 去完成同一項(xiàng)任務(wù)時(shí)所獲得的回報(bào)是不同的。如何分配工作方案可以使總回報(bào)最大?某種原材料有 M 個(gè)產(chǎn)地, 現(xiàn)在需要將原材料從產(chǎn)地運(yùn)往 N 個(gè)使用這些原材料的工廠。 假定 M 個(gè)產(chǎn)地 的產(chǎn)量和 N 家工廠的需要量已知, 單位產(chǎn)品從任一產(chǎn)地到任一工廠的運(yùn)費(fèi)已知, 那么如何安

4、排運(yùn)輸方案可 以使總運(yùn)輸成本最低? 6.2 圖的基本概念若用小圓點(diǎn)表示點(diǎn)集 V (G 中的點(diǎn),連線表示邊集 E (G 中的邊,則可用圖形將圖表示出來,稱之為 圖的圖形。我們常用圖的圖形代表圖本身。(e 1 = v 1v 2, (e 2 = v 2v 3, (e 3 = v 2v 3, (e 4 = v 3v 4, (e 5 = v 4v 4, 無環(huán)且無重邊的圖稱之為 簡單圖 。任意兩點(diǎn)均相鄰的簡單圖稱之為 完全圖 。 如果圖 G 的各條邊都被賦予了方向, 則稱圖 G 為 有向圖 。 如果圖 G 的每條邊 e 都附有一個(gè)實(shí)數(shù) w (e , 則稱圖 G 為 賦權(quán)圖 ,實(shí)數(shù) w (e 稱為邊 e 的

5、權(quán)(值 。 如果簡單圖 G 的每個(gè)頂點(diǎn)都有相同的度數(shù) d ,則稱 G 為 d 次 正則圖 。mvdnii2(1=。一個(gè)圖除了可以用圖形表示之外,還可用矩陣來表示。用矩陣表示圖有利于計(jì)算機(jī)處理。設(shè)圖 G = V , E , V = v 1, v 2, , v n , E = e 1, e 2, , e m 。無向圖的 關(guān)聯(lián)矩陣 M (G = (m ij 是一個(gè) n m 矩陣,其中=不相關(guān)聯(lián)與 若 , 相關(guān)聯(lián) 與 若 , 0 1j i j i ij e v e v m ; 有向圖的 關(guān)聯(lián)矩陣 M (G = (m ij 是一個(gè) n m 矩陣,其中=不相關(guān)聯(lián) 與 若 , 的終點(diǎn) 是 若 , -的起點(diǎn)

6、是 若 , 0 1 1j i j i j i ij e v e v e v m 。無向圖的 鄰接矩陣 A (G = (a ij 是一個(gè) n 階方陣,其中 a ij 為連接點(diǎn) v i 與點(diǎn) v j 之間邊的數(shù)目;有向圖的 鄰接矩陣 A (G = (a ij 是一個(gè) n 階方陣,其中 a ij 為從點(diǎn) v i 與出發(fā)到點(diǎn) v j 終止的邊的數(shù)目; 簡單賦權(quán)有向圖 的鄰接矩陣 A (G = (a ij 是一個(gè) n 階方陣,其中=E v v ji w E v v w a j i j i ij 0 若 , 若 , 是它的權(quán)值 且 若 , 。 無向賦權(quán)圖的 邊權(quán)矩陣 W (G = (w ij 是一個(gè) 3m

7、 方陣,其中 w 1j 為第 j 條邊的起點(diǎn)的標(biāo)號, w 2j 為第 j 條邊的終點(diǎn)的標(biāo)號, w 3j 為第 j 條邊的權(quán)值。定義 設(shè) G = V (G , E (G , G 與 H = V (H , E (H , H 為兩個(gè)圖。若 V (H V (G , E (H E (G ,且 H 是 G 在 E (H 上的限制,則稱 H 是 G 的 子圖 。若 H 是 G 的子圖,且 V (H = V (G ,則稱 H 是 G 的 生成 子圖 。若 V (H V (G , V (H ,且對于 v i , v j V (H , v i v j E (G v i v j E (H ,則稱 H 是 G 的 導(dǎo)

8、出子圖 。 = v 1e 1v 2e 2 v k e k v k +1,若滿足 e i 的端點(diǎn)為 v i 與 v i +1, i = 1, 2, , k ,則稱 為一條從起點(diǎn) v 1到終點(diǎn) v k +1的長為 k 的 通路 。邊不重復(fù)的通路稱為 簡單通路 ;除起點(diǎn)與終點(diǎn)可以相同外,任意兩點(diǎn)都不同的通路,稱為 基本通路 , 基本通路簡稱為 路 。顯然,基本通路必為簡單通路。稱起點(diǎn)與終點(diǎn)相同的通路為 回路 ;邊不重復(fù)的回路稱為 簡單回路 ;起點(diǎn)與終點(diǎn)相同的長為正的基本通 路稱為 基本回路 ,也稱為 圈 。如不引起混淆(如在簡單圖中 ,通路與回路均可用點(diǎn)序列來表達(dá)。1 = v 1v 2v 3, 2

9、= v 1v 2v 3v 4v 2, 3 = v 1v 2v 3v 2v 3v 4,則 1, 2, 3分別是長為 2, 4, 5的通路。其中 1與 2為簡單通路, 1為基本通路。又取C 1 = v 1v 2v 3v 4v 2v 5v 1, C 2 = v 1v 2v 5v 1,則 C 1是長為 6的簡單回路, C 2是長為 3的圈。 尋求從一固定起點(diǎn) u 0到其余各點(diǎn)的最短路的最有效算法之一是 Dijkstra (迪克斯特拉算法, 1959年 由 Dijkstra 提出。這個(gè)算法是一種迭代算法,它依據(jù)的是一個(gè)重要而明顯的性質(zhì):最短路是一條路 , 最短 路上的任一子段也是最短路 。Dijkstr

10、a 算法的基本思想是:按距 u 0從近到遠(yuǎn)為順序,依次求得 u 0到圖 G 的各頂點(diǎn)的最短路和距離, 直至頂點(diǎn) v 0(或直至圖 G 的所有頂點(diǎn) 。Dijkstra 算法問題:設(shè)簡單賦權(quán)圖 G = V , E 有 n 個(gè)頂點(diǎn),求 G 中 u 0點(diǎn)到其它各點(diǎn)的距離及最短路。為避免重復(fù)并保留每一步的計(jì)算信息,對 v V ,定義兩個(gè)標(biāo)號:l (v 頂點(diǎn) v 的標(biāo)號,表示從頂點(diǎn) u 0到 v 的一條路的權(quán)值;z (v 頂點(diǎn) v 的父節(jié)點(diǎn)標(biāo)號,用以確定最短路的路線。第一步 賦初值:令 l (u 0 = 0,對所有 v V u 0,令 l (v = , z (v = u 0; S 0 = u 0, i =

11、 0。第二步 若 i = n 1,停止;否則令i= V S i ,進(jìn)行下一步。第三步 更新標(biāo)號:對每個(gè) v i,令l (v =,(,(min vuwulvliiSu ii+;如果 l (v l (u i + w (u i v ,則 z (v = u i ,否則 z (v 不變。第四步 計(jì)算 (min vliv ,并用 u i +1記達(dá)到最小值的頂點(diǎn),置 S i +1 = S i u i +1, i = i +1,轉(zhuǎn)第二步。算法終止后, u 0到 v 的距離由 l (v 的終值給出,從 v 的父節(jié)點(diǎn)標(biāo)號 z (v 追溯到 u 0,就得到 u 0到 v 的 最短路的路線。 (2 用 u 0 = v

12、 1對各頂點(diǎn)的標(biāo)號進(jìn)行更新。 i = 1。0= v 2, v3, v4, v5, v6, v 0,由算法有:l (v 2 = , 0+7 = 7, l (v 3 = , 0+4 = 4, l (v 4 = , 0+ = , l (v 5 = , 0+ = ,l (v 6 = , 0+2 = 2。1= v 2, v3, v4, v5, v 1,由算法有:2= v 2, v4, v5, v 2,由算法有:l (v 2 = 7, 3+3 = 6, l (v 4 = 7, 3+1 = 4, l (v 5 = 7, 3+ = 7。3= v 2, v5, v 3,由算法有:l (v 2 = 6, 4+ =

13、 6, l (v 5 = 7, 4+2 = 6。4= v 2, v 4= v 2,由算法有:l (v 2 = 6, 6+ = 6。注 : 迭代的終止條件也可使用 S n 1 = v 1, , v n ,或者 1n = 。 若尋找 v 1到某點(diǎn) v 的最短路的路由,則由 v 開始追溯父節(jié)點(diǎn)直至 v 1。再如, v 1到 v 2的最短路為:v 1v 6v 3v 2。 若求 v 1到某點(diǎn) v 的距離,則直接由 l (v 的終值確定。 (a (b (c (d (e (f (g (h (i (j尋求賦權(quán)圖中各對頂點(diǎn)之間最短路,顯然可以調(diào)用 Dijkstra 算法。具體方法是:每次以不同的頂點(diǎn)作 為起點(diǎn),

14、用 Dijkstra 算法求出從該起點(diǎn)到其余頂點(diǎn)的最短路徑,反復(fù)執(zhí)行 n 次這樣的操作,就可得到每對 頂點(diǎn)之間的最短路。但這樣做需要大量重復(fù)計(jì)算,效率不高。 R. W. Floyd(弗洛伊德另辟蹊徑,提出了 比這更好的算法,操作方式與 Dijkstra 算法截然不同。Floyd 算法的基本思想是:從圖的帶權(quán)鄰接矩陣 A = a (i , j n n 開始,在 A 中用插入頂點(diǎn)的方法依次構(gòu) 造出 n 個(gè)矩陣 D (1、 D (2、 D (n ,使最后得到的矩陣 D (n 成為 圖的距離矩陣 ,即 矩陣 D (n 的 i 行 j 列元 素便是 i 號頂點(diǎn)到 j 號頂點(diǎn)的距離 。 構(gòu)造 D (i 的

15、同時(shí), 也引入一個(gè) 路由矩陣 P (i 來記錄兩點(diǎn)間的最短路徑。構(gòu)造矩陣 D (k , k = 1, 2, , n ,采用如下的遞推公式:D (0 = d ij (0 n n = A :是帶權(quán)鄰接矩陣, d ij (0 表示從 v i 到 v j 的、中間不插入任何點(diǎn)的路徑,即邊 v i v j 的 權(quán)值;D (1 = d ij (1 n n ,其中 d ij (1 = min dij (0, d i 1(0 + d1 j (0 :d ij (1 表示從 v i 到 v j 的、中間最多只允許 v 1作為 插入點(diǎn)的路徑中最短路的長度;D (2 = d ij (2 n n ,其中 d ij (2

16、 = min dij (1, d i 2(1 + d2 j (1 :d ij (2 表示從 v i 到 v j 的、中間最多只允許 v 1和 v 2作為插入點(diǎn)的路徑中最短路的長度; D (n = d ij (n n n ,其中 d ij (n = min dij (n 1 , d i , n 1 (n 1 + d n 1, j(n 1 :d ij (n 表示從 v i 到 v j 的、中間最多只允 許 v 1, v 2, , v n 1作為插入點(diǎn)的路徑中最短路的長度,即 v i 和 v j 之間的距離。建立路由矩陣 P (k , k = 1, 2, , n ,采用如下的遞推公式: P (0 =

17、 p ij (0 n n :p ij (0 表示從 v i 到 v j 的要經(jīng)過點(diǎn) v j ;每求得一個(gè) D (k 時(shí),按下列方式產(chǎn)生相應(yīng)的新的 P (k = p ij (k n n ,其中+=否則 若 , , 1(1( 1( 1( (k ijk kj k ik k ij k ijp d d d k p 。即當(dāng) v k 被插入到 v i 與 v j 之間的最短路時(shí),被記錄在 P (k 中。依次求 D (n 時(shí)求得 P (n ,可由 P (k 來查找任何兩點(diǎn)之間最短路的路由。Floyd 算法問題:設(shè)簡單賦權(quán)圖 G = V , E 有 n 個(gè)頂點(diǎn),求 G 中任意兩點(diǎn) v i 和 v j 之間的距離

18、及最短路。 輸入帶權(quán)鄰接矩陣 A = a (i , j n n 。第一步 賦初值:對所有 i 和 j , d (i , j = a (i , j ;當(dāng) a (i , j = 時(shí), path (i , j = 0,否則 path (i , j = j , k = 1。第二步 更新 d (i , j , path (i , j :對所有 i 和 j ,若 d (i , k + d (k , j d (i , j ,則轉(zhuǎn)第三步;否則 d (i , j = d (i , k + d (k , j , path (i , j = path (i , k , k = k +1,繼續(xù)執(zhí)行第三步。第三步 重復(fù)

19、第二步直到 k = n +1。 在此: d (i , j :d ij (k 。 path (i , j :p ij (k ;對應(yīng)于 d ij (k 的路徑上 i 的后繼點(diǎn),最終的取值為 i 到 j 的最短路徑上 i 的后繼點(diǎn)。 例如,若=5331154555443245552522221path 則頂點(diǎn) 1到頂點(diǎn) 3的最短路徑為 1253。這是因?yàn)?path(1, 3 = 2,意味著頂點(diǎn) 1的后繼點(diǎn)為 2;又path(2, 3 = 5, 意味著頂點(diǎn) 2的后繼點(diǎn)為 5; 同理, 因 path(5, 3 = 3, 從而頂點(diǎn) 5的后繼點(diǎn)為 3。 故 1253便是頂點(diǎn) 1到頂點(diǎn) 3的最短路徑。根據(jù) D

20、ijkstra 算法和 Floyd 算法的步驟,4和5中分別給出了相應(yīng)的 Matlab 程序。 Dijkstra 算法的 Matlab 實(shí)現(xiàn) % Dijkstra算法% 輸入帶權(quán)鄰接矩陣 w n = size(w,1;w1 = w(1,:;% 賦初值for i = 1:nl(i = w1(i;z(i = 1;ends = ;s(1 = 1;u = s(1;k = 1;l;z;while k l(u+w(u,i l(i = l(u+w(u,i; z(i = u;endendendendl;z;% 求 v*ll = l;for i = 1:nfor j = 1:kif i=s(jll(i = ll

21、(i;elsell(i = inf;endendendlv = inf;for i = 1:nif ll(i lvlv = ll(i;v = i;endendlv;v; s(k+1 = v; k = k+1; u = s(k;end l zFloyd 算法的 Matlab 實(shí)現(xiàn) % Floyd算法% 輸入帶權(quán)鄰接矩陣 a n = size(a,1 D = a;path = zeros(n,n; for i = 1:n for j = 1:nif D(i,j=inf path(i,j = j; end end endfor k = 1:n for i = 1:nfor j = 1:nif D(i

22、,k+D(k,j D(i,j D(i,j = D(i,k+D(k,j; path(i,j = path(i,k; end end end end D path0551inf 2502inf inf inf 5201infinf 1inf 1034inf inf inf 3072inf inf 470。(1 運(yùn)行 Dijkstra 算法的程序,輸出結(jié)果為l = 0 6 3 4 6 2; z = 1 3 6 3 4 1。于是,由 l 和 z 可以得到 v 1到其余各點(diǎn)的距離和最短路的路由。例如, v 1到 v 5的距離由 l(5 = 6給出;其最短路的路由根據(jù) z(5 = 4, z(4 = 3,

23、z(3 = 6, z(6 = 1得到:v 1v 6v 3v 4v 5。(2 運(yùn)行 Floyd 算法的程序,輸出結(jié)果為D = 0 6 3 4 6 2 6 0 3 4 6 4 3 3 0 1 3 1 4 4 1 0 2 2 6 6 3 2 0 4 2 4 1 2 4 0 path = 1 6 6 6 6 6 3 2 3 3 3 3 6 2 3 4 4 6 3 3 3 4 5 3 4 4 4 4 5 4 1 3 3 3 3 6 例如, v 1到 v 5的距離由 D(1, 5 = 6給出;其最短路的路由根據(jù) path(1, 5 = 6, path(6, 5 = 3, path(3, 5 = 4, pa

24、th(4, 5 = 5得到:v 1v 6v 3v 4v 5。解:輸入帶權(quán)鄰接矩陣 0inf 100inf 65700infinf inf inf 20030inf 80inf inf 0infinf inf inf 500。(1 運(yùn)行 Dijkstra 算法的程序,輸出結(jié)果為l = 0 50 230 250 130; z = 1 1 5 3 2。于是,由 l 和 z 可以得到節(jié)點(diǎn) 1到其余各點(diǎn)的距離和最短路的路由。例如, 節(jié)點(diǎn) 1到節(jié)點(diǎn) 4的距離由 l(4 = 250給出; 其最短路的路由根據(jù) z(4 = 3, z(3 = 5, z(5 = 2, z(2 = 1得到:12534。(2 運(yùn)行 F

25、loyd 算法的程序,輸出結(jié)果為D = 0 50 230 250 130 path = 1 2 2 2 2 145 0 180 200 80 5 2 5 5 5 155 30 0 20 90 4 2 3 4 4 135 185 170 0 70 5 5 5 4 5 65 115 100 120 0 1 1 3 3 5 例如, 節(jié)點(diǎn) 1到節(jié)點(diǎn) 4的距離由 D(1, 4 = 250給出; 其最短路的路由根據(jù) path(1, 4 = 2, path(2, 4 = 5, path(5, 4 = 3, path(3, 4 = 4得到:12534。 6.4 樹及其算法樹(tree 在圖論中是相當(dāng)重要的一類

26、圖,它非常類似于自然界中的樹。樹的性質(zhì)非常好,應(yīng)用相當(dāng) 廣泛1。 G 1G 2G 3(有圈 G 4(不連通(1G 是樹;(2G 中任意兩個(gè)不同點(diǎn)之間存在唯一的路;(3G 連通,刪去任一條邊均不連通;(4G 連通,且 n = m + 1;(5G 無圈,且 n = m + 1;(6G 無圈,添加任一條邊可得唯一的圈。 (a (b (c (d證明 給定連通圖 G ,若 G 無圈,則 G 本身就是自己的生成樹。若 G 有圈,則任取 G 中一個(gè)圈 C , 記刪去 C 中一條邊后所得之圖為 G 。顯然 G 中圈 C 已經(jīng)不存在,但 G 仍然連通。若 G 中還有圈,再 重復(fù)以上過程,直到得到一個(gè)無圈的連通圖

27、 H 。易知 H 是 G 的生成樹。證畢。一個(gè)簡單連通圖只要不是樹,其生成樹就不唯一,而且非常多。一般地, n 個(gè)頂點(diǎn)地完全圖,其不同 地生成樹個(gè)數(shù)為 n n 2。因而,尋求一個(gè)給定賦權(quán)圖的最小生成樹,一般是不能用窮舉法的。例如, 30個(gè)頂 點(diǎn)的完全圖有 3028個(gè)生成樹, 3028有 42位,即使用最現(xiàn)代的計(jì)算機(jī),在我們的有生之年也是無法窮舉的。 所以,窮舉法求最小生成樹是無效的算法,必須尋求有效的算法。在求最小生成樹的有效算法中,最著名的兩個(gè)是 Kruskal (克羅斯克爾算法和 Prim (普瑞姆算法, 其迭代過程都是基于貪婪法來設(shè)計(jì)的。1.求最小生成樹的 Kruskal 算法Krusk

28、al 算法的直觀描述假設(shè) T 0是賦權(quán)圖 G 的最小生成樹, T 0中的邊和頂點(diǎn)均涂成紅色,初始時(shí) G 中的邊均為白色。 將所有頂點(diǎn)涂成紅色; 在白色邊中挑選一條權(quán)值最小的邊,使其與紅色邊 不形成圈 ,將該白色邊涂紅; 重復(fù)直到有 n 1條紅色邊,這 n 1條紅色邊便構(gòu)成最小生成樹 T 0的邊集合。 (a(b (c (dKruskal 算法的基本思想設(shè) T 0和 C (T 0 分別為圖 G 的最小生成樹的邊集及其權(quán)值,初始狀態(tài)均為空,算法結(jié)束時(shí) T 0包含最小 生成樹的所有邊, C (T 0 表示最小生成樹的權(quán)值。 令 VS 是一個(gè)不相交的節(jié)點(diǎn)的集合, 初始狀態(tài)時(shí) VS = v 1, v 2,

29、 , v n 。 算法的主要步驟是每次從邊集 E 中選出一條未處理的有最小權(quán)值的邊 (u , v 進(jìn)行分析, 如 果 u 和 v 同屬于 VS 的一個(gè)元素集, 則將邊 (u , v 刪除, 如果 u 和 v 分屬于 VS 的兩個(gè)元素集, 則將邊 (u , v 加入到 T 0中,并將這兩個(gè)元素集合并為一個(gè)元素集,然后再從 E 中另選權(quán)值最小的邊進(jìn)行處理,直至找 到一棵最小生成樹為止。Kruskal 算法的步驟第一步 T 0, C (T 0 0, VS ,將 E 中的邊按權(quán)值從小到大排成序列 Q 。 第二步 對所有 v V , VS v ,即 VS = v 1, v 2, , v n 。 第三步

30、如果 |VS | = 1,輸出 T 0和 C (T 0 ,停止。否則進(jìn)行下一步。 第四步 從 Q 中取出權(quán)值最小的邊 (u , v ,并從 Q 中刪除 (u , v 。邊 (a , b (c , e (a , e (b , c (d , g (a , c (d , f (f , g (c , d (a , g (e , g (d , e 權(quán)4 5 7 9 12 15 16 20 25 28 30 32步驟選出邊 ew (e 操作C (T 0a , b 加到T 0中a , b , c , d , e , f , g (a , b c , e 加到 T 0中 a , b , c , e , d ,

31、 f , g a , b , (c , e a , e 加到 T 0中 a , b , c , e , d , f , g a , b , (c , e , (a , e b , c 刪除 a , b , c , e , d , f , g a , b , (c , e , (a , e d , g 加到 T 0中 a , b , c , e , d , g , f a , b , (c , e , (a , e , (d , g a , c 刪除 a , b , c , e , d , g , f a , b , (c , e , (a , e , (d , g d , f 加到 T 0中

32、a , b , c , e , d , g , f a , b , (c , e , (a , e , (d , g , (d , f f , g 刪除 a , b , c , e , d , g , f a , b , (c , e , (a , e , (d , g , (d , f , (c , d 44 c , d 加到 T 0中a , b , c , e , d , g , f a , b , (c , e , (a , e , (d , g , (d , f , (c , d 69 2.求最小生成樹的 Prim 算法Prim 算法的直觀描述假設(shè) T 0是賦權(quán)圖 G 的最小生成樹。任

33、選一個(gè)頂點(diǎn)將其涂紅,其余頂點(diǎn)為白點(diǎn);在一個(gè)端點(diǎn)為紅色, 另一個(gè)端點(diǎn)為白色的邊中,找一條權(quán)最小的邊涂紅,把該邊的白端點(diǎn)也涂成紅色;如此,每次將一條邊和 一個(gè)頂點(diǎn)涂成紅色,直到所有頂點(diǎn)都成紅色為止。最終的紅色邊便構(gòu)成最小生成樹 T 0的邊集合。 (a (b (cPrim 算法的基本思想設(shè) T 0和 C (T 0 分別為圖 G 的最小生成樹的邊集及其權(quán)值,初始狀態(tài)均為空,算法結(jié)束時(shí) T 0包含最小 生成樹的所有邊, C (T 0 表示最小生成樹的權(quán)值。先指定一個(gè)頂點(diǎn)為初始訪問點(diǎn),記做 v 0,將 v 0加到“通 過點(diǎn)”的集合 V 中,然后找出跨接在“通過點(diǎn)”集合 V 與“未通過點(diǎn)”集合 V V 之間

34、權(quán)最小的邊 e 作 為“通過邊”加入 T 0中,并將 e 在 V V 中的端點(diǎn)轉(zhuǎn)到 V 中。重復(fù)上述過程直至 V = V 為止。Kruskal 算法的步驟第一步 T 0, C (T 0 0, V v 0。第二步 對每一個(gè)點(diǎn) v V V , L (v c (v , v 0 (如果 (v , v 0 E ,則 c (v , v 0 = 。 第三步 如果 V = V ,輸出 T 0, C (T 0 ,停止。否則進(jìn)行下一步。 第四步 在 V V 中找一點(diǎn) u ,使L (u = minL (v | v V V ,并將 V 中與 u 鄰接的點(diǎn)記為 w , e = (w , u 。第五步 T 0T 0e ,

35、 C (T 0 C (T 0 + C (e , V V v 0。第六步 對所有 v V V ,如 c (v , u L (v ,則 L (v c (v , u ,否則 L (v 不變。第七步 轉(zhuǎn)第三步。步驟 u L (b L (c L (d L (e L (f L (g e V T 0C (T 01 a 7 a 02 b -9 7 a , b a , b a , b3 e -a , e a , b , e a , b , (a , e4 c -25 -c , e a , b , e , c a , b , (a , e , (c , e5 d -c , d a , b , e , c , d a , b , (a , e , (c , e , (c , d6 g -16 -(d , g a , b , e , c , d , g a , b , (a , e ,