Kruskal算法原理与实现

1. 问题描述

Kruskal算法是用于在加权无向图中寻找最小生成树的一种贪心算法。最小生成树是一棵包含原图所有顶点的树，并且这棵树的所有边的权重之和最小。Kruskal算法的核心思想是：按照边的权重从小到大依次选择边，如果这条边连接的两个顶点不在当前的生成树连通分量中（即加入这条边不会形成环），则将这条边加入最小生成树。

2. 算法核心思想

算法的本质是一个基于“边”的贪心选择过程，其正确性依赖于“切割性质”：对于一个图的一个切割，连接两个不同部分的最小权重边一定属于图的最小生成树。Kruskal算法不断选择当前未选择过的最小权重边，并确保其加入后不会形成环，直到选择了(V-1)条边（V为顶点数）。

3. 详细步骤拆解

我们通过一个具体例子来讲解。假设有图如下（顶点V=4，边E=5）：
顶点: 0, 1, 2, 3
边: (0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)
（格式：顶点u, 顶点v, 权重w）

步骤1：初始化

• 将所有边按照权重从小到大排序。排序后结果：
  (2, 3, 4)
  (0, 3, 5)
  (0, 2, 6)
  (0, 1, 10)
  (1, 3, 15)
• 准备一个结果列表mst_edges，用于存储最终组成最小生成树的边。初始为空。
• 准备一个关键数据结构：并查集，用于高效地判断两个顶点是否已经连通（即是否在同一个集合中）。初始时，每个顶点自成一个集合。

步骤2：遍历排序后的边
我们按权重从小到大，依次检查每条边(u, v)。

1. 处理边(2, 3, 4):

• 在并查集中查找顶点2的根节点和顶点3的根节点。初始时，它们根节点分别是2和3，不同。
• 因为根节点不同，意味着加入这条边不会形成环。于是：
• 将这条边加入mst_edges。
• 在并查集中，将顶点2和顶点3所在的集合合并（Union操作）。现在{2, 3}在一个集合中。

2. 处理边(0, 3, 5):

• 查找顶点0的根（0）和顶点3的根（现在是2）。根不同。
• 不会形成环。将边(0, 3, 5)加入mst_edges。
• 合并顶点0和顶点3所在集合。现在{0, 2, 3}在一个集合中。

3. 处理边(0, 2, 6):

• 查找顶点0的根和顶点2的根。此时0的根是2（因为上一步合并后，集合的代表元可能是2），顶点2的根也是2。根相同。
• 这意味着顶点0和2已经在同一个连通分量中。加入这条边会形成一个环。因此跳过这条边。

4. 处理边(0, 1, 10):

• 查找顶点0的根（2）和顶点1的根（1）。根不同。
• 不会形成环。将边(0, 1, 10)加入mst_edges。
• 合并顶点0和1所在集合。现在所有顶点{0, 1, 2, 3}都在一个集合中了。

步骤3：终止条件
此时，mst_edges中已经包含了3条边。对于具有V=4个顶点的树，恰好需要(V-1)=3条边。因此算法结束。

得到的最小生成树包含的边是：(2,3,4), (0,3,5), (0,1,10)，总权重=4+5+10=19。

4. 关键数据结构：并查集的作用

为什么需要并查集？在上述过程中，我们需要频繁判断两个顶点是否连通，以及在加入边后合并两个连通分量。并查集提供了两个高效的操作：

• Find(u)：查找顶点u所在集合的代表元（根节点）。用于判断u和v是否属于同一集合。
• Union(u, v)：合并u和v所在的集合。通常在加入一条新边后执行。
  通过路径压缩和按秩合并优化，这两个操作的平均时间复杂度可以接近常数O(α(n))，其中α(n)是增长极慢的反阿克曼函数。

5. 算法伪代码

Kruskal(Graph G):
    mst_edges = []  // 存储最小生成树的边
    sort all edges in G by weight in ascending order
    
    uf = new UnionFind(G.V)  // 初始化并查集，每个顶点一个集合

    for each edge (u, v, w) in sorted_edges:
        if uf.find(u) != uf.find(v):  // 如果u和v不连通
            mst_edges.add( (u, v, w) )
            uf.union(u, v)  // 合并两个集合
            if len(mst_edges) == G.V - 1:
                break  // 已找到V-1条边，可提前结束
    return mst_edges

6. 复杂度分析

• 时间复杂度：主要开销来自排序边，O(E log E)。由于E的最大可能值是O(V^2)，所以也可以表示为O(E log V)。并查集操作近似线性，总体复杂度由排序主导。
• 空间复杂度：O(V + E)。存储边和并查集结构。

7. 与Prim算法的对比

• Kruskal算法基于边操作，适合稀疏图（边数E远小于顶点数V^2）。
• Prim算法基于顶点操作，适合稠密图。
• 两者都是贪心算法，都能得到全局最优的最小生成树。

8. 总结

Kruskal算法的核心是“按权重排序边，用并查集判环”。其步骤清晰，实现相对简单，是解决最小生成树问题的经典方法。理解并查集在其中的作用是掌握该算法的关键。