《現(xiàn)代通信網(wǎng)》課件K方法求最小支撐樹

K方法求最小支撐樹1例：要建設(shè)連接如下圖所示的五個(gè)城鎮(zhèn)的線路網(wǎng)，圖中所標(biāo)權(quán)值為兩城鎮(zhèn)之間的距離，請(qǐng)用K方法找出連接這五個(gè)城鎮(zhèn)線路費(fèi)用最小的網(wǎng)路結(jié)構(gòu)圖（設(shè)線路費(fèi)用與距離成正比）。6.4148512118.51063v2五個(gè)城鎮(zhèn)的地圖v1v3v4v5K方法求最小支撐樹2Kruskal方法（簡(jiǎn)稱K方法）K0：將圖G中的所有邊按權(quán)值遞增（或非減）的次序排列（若有兩條以上邊的權(quán)值相等，則這些邊可以任意次序排列）。K1：依次選取表中權(quán)值最小的邊為樹枝，若當(dāng)前選取的邊與已經(jīng)選出的邊形成回路，則舍去。K2：結(jié)束條件——n的點(diǎn)的圖，選出了n-1條邊。按上述方法選出的n-1條邊與n個(gè)點(diǎn)就構(gòu)成圖G的最小支撐樹。K方法求最小支撐樹3K0：將城鎮(zhèn)之間的距離按非減次序排列，如下表。6.4148512118.51063v2五個(gè)城鎮(zhèn)的地圖v1v3v4v5順序邊距離順序邊距離1(v1,v2)36(v1,v5)8.52(v2,v3)57(v1,v4)103(v1,v3)68(v2,v5)114(v4,v5)6.49(v2,v4)125(v3,v4)810(v3,v5)14K方法求最小支撐樹4K1：按排列的順序選邊順序邊距離順序邊距離1(v1,v2)36(v1,v5)8.52(v2,v3)57(v1,v4)103(v1,v3)68(v2,v5)114(v4,v5)6.49(v2,v4)125(v3,v4)810(v3,v5)141.選(v1,v2)，距離為3；6.4148512118.51063v2五個(gè)城鎮(zhèn)的地圖v1v3v4v5K方法求最小支撐樹5K1：按排列的順序選邊順序邊距離順序邊距離1(v1,v2)36(v1,v5)8.52(v2,v3)57(v1,v4)103(v1,v3)68(v2,v5)114(v4,v5)6.49(v2,v4)125(v3,v4)810(v3,v5)141.選(v1,v2)，距離為3；2.選(v2,v3)，不形成回路，保留，距離為5；6.4148512118.51063v2五個(gè)城鎮(zhèn)的地圖v1v3v4v5K方法求最小支撐樹6K1：按排列的順序選邊順序邊距離順序邊距離1(v1,v2)36(v1,v5)8.52(v2,v3)57(v1,v4)103(v1,v3)68(v2,v5)114(v4,v5)6.49(v2,v4)125(v3,v4)810(v3,v5)141.選(v1,v2)，距離為3；2.選(v2,v3)，不形成回路，保留，距離為5；3.選(v1,v3)，形成回路，舍棄；6.4148512118.51063v2五個(gè)城鎮(zhèn)的地圖v1v3v4v5K方法求最小支撐樹7K1：按排列的順序選邊順序邊距離順序邊距離1(v1,v2)36(v1,v5)8.52(v2,v3)57(v1,v4)103(v1,v3)68(v2,v5)114(v4,v5)6.49(v2,v4)125(v3,v4)810(v3,v5)141.選(v1,v2)，距離為3；2.選(v2,v3)，不形成回路，保留，距離為5；3.選(v1,v3)，形成回路，舍棄；4.選(v4,v5)，不形成回路，保留，距離為6.4；6.4148512118.51063v2五個(gè)城鎮(zhèn)的地圖v1v3v4v5K方法求最小支撐樹8K1：按排列的順序選邊順序邊距離順序邊距離1(v1,v2)36(v1,v5)8.52(v2,v3)57(v1,v4)103(v1,v3)68(v2,v5)114(v4,v5)6.49(v2,v4)125(v3,v4)810(v3,v5)141.選(v1,v2)，距離為3；2.選(v2,v3)，不形成回路，保留，距離為5；3.選(v1,v3)，形成回路，舍棄；4.選(v4,v5)，不形成回路，保留，距離為6.4；5.選(v3,v4)，不形成回路，保留，距離為8。6.4148512118.51063v2五個(gè)城鎮(zhèn)的地圖v1v3v4v5K方法求最小支撐樹9K1：按排列的順序選邊順序邊距離順序邊距離1(v1,v2)36(v1,v5)8.52(v2,v3)57(v1,v4)103(v1,v3)68(v2,v5)114(v4,v5)6.49(v2,v4)125(v3,v4)810(v3,v5)141.選(v1,v2)，距離為3；2.選(v2,v3)，不形成回路，保留，距離為5；3.選(v1,v3)，形成回路，舍棄；4.選(v4,v5)，不形成回路，保留，距離為6.4；5.選(v3,v4)，不形成回路，保留，距離為8。K2：至此，已找到4條邊，與5個(gè)點(diǎn)構(gòu)成最小支撐樹。6.4148512118.51063v2五個(gè)城鎮(zhèn)的地圖v1v3v4v5例：下圖是一個(gè)有7個(gè)節(jié)點(diǎn)的圖G（V，E），各節(jié)點(diǎn)之間的邊及權(quán)值如圖所示，試求這個(gè)圖的最小支撐樹，畫出圖并求出其長(zhǎng)度。（V1，V2），權(quán)值為1；（V1，V3），權(quán)值為2，與已選邊沒有形成回路；（V3，V5），權(quán)值為4，與已選邊沒有形成回路；（