最小生成树理论基础:
第一个证明: 第二个证明:
那么明白了这两个基础理论 对于prim算法 维护的集合S可以看成一个连通块,每一个不在集合中的点也可以看成只有一个点的连通块,用基础理论二就知道它们的正确性。 对于kruskal算法,更直接。就是每次看两个连通块是否在一个集合是的话直接pass, 不是的话就连接起来因为边权已经按照从小到大排好序了,按照理论二也可得到正确性。