Kruskal 算法教程：从原理到代码示例

1. 简介

在图论中，最小生成树（Minimum Spanning Tree, MST）是一个无向加权连通图的子图，它连接了所有的顶点，并且没有循环，同时边的权重之和最小。Kruskal 算法是一种贪心算法，用于找到这样的最小生成树。

2. 算法原理

Kruskal 算法的核心思想是：不断地选择权重最小的边，并将该边所连接的两个顶点加入到生成树中，直到所有顶点都被连接起来，形成一个最小生成树。在这个过程中，需要避免形成环路。

具体步骤如下：

1. 初始化：

   • 将图中的所有边按照权重从小到大进行排序。
   • 创建一个空的集合来表示最小生成树。
   • 创建一个并查集（Union-Find）数据结构来维护顶点的连通性，初始时每个顶点自成一个集合。

2. 迭代：

   • 从排序后的边集中依次取出权重最小的边。
   • 使用并查集判断该边的两个顶点是否属于同一个集合（即是否已经连通）。
   • 如果两个顶点不属于同一个集合，则将它们合并到同一个集合中，并将该边加入到最小生成树的集合中。
   • 如果两个顶点属于同一个集合，则说明加入该边会形成环路，因此舍弃该边。

3. 终止：

   • 重复步骤 2，直到最小生成树集合中包含了 (V - 1) 条边，其中 V 是顶点的数量。此时，最小生成树构建完成。

3. 图示

假设我们有以下无向加权连通图：

A---(4)---B
| \ / |
(8) (11) (8)
| \ / |
C---(7)---D---(9)---E
| | \ / |
(2) (6) (10) (14)
| | \ / |
F---(1)---G---(2)---H
|
(4)
|
I

使用 Kruskal 算法构建最小生成树的过程如下：

1. 排序边： 将所有边按照权重从小到大排序：
   (F, G, 1), (C, F, 2), (G, H, 2), (A, B, 4), (G, I, 4), (D, F, 6), (C, D, 7), (A, C, 8), (B, D, 8), (D, E, 9), (D, G, 10), (A, H, 11), (E, H, 14)

2. 迭代选择边：

   • 选择 (F, G, 1)，F 和 G 不连通，加入 MST。
   • 选择 (C, F, 2)，C 和 F 不连通，加入 MST。
   • 选择 (G, H, 2)，G 和 H 不连通，加入 MST。
   • 选择 (A, B, 4)，A 和 B 不连通，加入 MST。
   • 选择 (G, I, 4)，G 和 I 不连通，加入 MST。
   • 选择 (D, F, 6)，D 和 F 不连通，加入 MST。
   • 选择 (C, D, 7)，C 和 D 已连通（通过 C-F-D），舍弃。
   • 选择 (A, C, 8)，A 和 C 已连通（通过 A-B-?-F-C, ?为其它相连的点），舍弃。
   • 选择 (B, D, 8)，B 和 D 已连通（通过 B-A-?-F-D, ?为其它相连的点），舍弃。
   • 选择 (D, E, 9)，D 和 E 不连通，加入 MST。

3. 终止： 此时 MST 中已有 (9 - 1) = 8 条边，算法结束。

最终得到的最小生成树如下：

```
A---(4)---B

|

(8)
|
C D---(9)---E
| |
(2) (6)
| |
F---(1)---G---(2)---H
|
(4)
|
I
```

4. 代码示例 (Python)

```python
class UnionFind:
def init(self, vertices):
self.parent = {v: v for v in vertices}
self.rank = {v: 0 for v in vertices}

def find(self, v):
    if self.parent[v] != v:
        self.parent[v] = self.find(self.parent[v])
    return self.parent[v]

def union(self, v1, v2):
    root1 = self.find(v1)
    root2 = self.find(v2)
    if root1 != root2:
        if self.rank[root1] > self.rank[root2]:
            self.parent[root2] = root1
        elif self.rank[root1] < self.rank[root2]:
            self.parent[root1] = root2
        else:
            self.parent[root2] = root1
            self.rank[root1] += 1

def kruskal(graph):
edges = []
for u in graph:
for v, weight in graph[u]:
edges.append((u, v, weight))

edges.sort(key=lambda x: x[2])  # Sort edges by weight

mst = []
uf = UnionFind(graph.keys())

for u, v, weight in edges:
    if uf.find(u) != uf.find(v):
        uf.union(u, v)
        mst.append((u, v, weight))

return mst

Example graph represented as an adjacency list

graph = {
'A': [('B', 4), ('C', 8), ('H', 11)],
'B': [('A', 4), ('D', 8)],
'C': [('A', 8), ('D', 7), ('F', 2)],
'D': [('B', 8), ('C', 7), ('E', 9), ('F', 6), ('G', 10)],
'E': [('D', 9), ('H', 14)],
'F': [('C', 2), ('D', 6), ('G', 1)],
'G': [('D', 10), ('F', 1), ('H', 2), ('I', 4)],
'H': [('A', 11), ('E', 14), ('G', 2), ('I', 4)],
'I': [('G', 4), ('H', 4)]
}

minimum_spanning_tree = kruskal(graph)
print("Minimum Spanning Tree:")
for u, v, weight in minimum_spanning_tree:
print(f"{u} - {v}: {weight}")

```

代码解释:

• UnionFind 类: 实现了并查集数据结构，用于判断两个顶点是否连通以及合并两个集合。
  • find(v): 查找顶点 v 所属的集合的根节点。
  • union(v1, v2): 合并顶点 v1 和 v2 所属的集合。
• kruskal(graph) 函数: 实现了 Kruskal 算法。
  • edges: 存储所有边的列表，每个元素是一个元组 (u, v, weight)，表示顶点 u 和 v 之间的边的权重为 weight。
  • mst: 存储最小生成树的边的列表。
  • uf: UnionFind 类的实例，用于处理顶点的连通性。
• 示例图 graph: 使用邻接表表示图。

5. 复杂度分析

• 时间复杂度： O(E log E)，其中 E 是边的数量。主要的时间开销在于对边进行排序。如果使用更高效的排序算法，例如基数排序，时间复杂度可以降至接近 O(E)。并查集的操作（find 和 union）的时间复杂度接近常数。
• 空间复杂度： O(V + E)，其中 V 是顶点的数量，E 是边的数量。需要存储顶点、边以及并查集的数据。

6. 总结

Kruskal 算法是一种简单高效的构建最小生成树的贪心算法。它易于理解和实现，适用于各种类型的无向加权连通图。通过结合并查集数据结构，可以有效地避免环路的产生，确保生成的树是最小生成树。理解 Kruskal 算法的原理和实现步骤，对于解决图论中的相关问题以及进行算法设计都具有重要意义。