三种最小生成树算法的简要比较：Kruskal算法, 破圈法(管梅谷), Prim算法

本文针对之前常常弄混Kruskal算法, 破圈法(管梅谷), Prim算法这三种算法的问题，仅仅简单地总结Kruskal算法, 破圈法(管梅谷), Prim算法在求最小生成树时的思路的区别。

如果目的是为了比较这三种算法的复杂度、优缺点等高级的区别，请参考其他文章。

1. Kruskal算法

克鲁斯克尔(Kruskal):1928年生，一家3弟兄都是数学家，1954年 在普林斯顿大学获博士学位，导师是著名的ErdÖs,他大部分研究工作是 数学和语言学，主要在贝尔实验室工作。1956年发表包含克鲁斯 克尔算法论文，使他名声大振。

思路：从G中的最小边开始，进行避圈式扩张。

2. 破圈法(管梅谷)

管梅谷（１９３４－）。我国著名数学家，曾任山东师范大学校 长。中国运筹学会第一、二届常务理事，第六届全国政协委员。从 事运筹学及其应用的研究，对最短投递路线问题的研究取得成果 ， 冠名为中国邮路问题，该问题被列入经典图论教材 和著作。

思路：从赋权图G的任意圈开始， 去掉该圈中权值最大的一条边，称为破圈。不断破圈，直到G中没 有圈为止，最后剩下的G的子图为G的最小生成树。

3. Prim算法

Prim(1921---) 1949年在普林斯顿大学获博士学位，是Sandia公司副总裁。

从G中的任意点开始，选择关联的权重最小且不生成圈的边添加，直到得到最小生成树。

总结：(下面的话是对的，但原因尚不清楚，建议参考拟阵相关知识)

这三个算法都是基于贪婪算法的思想设计的(一个从最小边开始，一个从任意全开始，一个从任意点开始)，每一步选择局部最优，从而期望得到全局最优的算法。

• 如果组合优化问题满足拟阵的结构，则可以使用适当的贪婪算法得到最优解，如这三个算法。
• 不满足拟阵结构的问题，贪婪算法可能得不到最优解，如旅行商问题(TSP).