算法简介

Kruskal算法是一种按照边权值递增的顺序构建最小生成树的算法，采用了贪心策略。具体来说，该算法按照边的权值从小到大的顺序，将边加入到生成树中去，但是必须保证加入的边不会与已经加入的边构成环，直到生成树中有n-1条边为止。

适用情况

Kruskal算法适用于稀疏图，即边数相对点数较少的图。

使用方法

1. 将边按照权值从小到大排序

例如：

2. 按照权值从小到大依次添加边，并判断是否形成环

例如，开始没有边，在添加AB边后，将点A和点B连通起来了。接着，添加CA边会形成环，因此不加入。之后，添加CE边，将点C和点E连通起来了。继续添加EG，FE，以及BC，连接点G、F、B、C、D。最后，成功生成了如下最小生成树：

    A    |  ---4------ |    |     | B    C     E |    |     | 11   7     2 |          | D          | |----9-----|      |      F      |      G

示例

示例一

有一个带权无向图，边的权值为：

         9             6   (0)------(1)------(2)   |         |         |  14         24        20   |         |         |   (3)------(4)------(5)          18            2

生成如下最小生成树：

    0    |  --9--  |     | 3     2 |     | 14   20 |     | 4     1 |     |-18--24-- |     | 5     | |     | --6---

示例二

某城市有多座节点，节点间路径距离为：

        A    B    C    D    E     A   0    12   14   16   20     B  12    0   24   20   32     C  14   24    0   10   22     D  16   20   10    0   18     E  20   32   22   18    0

通过Kruskal算法构建最小生成树，结果如下：

A---B---C|       |D       E

总结

Kruskal算法是解决生成树问题效率较高的进一步改进，时间复杂度为O（ElogE），其中E为边的数量。综上，该算法应用广泛，且具有较广的使用范围。