详解克鲁斯卡尔算法原理与使用方法

算法简介

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

适用情况

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

使用方法

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

例如：

边	权值
AB	4
AC	7
BC	8
BD	11
CE	2
DE	9
EF	10
EG	2
FG	6

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为边的数量。综上，该算法应用广泛，且具有较广的使用范围。