文档介绍：最小生成树算法
最小生成树:
在一给定的无向图 G=(V,E) 中 ,(u,v) 代表连接顶点 u 与顶点 v 的边 ,
而 w(u,v) 代表此边的权重 , 若存在 T 为 E 的子集且为无循环图 , 使得
w(T) 最小 , 则此 T 为 G的最小生成树。
最小生成树其实是最小权重生成树的简称。
最小生成树性质:设 G=(V,E) 是一个连通网络, U 是顶点集 V 的
一个非空真子集。若 (u,v) 是 G 中一条一个端点在 U 中 ( 例如 :u ∈U),
另一个端点不在 U 中的边(例如: v∈ V-U),且(u ,v) 具有最小权值 ,
则一定存在 G 的一棵最小生成树包括此边 (u,v) 。
一个有 n 个结点的连通图的生成树是原图的极小连通子图,且
包含原图中的所有 n 个结点 , 并且有保持图连通的最少的边。最小生
成树可以用 kruskal( 克鲁斯卡尔 ) 算法或 prim( 普里姆 ) 算法求出。
:
最小生成树性质:设 G=(V,E)是一个连通网络, U 是顶点集 V 的一
v 一
个非空真子集。 若(u, )是 G 中一条 “ 个端点在 U 中(例如:u∈ U),
另一个端点不在 U 中的边(例如: v∈ V-U),且( u,v)具有最小权
值,则一定存在 G 的一棵最小生成树包括此边( u, v)。
:
计算稠密图的最小生成树最早是由罗伯特・ 普里姆在 1957 年发明的,
即 Prim 算法。之后艾兹赫尔・戴克斯特拉也独自发明了它。但该算
法的基本思想是由沃伊捷赫・亚尔尼克于 1930 年发明的。所以该算
k k
法有时候也被称为 Jarní 算法或者 Prim-Jarní 算法。 20 世纪 70 年
代,优先队列发明之后很快被用在了寻找稀疏图中的最小生成树上。
1984 年,迈克尔・ 弗里德曼和罗伯特・ 塔扬发明了斐波那契堆, Prim
V
算法所需要的运行时间在理论上由 E log E提升到了 E + V log 。约瑟
夫・克鲁斯卡尔在 1956 年发表了他的算法, 在他的论文中提到了 Prim
算法的一个变种, 而奥塔卡尔・ 布卢瓦卡在 20 世纪 20 年代的论文中
就已经提到了该变种。  在 1961 年重新发现了该算法, 该算法
后成为实现较好渐进性能的最小生成树算法和并行最小生成树算法
的基础。
:
生成树和最小生成树有许多重要的应用。 例如:要在 n 个城市之间铺
设光缆,主要目标是要使这 n 个城市的任意两个之间都可以通信,
但铺设光缆的费用很高, 且各个城市之间铺设光缆的费用不同, 因此
另一个目标是要使铺设光缆的总费用最低。 这就需要找到带权的最小
生成树。
:
求 MST 的一般算法可描述为:针对图 G,从空树 T 开始,往集合 T
中逐条选择并加入 n-1 条安全边( u, v),最终生成一棵含 n-1 条边
的 MST。
当一条边( u,v)加入 T 时,必须保证 T∪ {(u,v)}仍是 MST 的子集,
我们将这样的边称为 T 的安全边。
 Prim 算法简述
1).输入:一个加权连通图,其中顶点集合为 V,边集合为 E