最小生成树kruskal算法证明

### Kruskal算法构建最小生成树的正确性证明

#### 边的选择与贪心策略
Kruskal算法采用了一种基于边的贪心策略，即每次都选择当前可用的最短边加入到正在构建的最小生成树中[^1]。为了确保所选边不会形成环路，该算法利用了并查集的数据结构来进行高效的连通性检测。

#### 关键性质分析
- **无环特性**：当向现有森林中的任意两棵树之间添加一条新边时，只要这两棵树原本并不相连，则新增加的这条边一定不会造成循环。这是因为任何闭合路径至少需要三个节点参与构成，在仅有两个独立顶点间建立连接的情况下不可能形成闭环。

- **最优子结构性质**：假设存在某个时刻T，在此之前已经选择了若干条安全边形成了部分MST G'=(V',E')。那么对于剩余未处理的所有边而言，仍然可以从这些候选者当中继续挑选满足条件的安全边来扩充G'直至最终完成整个MST构造过程而不影响全局最优解的存在性和唯一性（如果有）。这一结论依赖于这样一个事实：在一个连通图里，无论怎样划分成多个互不相交的小区域，各区域内各自形成的局部MST组合起来也必定会是最优的整体解决方案之一[^2]。

#### 归纳推理
设P(k)表示经过k轮迭代操作后得到的部分MST P_k是原图的一棵合法子树，并且它的总权重不大于其他任何形式相同规模大小但不属于标准形态下的子树Q_k。显然有：

- 初始状态P(0)=∅显然是成立的；
- 假定命题对i=k的情况有效，现在考察第k+1步执行完毕后的状况。此时按照算法逻辑必然会选取一条跨越不同组件之间的轻量级桥梁e*作为下一个成员纳入进来更新为新的部分MST P_(k+1)，而依据前述讨论可知这样的决策总是合理的并且有助于维持甚至提升整体效益水平。因此可以断言P(i+1)同样保持真值不变。

综上所述，通过上述论证方式可以看出Kruskal方法确实能够在理论上保证求得正确的最小生成树结果[^4]。

def kruskal_algorithm(edges, n):
    edges.sort(key=lambda edge: edge[2])  # Sort all the edges by weight
    
    parent = list(range(n))
    
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        rootX = find(x)
        rootY = find(y)
        if rootX != rootY:
            parent[rootX] = rootY
            
    minimum_spanning_tree = []
    for u, v, w in edges:
        if find(u) != find(v):  # Check cycle formation using Union-Find structure
            union(u, v)
            minimum_spanning_tree.append((u, v, w))

    return minimum_spanning_tree