Kruskal算法求最小生成树

一.  前言

Kruskal算法又称克鲁斯卡尔算法，在离散数学中又叫避圈法，是一种用来查找最小生成树的算法，由Joseph Kruskal在1956年发表，用来解决同样问题的还有Prim算法，我们先来引入最小生成树的概念

二.  最小生成树

设无向连通带权图G = <V,E,W>，T是G的一棵生成树，T的各边权之和称为T的权，记作W(T)，G的所有生成树中权最小的生成树，称为G的最小生成树，最小生成树若有n个结点，则有n-1条边

三.  Kruskal算法

1.  设n阶无向连通带权图G = <V,E,W>有m条边，将m条边的权按照从小到大的顺序排列，设为e1，e2，……em

2.  取e1 在T中，然后依次检查e2，e3……em，如果ej(j>=2)与已在T中的边不能构成回路，则取ej在T中，否则去掉ej

3.  当算法停止时，得到的T就是G的最小生成树

另外值得注意的是：

使用不同的遍历图的方法，可以得到不同的生成树；

从不同的顶点出发，也可能得到不同的生成树。

四.  举例

1.  用KruKal算法，求下图的最小生成树

2.  首先将权值从小到大排列：10 < 12 < 14 < 16 < 18 < 22 < 24 < 25 < 28

3.  接下来，先取权值最小的10，如下图

4.  再取12，如下图

5.  再取14，如下图

6.  再取16，如下图

7.  再取18，但是我们发现加上18后，构成了一个回路，所以18不可取，如下图

8.  再取22，如下图

9.  再取24，但是我们发现加上24后，构成了一个回路，所以24不可取，如下图

10.  再取25，如下图

11.  再取28，但是我们发现加上28后，构成了一个回路，所以28不可取，至此，最小生成树完成，如下图