Tag Archives: 最小生成树

数据结构重读 – 最小生成树(Prim和Kruskal)

假设要在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(普里姆)算法

我们需要设置[……]

继续阅读