xxx 最小生成树问题（Kruskal算法）

题目描述：
给定一个连通无向图G=(V,E)，其中V是顶点集，E是边集，每条边e∈E有一个权重w(e)。要求找到一个边集T⊆E，使得图G'=(V,T)是连通的，并且所有边的权重之和最小。这样的边集T称为图的最小生成树。

解题过程：

步骤1：理解最小生成树的基本概念

• 生成树：包含图中所有顶点的无环连通子图
• 最小生成树：所有生成树中边权重之和最小的那个
• Kruskal算法采用贪心策略，每次选择权重最小的边，同时保证不形成环

步骤2：算法核心思想
Kruskal算法的基本思想是：

1. 将图中所有边按权重从小到大排序
2. 按排序后的顺序依次考虑每条边
3. 如果加入当前边不会形成环，则将其加入最小生成树
4. 重复直到选择了|V|-1条边（生成树有n个顶点时恰有n-1条边）

步骤3：数据结构准备
需要两种关键数据结构：

• 并查集（Union-Find）：用于高效判断是否形成环
• 最小堆或排序数组：用于按权重排序边

步骤4：详细算法步骤

步骤4.1：初始化

1. 创建并查集数据结构，每个顶点自成一个集合
2. 将图中所有边按权重升序排序
3. 初始化最小生成树T为空集
4. 设置计数器count=0（记录已选边数）

步骤4.2：处理每条边

对于排序后的每条边(u,v,w)，按顺序处理：
  1. 使用并查集检查顶点u和v是否在同一个集合中
     - 如果find(u) ≠ find(v)：说明u和v不在同一连通分量，加入边(u,v)不会形成环
        a. 将边(u,v)加入最小生成树T
        b. 执行union(u,v)，合并u和v所在的集合
        c. count = count + 1
  2. 如果count = |V|-1，算法结束

步骤5：并查集操作详解

查找操作find(x)：

def find(x, parent):
    if parent[x] != x:
        parent[x] = find(parent[x], parent)  # 路径压缩
    return parent[x]

合并操作union(x,y)：

def union(x, y, parent, rank):
    root_x = find(x, parent)
    root_y = find(y, parent)
    
    if root_x != root_y:
        # 按秩合并，小树合并到大树
        if rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        elif rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        else:
            parent[root_y] = root_x
            rank[root_x] += 1

步骤6：完整算法实现

def kruskal(n, edges):
    # 初始化并查集
    parent = [i for i in range(n)]
    rank = [0] * n
    
    # 按边权重排序
    edges.sort(key=lambda x: x[2])
    
    mst = []  # 最小生成树
    total_weight = 0
    edges_used = 0
    
    for u, v, w in edges:
        if edges_used == n - 1:
            break
            
        root_u = find(u, parent)
        root_v = find(v, parent)
        
        if root_u != root_v:
            mst.append((u, v, w))
            total_weight += w
            edges_used += 1
            union(root_u, root_v, parent, rank)
    
    return mst, total_weight

步骤7：时间复杂度分析

• 边排序：O(E log E)
• 并查集操作：O(α(V))近似常数时间，其中α是反阿克曼函数
• 总时间复杂度：O(E log E + E α(V)) ≈ O(E log E)
• 由于E ≤ V²，也可表示为O(E log V)

步骤8：正确性证明（贪心选择性质）
Kruskal算法的正确性基于以下关键观察：

• 安全性：每次选择的权重最小的跨切割边必然属于某个最小生成树
• 最优子结构：在选择了某条边后，问题简化为在剩余图上找最小生成树

步骤9：实例演示
考虑一个6顶点图：

顶点：0,1,2,3,4,5
边：(0,1,4), (0,2,4), (1,2,2), (1,0,4), (2,0,4), 
    (2,1,2), (2,3,3), (2,5,2), (2,4,4), (3,2,3),
    (3,4,3), (4,2,4), (4,3,3), (5,2,2), (5,4,3)

执行过程：

1. 排序边：(1,2,2), (2,5,2), (2,3,3), (3,4,3), (5,4,3), ...
2. 选择(1,2,2)，合并{1,2}
3. 选择(2,5,2)，合并{1,2,5}
4. 选择(2,3,3)，合并{1,2,3,5}
5. 选择(3,4,3)，合并{1,2,3,4,5}
6. 选择(0,1,4)，合并{0,1,2,3,4,5}
7. 已选5条边，算法结束

步骤10：算法特点总结

• 优点：简单直观，适合稀疏图（E ≈ V）
• 缺点：对稠密图效率不如Prim算法
• 应用：网络设计、聚类分析、图像分割等

通过以上步骤，Kruskal算法系统地构建了最小生成树，保证了全局最优解，同时具有较高的执行效率。