2023年8月1日发(作者：)

最⼩⽣成树的Prim算法以及Kruskal算法的证明Prime算法的思路：从任何⼀个顶点开始，将这个顶点作为最⼩⽣成树的⼦树，通过逐步为该⼦树添加边直到所有的顶点都在树中为⽌。其中添加边的策略是每次选择外界到该⼦树的最短的边添加到树中（前提是⽆回路）。Prime算法的正确性证明：引理1：对于连通图中的顶点vi，与它相连的所有边中的最短边⼀定是属于最⼩⽣成树的。引理2：证明：假设最⼩⽣成树已经建成；(vi, vj)是连接到顶点vi的最短边，在最⼩⽣成树中取出vi，断开连接到vi的边，则⽣成树被拆分成

1、顶点vi

2、顶点vj所在的连通分量（单独⼀个顶点也看作⼀个独⽴的连通分量）

3、其余若⼲个连通分量（个数⼤于等于0）

三个部分

现在要重建⽣成树，就要重新连接之前被断开的各边

虽然不知道之前被断开的都是哪⼏条边，但是可以通过这样⼀个简单的策略来重建连接：将vi分别以最⼩的成本逐个连接到这若⼲个互相分离的连通分量；具体来说，就是要分别遍历顶点vi到某个连通分量中的所有顶点的连接，然后选择其中最短的边来连接vi和该连通分量；⽽要将vi连接到vj所在的连通分量，显然通过边(vi, vj)连接的成本最低，所以边(vi, vj)必然属于最⼩⽣成树（如果连接到vi的最短边不⽌⼀条，只要任意挑选其中的⼀条(vi, vj)即可，以上的证明对于这种情况同样适⽤）。

这样我们就为原来只有⼀个顶点vi的⼦树添加了⼀个新的顶点vj及新边(vi, vj)；接下来只要将这棵新⼦树作为⼀个连通⼦图，并且⽤这个连通⼦图替换顶点vi重复以上的分析，迭代地为⼦树逐个地添加新顶点和新边即可。Kruskal算法：通过从⼩到⼤遍历边集，每次尝试为最⼩⽣成树加⼊当前最短的边，加⼊成功的条件是该边不会在当前已构建的图中造成回路，当加⼊的边的数⽬达到n-1，遍历结束。Kruskal算法的正确性证明：Kruskal算法每次为当前的图添加⼀条不会造成回路的新边，其本质是逐步地连接当前彼此分散的各个连通分量（单个顶点也算作⼀个连通分量），⽽连接的策略是每次只⽤最⼩的成本连接任意两个连通分量。这个策略之所以能够实现，是因为每加⼊⼀条边之后只会出现两种结果：1、在已有的连通分量中形成回路2、连接两个彼此独⽴的连通分量所以，通过从⼩到⼤遍历边集，判断是否会造成回路，然后逐条添加新边就可以实现上诉的连接策略接下来需要证明的是，为什么每次⽤最⼩成本连接两个连通分量，最后就可以⽣成⼀棵最⼩⽣成树（毕竟每⼀个当前的最优解之和未必是全局的最优解）借⽤在Prim算法中提到的那个判断就可以很⽅便地证明：“如果某个连通图属于最⼩⽣成树，那么所有从外部连接到该连通图的边中的⼀条最短的边必然属于最⼩⽣成树”通过这个判断，可以很容易地证明：当最⼩⽣成树被拆分成彼此独⽴的若⼲个连通分量的时候，所有能够连接任意两个连通分量的边中的⼀条最短边必然属于最⼩⽣成树（因为该边必然是这两个连通分量的可以连接到外部的最短边）。由此也就证明了，Kruskal算法通过每次以最⼩的成本来连接两个连通分量的策略确实可以正确地⽣成最⼩⽣成树。

prim算法中如果⽤优先队列来寻找距离⼀个点最近的点的话时间复杂度是O(ElogV)，⽽Kruskal算法⽤STL::sort（）函数对边进⾏排序的复杂度是O(|E|log|E|)，⽽并查集的复杂度是O(|E|)，所以整个算法的时间⼤多花费在对边进⾏排序上，总体时间复杂度⼤约是O(|E|log|E|)，所以对于稠密图来说prim算法更加有优势，⽽对于稀疏图来说，Kruskal算法更加有优势。

