最小生成树

对于一个连通图G，如果其全部顶点和一部分边构成一个子图G1，若这一部分边刚好将图中所有顶点连通，且又不形成回路，则称子图G1是原图G的一棵生成树。

对于同一个图，可以有多个不同的生成树。

生成树是将原图的全部顶点以最小的边连通的子图，对于有n个顶点的连通图，生成树有n-1条边，若边数少于此数就不可能将各顶点连通，如果连通边的数量多于n1，则必然会产生回路。

对于一个带权连通图，生成树不同，树中各边上的权值总和也不同，权值最小的生成树称为图的最小生成树。

 编程经验 求图的最小生成树在很多领域都有实用价值。例如，若用一个图表示城市之间的交通系统，每一个顶点代表一个城市，边的权值表示两城市之间的距离。当有多个城市 时，可能会有n（n+1）/2条线路，怎样选择n-1条线路，使各城市之间总距离最短？这就可用求最小生成树来解决。