假设要在n个城市之间建立通信网络，则连通n个城市只需要n-1条线路。现在想节省光缆，使得路径和最小。

这一问题就是最小代价生成树问题(Minimum Cost Spanning Tree)，简称MST。

MST性质：假设N=(V, {E})是一个连通图，U是顶点集合V的一个非空子集，若(u, v)是一条具有最小权值的边，u属于U且v属于V-U。则必存在一棵包含边(u, v)的最小生成树。

因此，可以采用贪心算法解决。

1、Prim(普里姆)算法

我们需要设置[......]

继续阅读