kruskal 算法正确性的证明作者带提高组的学生比较多在教学最小生成树相关内容的时候比如最小生成树的求解、唯一性等等…学生的反馈通常都比较糟糕所以这里整理一下我关于 kruskal 算法的一些理解。而 prim 的基本原理其实和 kruskal 类似再加上篇幅不宜太长这里就先不讨论了。大多数 kruskal 算法的内容都是基于其正确性的证明我们需要明白为什么可以这样做所以这里先聊一聊正确性的问题。最小生成树MST问题给定一张无向连通带权图GGG生成树是指从GGG中选取部分边构成一棵包含所有顶点且无环的树生成树的边权和为所有边的权值之和。最小生成树Minimum Spanning Tree, MST是指在所有可能的生成树中边权和最小的那棵可能不唯一。以上内容来自网络kruskal 算法的求解过程将所有的边按照权值从小到大进行排序选择当前可用边里面权值最小的边尝试将其加入到生成树当中这里我们通常使用并查集来进行判断如果加入这条边会导致出现环那么就跳过否则将其加入到生成树当中重复步骤 2直到生成树当中包含了所有顶点为止。正确性证明这里我们给无向连通图的每一条边一个编号通过 kruskal 算法我们得到了一个生成树TTT这棵树包含n−1n - 1n−1条边。接下来我们使用反证法来证明 kruskal 算法的正确性假设存在一个与TTT不同的生成树T′TT′而这棵生成树的边权之和要小于原本的TTT。然后这里有两个性质我们可以把T′TT′看作删除了TTT中的某一些边然后添加了一些其他的边得到的当然了这些边全是GGG中的对应的我们可以把生成树T′TT′的方法理解为先选择无向图中权值较大的一些边而不是最小的直到生成树当中包含了所有顶点为止跟 kruskal 恰好相反。我们先来看第一个性质假设我们删除了TTT中的一些边这些边为a1,a2,…,aka_1, a_2, \ldots, a_ka1,a2,…,ak。在我们删除a1,a2,…,aka_1, a_2, \ldots, a_ka1,a2,…,ak之后整棵树被拆分成了若干棵子树下一步我们需要再按照其他的方式使得生成树权值之和变得更小再把所有的子树重新连接起来。那么这里其实我们可以视这些子树为一个一个的点重新做一遍最小生成树问题。例如上图在删除 1 和 5 两条边之后我们可以认为整棵树只有三个点分别对应三棵子树需要再添加两条边使得他们连起来。那么这里要处理的问题变成了给你一个无向图然后给你两种完全不同的边的方案分别为a1,a2,…,aka_1, a_2, \ldots, a_ka1,a2,…,ak和b1,b2,…,bkb_1, b_2, \ldots, b_kb1,b2,…,bk其中a1,a2,…,aka_1, a_2, \ldots, a_ka1,a2,…,ak是按照 kruskal 算法求解的而b1,b2,…,bkb_1, b_2, \ldots, b_kb1,b2,…,bk是按照性质 2 所说的方法求解的。我们需要证明不存在任何一种性质 2 的方法使得生成树的边权之和比 kruskal 算法的边权之和要小。剩下来的就好办了我们把两种方案的边按照权值从小到大进行排序a1a_1a1和b1b_1b1分别表示两种方案中权值最小的边。根据性质 2显然a1a_1a1要小于b1b_1b1换而言之a1a_1a1比b1,b2,…,bkb_1, b_2, \ldots, b_kb1,b2,…,bk都要小。假设选择b1,b2,…,bkb_1, b_2, \ldots, b_kb1,b2,…,bk这些边生成的树长成下面的样子黑色部分而红色的边表示a1a_1a1只要我删除从 x 到 y 路径上的任意一条边换成a1a_1a1就可以得到一个比T′TT′边权和更小的生成树 —— 因为a1a_1a1比b1,b2,…,bkb_1, b_2, \ldots, b_kb1,b2,…,bk都要小。所以我们证明了不存在任何一种性质 2 的方法使得生成树的边权之和比 kruskal 算法的边权之和要小。那么到此为止就证明了 kruskal 算法的正确性。
kruskal 算法正确性的证明
发布时间：2026/6/13 12:56:16
kruskal 算法正确性的证明作者带提高组的学生比较多在教学最小生成树相关内容的时候比如最小生成树的求解、唯一性等等…学生的反馈通常都比较糟糕所以这里整理一下我关于 kruskal 算法的一些理解。而 prim 的基本原理其实和 kruskal 类似再加上篇幅不宜太长这里就先不讨论了。大多数 kruskal 算法的内容都是基于其正确性的证明我们需要明白为什么可以这样做所以这里先聊一聊正确性的问题。最小生成树MST问题给定一张无向连通带权图GGG生成树是指从GGG中选取部分边构成一棵包含所有顶点且无环的树生成树的边权和为所有边的权值之和。最小生成树Minimum Spanning Tree, MST是指在所有可能的生成树中边权和最小的那棵可能不唯一。以上内容来自网络kruskal 算法的求解过程将所有的边按照权值从小到大进行排序选择当前可用边里面权值最小的边尝试将其加入到生成树当中这里我们通常使用并查集来进行判断如果加入这条边会导致出现环那么就跳过否则将其加入到生成树当中重复步骤 2直到生成树当中包含了所有顶点为止。正确性证明这里我们给无向连通图的每一条边一个编号通过 kruskal 算法我们得到了一个生成树TTT这棵树包含n−1n - 1n−1条边。接下来我们使用反证法来证明 kruskal 算法的正确性假设存在一个与TTT不同的生成树T′TT′而这棵生成树的边权之和要小于原本的TTT。然后这里有两个性质我们可以把T′TT′看作删除了TTT中的某一些边然后添加了一些其他的边得到的当然了这些边全是GGG中的对应的我们可以把生成树T′TT′的方法理解为先选择无向图中权值较大的一些边而不是最小的直到生成树当中包含了所有顶点为止跟 kruskal 恰好相反。我们先来看第一个性质假设我们删除了TTT中的一些边这些边为a1,a2,…,aka_1, a_2, \ldots, a_ka1,a2,…,ak。在我们删除a1,a2,…,aka_1, a_2, \ldots, a_ka1,a2,…,ak之后整棵树被拆分成了若干棵子树下一步我们需要再按照其他的方式使得生成树权值之和变得更小再把所有的子树重新连接起来。那么这里其实我们可以视这些子树为一个一个的点重新做一遍最小生成树问题。例如上图在删除 1 和 5 两条边之后我们可以认为整棵树只有三个点分别对应三棵子树需要再添加两条边使得他们连起来。那么这里要处理的问题变成了给你一个无向图然后给你两种完全不同的边的方案分别为a1,a2,…,aka_1, a_2, \ldots, a_ka1,a2,…,ak和b1,b2,…,bkb_1, b_2, \ldots, b_kb1,b2,…,bk其中a1,a2,…,aka_1, a_2, \ldots, a_ka1,a2,…,ak是按照 kruskal 算法求解的而b1,b2,…,bkb_1, b_2, \ldots, b_kb1,b2,…,bk是按照性质 2 所说的方法求解的。我们需要证明不存在任何一种性质 2 的方法使得生成树的边权之和比 kruskal 算法的边权之和要小。剩下来的就好办了我们把两种方案的边按照权值从小到大进行排序a1a_1a1和b1b_1b1分别表示两种方案中权值最小的边。根据性质 2显然a1a_1a1要小于b1b_1b1换而言之a1a_1a1比b1,b2,…,bkb_1, b_2, \ldots, b_kb1,b2,…,bk都要小。假设选择b1,b2,…,bkb_1, b_2, \ldots, b_kb1,b2,…,bk这些边生成的树长成下面的样子黑色部分而红色的边表示a1a_1a1只要我删除从 x 到 y 路径上的任意一条边换成a1a_1a1就可以得到一个比T′TT′边权和更小的生成树 —— 因为a1a_1a1比b1,b2,…,bkb_1, b_2, \ldots, b_kb1,b2,…,bk都要小。所以我们证明了不存在任何一种性质 2 的方法使得生成树的边权之和比 kruskal 算法的边权之和要小。那么到此为止就证明了 kruskal 算法的正确性。
的演进与通信机制)
