实现最小生成树（MST）的Kruskal算法

题目描述
最小生成树（Minimum Spanning Tree, MST）是指在连通加权无向图中，选取一部分边构成一棵树，使得树包含图中所有顶点，且所有边的权值之和最小。Kruskal算法是求解MST的经典贪心算法之一，其核心思想是从小到大遍历所有边，如果边连接的两个顶点当前不在同一连通分量中，则将该边加入生成树，直到生成树包含所有顶点（即选取了n-1条边）。你需要理解Kruskal算法的步骤、正确性证明，并能够用代码实现。

解题过程讲解
我将分步拆解Kruskal算法的原理、数据结构选择、实现细节和复杂度分析，帮助你彻底掌握。

1. 核心思路

Kruskal算法的操作可以概括为：

• 排序：将图中所有边按权值从小到大排序。
• 贪心选择：依次遍历每条边，如果当前边连接的两个顶点在“当前生成森林”中属于不同的连通分量（即加入该边不会形成环），则选择这条边加入生成树。
• 终止条件：当已选择的边数等于顶点数减1时，算法结束。

关键点：判断两个顶点是否属于同一连通分量，这需要用到并查集（Union-Find） 数据结构来高效维护。

2. 数据结构准备

假设图有V个顶点、E条边，通常用边列表（Edge List）存储图，每条边包含：起点u、终点v、权值weight。

并查集（Union-Find）的作用：

• 初始时每个顶点自成一个集合（连通分量）。
• 当考虑边(u, v)时，查询u和v所属的集合代表（find操作），如果不同，则选择该边，并合并两个集合（union操作）；如果相同，说明u和v已连通，加入会形成环，故舍弃。

3. 逐步推演示例

考虑以下无向连通图（顶点0~3）：

边列表（u, v, weight）:
(0, 1, 10)
(0, 2, 6)
(0, 3, 5)
(1, 3, 15)
(2, 3, 4)

步骤：

1. 按边权排序：
   (2,3,4) → (0,3,5) → (0,2,6) → (0,1,10) → (1,3,15)
2. 初始化并查集：每个顶点独立集合 {0}, {1}, {2}, {3}，已选边数=0。
3. 处理(2,3,4)：find(2)≠find(3)，选择，union(2,3)，集合变为{0},{1},{2,3}，已选边=1。
4. 处理(0,3,5)：find(0)≠find(3)，选择，union(0,3)，集合变为{0,2,3},{1}，已选边=2。
5. 处理(0,2,6)：find(0)==find(2)（都属于{0,2,3}），舍弃（会形成环）。
6. 处理(0,1,10)：find(0)≠find(1)，选择，union(0,1)，集合变为{0,1,2,3}，已选边=3。
7. 已选边数 = 3 = V-1，算法结束。
   生成树边为：(2,3,4), (0,3,5), (0,1,10)，总权值=19。

4. 伪代码实现

class DSU:  # 并查集实现
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0]*n
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        return True

def kruskal(vertices, edges):
    """
    vertices: 顶点数V
    edges: 列表，每个元素为(u, v, weight)
    返回：(MST权值和, MST边列表)
    """
    edges.sort(key=lambda x: x[2])  # 按边权升序排序
    dsu = DSU(vertices)
    mst_weight = 0
    mst_edges = []
    
    for u, v, w in edges:
        if dsu.union(u, v):  # 如果合并成功，说明该边可加入MST
            mst_weight += w
            mst_edges.append((u, v, w))
            if len(mst_edges) == vertices - 1:
                break
    return mst_weight, mst_edges

5. 复杂度分析

• 时间复杂度：
  • 排序边：O(E log E)
  • 并查集操作：E次find/union，单次近似O(α(V))（α为反阿克曼函数，可视为常数）
  • 总复杂度：O(E log E) 或 O(E log V)（因为E ≤ V²，log E = O(log V)），通常表达为O(E log E)。
• 空间复杂度：O(V + E)（存储图、并查集、结果）。

6. 正确性简要证明

Kruskal的贪心选择是安全的，可以用“切割性质”证明：

• 对图的任意一个切割（将顶点分成两个集合），如果一条边是跨越这个切割的最小权边，那么这条边一定在某个最小生成树中。
• 算法按边权从小到大的顺序考虑每条边，在决定是否加入时，该边是当前连接两个不同连通分量的最小边（因为更小的边之前已处理过且未形成环），因此它满足切割性质，属于MST。

7. 对比Prim算法

• Kruskal：基于边操作，适合稀疏图（E远小于V²）。
• Prim：基于顶点操作，类似Dijkstra，适合稠密图（邻接矩阵存储时效率更高）。

两者都能得到正确的最小生成树，但适用场景不同。

核心要点回顾

• Kruskal算法是贪心法，按边权升序选择，用并查集判断环。
• 实现关键在于：排序 + 并查集。
• 理解“切割性质”是证明其正确性的基础。
• 实际编码时注意图的顶点编号（通常0-based）和边列表的输入格式。