最小生成树即一个图其代价最小的生成树

最小生成树即一个图其代价最小的生成树，生成树必须包含图中所有顶点，并使图中任意两个顶点之间存在唯一一条路径，设顶点数为n，则生成树的边数为n - 1，对连接顶点的边赋予权重，权重之和最小的生成树即为最小生成树。图的生成树并不是唯一的，最小生成树也是如此(但代价唯一)。

在实际应用中，假如对n个城市铺设电缆，在确保n个城市是连通的情况下，需要n - 1条线路，如果铺设每条电缆的代价都是不一样的，那么如何使得代价最低？最小生成树就用来可以解决这个问题。在下图中，最下面的生成树为最小生成树，它连接了图的所有顶点，也保证了边的权重是最小的。构造最小生成树的算法有多种，本文介绍的是最为广泛的两种:普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。

Prime算法是通过点来构建最小生成树，对于稠密图，prim比kruskal性能更优。

不同于prime算法，kruskal算法通过找边来构建最小生成树，对于稀疏图，其性能优于prime算法。