5 例子: 2|34|5 V-U TE VEX ①@⑩①① 2,3,4,5,6} LOwC0sT0615∞ ①③ 2,4,5,6} 05056|4 1,3,6} 2,4,5} (3,6) 050260 1,3,6,4 2,5} (6,4) 050016|0 1,3,6,4,2} 3,2) 000030 1,3,6,4,2,5} 000000
例子： V Closedge 1 2 3 4 5 6 U V-U TE VEX LOWCOST 0 ①6 ①1 ①5 ①∞ ①∞ {1} {2,3,4,5,6} {} 0 ③5 0 ①5 ③6 ③4 {1,3} {2,4,5,6} {1,3} 0 ③5 0 ⑥2 ③6 0 {1,3,6} {2,4,5} ..(3,6) 0 ③5 0 0 ③6 0 {1,3,6,4} {2,5} ..(6,4) 0 0 0 0 ②3 0 {1,3,6,4,2} {5} ..(3,2) 0 0 0 0 0 0 {1,3,6,4,2,5} {} ..(2.5) ② ① ④ ⑤ 5 2 1 ③ 3 4 6 65 5 6 ⑥
四、克鲁斯卡尔( Kruskal)最小生成树算法 Kruskal算法是逐步给生成树T中添加不和T中的边构成回路 的当前最小代价边。 特点:以最小代价边主。 设N=(V,{E})是个连通网,算法步骤为: 1.置生成树T的初始状态为T=(V,{Φ}) 2.当T中边数<n-时,重复下列步骤: ·从E中选取代价最小的边(vu),并删除之; 若(v,u)依附的顶点v和u在T中不同的连同分量上, 则将边(v,u)并入到T的边集中; 否则,舍去该边,选择下一条代价最小的边
四、克鲁斯卡尔（Kruskal）最小生成树算法 Kruskal 算法是逐步给生成树T中添加不和T中的边构成回路 的当前最小代价边。 特点: 以最小代价边主。 设N=（V，{E}）是个连通网, 算法步骤为： 1. 置生成树T的初始状态为T=（V，{Ф}） 2. 当T中边数<n-1时, 重复下列步骤: • 从E中选取代价最小的边（v, u）, 并删除之; • 若（v, u）依附的顶点v和u落在T中不同的连同分量上， 则将边（v, u）并入到T的边集中； 否则，舍去该边，选择下一条代价最小的边