最小生成树证明贪心选择性

### 贪心选择性质在最小生成树中的证明

对于最小生成树(MST)，贪心选择性质表明，在构建MST的过程中，总是可以选择权重最小的边来加入当前正在形成的树中，只要这条边不会形成环路。这种策略能够保证最终得到的是连接所有顶点且总权重最小的一棵树。

#### 定义与假设
设G=(V,E)是一个连通无向图，其中每条边都有一个正权值w(e)[^1]。定义T为该图的一个最小生成树。考虑任意切割(S,V-S)，即把节点集划分为两个不相交子集S和V-S，并假定存在一条横跨此切割的轻量级边(u,v)(u属于S而v不属于S)，那么：

- 如果(u,v)不在任何已知的最小生成树上，则可以找到一个新的最小生成树T'，它包含了(u,v)；
- 新的最小生成树T'可以通过替换原来跨越这个切分的另一条更重的边实现；

#### 证明过程
为了验证上述断言的有效性，采用反证法来进行说明:

1. 假设不存在这样的最小生成树T',使得其包含轻量级边(u,v);
2. 设原最小生成树记作T0;
3. 将轻量级边(u,v)添加到T0中会构成唯一回路C;
4. C必定含有至少一条不同于(u,v)并连接集合S和(V-S)之间的其他边(x,y);
5. 因为选择了(u,v)作为最短路径上的边，所以有 w(u,v)<=w(x,y);
6. 删除(x,y)并将(u,v)加入新的树结构里，这样就形成了另一个生成树 T';
7. 显然新生成树T' 的总成本不超过原来的T0的成本，因此也是一棵最小生成树;

由此得出结论：如果有一条轻量级边(u,v)满足条件，则一定可以在某个最小生成树内发现它的身影。这也就意味着每次挑选出来的都是局部最优解——也就是所谓的“贪心选择”。

def add_edge_to_mst(mst_edges, edge):
    u, v, weight = edge
    
    # Check if adding this edge forms a cycle with existing edges in MST.
    if not forms_cycle(mst_edges | {edge}):
        mst_edges.add(edge)

def kruskal_algorithm(edges):
    sorted_edges = sort_by_weight(edges)
    
    mst_edges = set()
    for edge in sorted_edges:
        add_edge_to_mst(mst_edges, edge)
        
    return mst_edges