2023年8月1日发(作者：)

最⼩⽣成树的Prim算法以及Kruskal算法的证明Prime算法的思路：从任何⼀个顶点开始，将这个顶点作为最⼩⽣成树的⼦树，通过逐步为该⼦树添加边直到所有的顶点都在树中为⽌。其中添加边的策略是每次选择外界到该⼦树的最短的边添加到树中（前提是⽆回路）。Prime算法的正确性证明：引理1：对于连通图中的顶点vi，与它相连的所有边中的最短边⼀定是属于最⼩⽣成树的。引理2：证明：假设最⼩⽣成树已经建成；(vi, vj)是连接到顶点vi的最短边，在最⼩⽣成树中取出vi，断开连接到vi的边，则⽣成树被拆分成

1、顶点vi

2、顶点vj所在的连通分量（单独⼀个顶点也看作⼀个独⽴的连通分量）

3、其余若⼲个连通分量（个数⼤于等于0）

三个部分

现在要重建⽣成树，就要重新连接之前被断开的各边

虽然不知道之前被断开的都是哪⼏条边，但是可以通过这样⼀个简单的策略来重建连接：将vi分别以最⼩的成本逐个连接到这若⼲个互相分离的连通分量；具体来说，就是要分别遍历顶点vi到某个连通分量中的所有顶点的连接，然后选择其中最短的边来连接vi和该连通分量；⽽要将vi连接到vj所在的连通分量，显然通过边(vi, vj)连接的成本最低，所以边(vi, vj)必然属于最⼩⽣成树（如果连接到vi的最短边不⽌⼀条，只要任意挑选其中的⼀条(vi, vj)即可，以上的证明对于这种情况同样适⽤）。

这样我们就为原来只有⼀个顶点vi的⼦树添加了⼀个新的顶点vj及新边(vi, vj)；接下来只要将这棵新⼦树作为⼀个连通⼦图，并且⽤这个连通⼦图替换顶点vi重复以上的分析，迭代地为⼦树逐个地添加新顶点和新边即可。Kruskal算法：通过从⼩到⼤遍历边集，每次尝试为最⼩⽣成树加⼊当前最短的边，加⼊成功的条件是该边不会在当前已构建的图中造成回路，当加⼊的边的数⽬达到n-1，遍历结束。Kruskal算法的正确性证明：Kruskal算法每次为当前的图添加⼀条不会造成回路的新边，其本质是逐步地连接当前彼此分散的各个连通分量（单个顶点也算作⼀个连通分量），⽽连接的策略是每次只⽤最⼩的成本连接任意两个连通分量。这个策略之所以能够实现，是因为每加⼊⼀条边之后只会出现两种结果：1、在已有的连通分量中形成回路2、连接两个彼此独⽴的连通分量所以，通过从⼩到⼤遍历边集，判断是否会造成回路，然后逐条添加新边就可以实现上诉的连接策略接下来需要证明的是，为什么每次⽤最⼩成本连接两个连通分量，最后就可以⽣成⼀棵最⼩⽣成树（毕竟每⼀个当前的最优解之和未必是全局的最优解）借⽤在Prim算法中提到的那个判断就可以很⽅便地证明：“如果某个连通图属于最⼩⽣成树，那么所有从外部连接到该连通图的边中的⼀条最短的边必然属于最⼩⽣成树”通过这个判断，可以很容易地证明：当最⼩⽣成树被拆分成彼此独⽴的若⼲个连通分量的时候，所有能够连接任意两个连通分量的边中的⼀条最短边必然属于最⼩⽣成树（因为该边必然是这两个连通分量的可以连接到外部的最短边）。由此也就证明了，Kruskal算法通过每次以最⼩的成本来连接两个连通分量的策略确实可以正确地⽣成最⼩⽣成树。

prim算法中如果⽤优先队列来寻找距离⼀个点最近的点的话时间复杂度是O(ElogV)，⽽Kruskal算法⽤STL::sort（）函数对边进⾏排序的复杂度是O(|E|log|E|)，⽽并查集的复杂度是O(|E|)，所以整个算法的时间⼤多花费在对边进⾏排序上，总体时间复杂度⼤约是O(|E|log|E|)，所以对于稠密图来说prim算法更加有优势，⽽对于稀疏图来说，Kruskal算法更加有优势。