算法札记：Kruskal 和 Prim 算法的正确性
Kruskal 和 Prim 算法的正确性均基于最小生成树（MST）的切割性质：对于图的任意切割（将顶点分为两个不相交集合），横跨切割且权值最小的边（轻量级边）一定属于某棵最小生成树。
核心证明逻辑：切割性质
设 G=(V,E) 为连通加权无向图，A 是包含在某棵 MST 中的边子集。若 (S,V−S) 是尊重 AA 的任意切割（即 A 中无边横跨该切割），且 (u,v) 是横跨该切割的一条轻量级边，则 (u,v)(u,v) 对 AA 是安全的（即A∪{(u,v)} 仍包含在某棵 MST 中）。
证明思路（反证法）：
- 假设存在一棵包含 A 的 MST， T 不包含 (u,v)。
- 将 (u,v) 加入 T，必形成环。该环中必存在另一条横跨切割 (S,V−S) 的边 (x,y)（因为 u,v 分属切割两侧）。
- 由于 (u,v) 是轻量级边，故 w(u,v)≤w(x,y)。
- 构造新树 T′=T−{(x,y)}∪{(u,v)}，其总权值w(T′)=w(T)−w(x,y)+w(u,v)≤w(T)。
- 因 T 已是 MST，故 w(T′)=w(T)，即 T′ 也是 MST 且包含 (u,v)。矛盾得证。
Prim 算法正确性证明
Prim 算法每次从已选顶点集 S 到未选顶点集 V−S 的横跨边中选取权值最小的边。
- 贪心选择：每一步选择的边 (u,v) 恰好是切割 (S,V−S) 下的轻量级边。
- 归纳维持：初始时 S={v0}，边集 A=∅ 显然尊重切割。每步加入安全边后，AA 仍包含在某 MST 中，且 S 扩大。
- 终止：当 S=V 时，A 包含 n−1 条边且无环，构成 MST。
Kruskal 算法正确性证明
Kruskal 算法按权值递增顺序遍历边，若边连接两个不同连通分量则加入。
- 连通分量即切割：算法维护的森林中，每条候选边 (u,v) 连接两个不同树（连通分量 Cu,Cv）。此时切割(Cu,V−Cu) 尊重当前边集 A。
- 轻量级保证：由于边按权值排序，(u,v) 是连接 Cu 与其他分量的所有边中权值最小的（否则更小的边已被处理并合并了分量）。
- 安全加入：根据切割性质，(u,v) 是安全边。重复此过程直至所有点连通，所得即为 MST。
两种算法本质都是贪心策略在 MST 问题上的应用，通过确保每一步加入的边都是“安全”的，从而保证全局最优。