历安毛子代枚大” 最小生成树 XIDIAN UNIVERSITY 3. 最小生成树算法 > 无环，不能有回路 节点数和网络节点数相等 > 边数比节点数少一个 最小生成树可能有一个，也可能有多个 0.55 0.5 0.5 12 12 15 0.43 4 0.5 0.55 0.43 0.43 .5 0.75 0.43 0.43 0.75 0.55 0.46 0.46 0.46 0.43 0.43 10 5 0.55八14 /0.43 0.55 .460.75 0.46 0.75 0.55 0.75 0.6 7 0.43 0. 0.75 0.6 0.75 0.75 0.55 0.75 图1.一个网络与它的最小生成树 5 3. 最小生成树算法  无环，不能有回路  节点数和网络节点数相等  边数比节点数少一个  最小生成树可能有一个，也可能有多个 最小生成树 5 0.55 0.55 0.75 0.75 0.6 0.46 0.46 0.43 0.46 0.6 0.5 0.5 0.43 0.75 0.75 0.75 0.75 0.43 0.5 0.55 0.5 0.43 0.55 0.55 0.55 0.43 10 9 11 14 12 15 7 3 5 2 1 6 4 a 8 0.75 13 0.43 0.75 0.6 0.46 0.46 0.43 0.75 0.75 0.5 0.43 0.5 0.43 0.55 0.75 10 9 11 13 14 12 15 5 1 6 2 7 4 3 8 b 图1. 一个网络与它的最小生成树