Kruskal算法

题目描述
给定一个带权无向图，包含n个节点和m条边，每条边有权重。要求找出图的最小生成树（MST），即包含所有节点且边权总和最小的树。你需要实现Kruskal算法来解决这个问题。

解题过程

1. 理解最小生成树

   • 最小生成树是连接图中所有节点的树形子图，且总边权最小
   • 树的性质：n个节点的树有n-1条边，且无环

2. Kruskal算法核心思想

   • 将边按权重从小到大排序
   • 按顺序选择边，如果加入该边不会形成环，则加入最小生成树
   • 使用并查集（Union-Find）来高效检测环

3. 详细步骤

   步骤1：数据结构准备

   # 边类定义
   class Edge:
       def __init__(self, u, v, weight):
           self.u = u      # 起点
           self.v = v      # 终点  
           self.weight = weight  # 权重
   
   # 并查集实现
   class UnionFind:
       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):
           rootX = self.find(x)
           rootY = self.find(y)
   
           if rootX == rootY:
               return False  # 已经在同一集合
   
           # 按秩合并
           if self.rank[rootX] < self.rank[rootY]:
               self.parent[rootX] = rootY
           elif self.rank[rootX] > self.rank[rootY]:
               self.parent[rootY] = rootX
           else:
               self.parent[rootY] = rootX
               self.rank[rootX] += 1
           return True
   

   步骤2：算法主流程

   def kruskal(n, edges):
       # 初始化
       uf = UnionFind(n)
       mst = []  # 存储最小生成树的边
       total_weight = 0
   
       # 按边权排序
       edges.sort(key=lambda x: x.weight)
   
       # 遍历所有边
       for edge in edges:
           if len(mst) == n - 1:
               break  # 已找到n-1条边
   
           # 检查加入该边是否形成环
           if uf.union(edge.u, edge.v):
               mst.append(edge)
               total_weight += edge.weight
   
       return total_weight, mst
   

4. 具体示例演示

   考虑以下图：

   节点：0, 1, 2, 3
   边：
   0-1: 权重10
   0-2: 权重6  
   0-3: 权重5
   1-3: 权重15
   2-3: 权重4
   

   执行过程：

   • 边排序：2-3(4), 0-3(5), 0-2(6), 0-1(10), 1-3(15)
   • 选择2-3：无环，加入MST
   • 选择0-3：无环，加入MST
   • 选择0-2：形成环(0-3-2-0)，跳过
   • 选择0-1：无环，加入MST
   • 已找到3条边，算法结束

   结果： MST包含边[2-3, 0-3, 0-1]，总权重19

5. 复杂度分析

   • 时间复杂度：O(m log m)，主要来自边排序
   • 空间复杂度：O(n + m)，存储并查集和边列表

6. 算法特点

   • 适合稀疏图（边较少）
   • 实现相对简单
   • 需要先对所有边排序
   • 使用并查集高效检测环