历些毛子种枝大票 最小生成树 XIDIAN UNIVERSITY 1. 什么是最小生成树(minimum spanning tree)? 所谓最小生成树，就是在一个具有N个顶点的加权连通图G 中，如果存在某个树形子图T,其包含了图G中的所有项点和 一部分边，且不形成回路，并且子图T的各边权值（距离）之 和最小，则称T为图G的最小生成树。 0.55 0.5」 0.5 12 15 12 15 0.43 0.5\0.55 0.5 0.43 0.75 0.75 0.43 0.55 0.5 0.43 /0.46 0.46 0.46 0.43 13 10 0.55 0.460.75 0.43 八14/0.43 0.46 0.75 0.6 > 0.43 75 0.55 0.75 0.60.75 0.75 0.75 0.55 .75 0.75 图1.一个网络与它的最小生成树 3 1. 什么是最小生成树（minimum spanning tree ）？ 所谓最小生成树，就是在一个具有N个顶点的加权连通图G 中，如果存在某个树形子图T，其包含了图G中的所有顶点和 一部分边，且不形成回路，并且子图T的各边权值（距离）之 和最小，则称T为图G的最小生成树。 最小生成树 3 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. 一个网络与它的最小生成树