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 扩大。‌终止‌当 SV 时A 包含 n−1 条边且无环构成 MST。‌‌Kruskal 算法正确性证明Kruskal 算法按权值递增顺序遍历边若边连接两个不同连通分量则加入。‌连通分量即切割‌算法维护的森林中每条候选边 (u,v) 连接两个不同树连通分量 Cu,Cv​。此时切割(Cu​,V−Cu​) 尊重当前边集 A。‌轻量级保证‌由于边按权值排序(u,v) 是连接 Cu​ 与其他分量的所有边中权值最小的否则更小的边已被处理并合并了分量。‌安全加入‌根据切割性质(u,v) 是安全边。重复此过程直至所有点连通所得即为 MST。‌‌两种算法本质都是‌贪心策略‌在 MST 问题上的应用通过确保每一步加入的边都是“安全”的从而保证全局最优。‌‌