kruskal算法的证明

缘起

RT.

分析

kruskal算法的本质是使用最小代价连接两个不同的连通分支（一开始假设没有任何边，则就是n个连通分支，每个连通分支都是单点集）, 则连通分支个数-1，直至最后连通分支的个数为1.

类似于prim算法的证明（【1】）. 我们断言——连通分支S外部连接S的最短边一定属于MST. 证明完全相同——因为总得连接，如果不是这条最短边, 则可以用最短边换掉.

则我们首先将边排序，则拿出最短的边，连通分支个数-1，然后逐步考察剩余的边（按照边长从小到大），遇到第一个连接不同连通分支的边（并查集判断）根据上述断言它一定是MST中的边. 取之. 然后继续. 注意，每取一次连通分支就少1，而最终连通分支的个数一定是1，所以整个kruskal过程我们断言了n-1条边在MST中. 而MST就恰好n-1条边(多了就会有环).所以kruskal算法得到了MST，是一个正确的算法.

参考

【1】https://yfsyfs.github.io/2019/08/22/prim-%E7%AE%97%E6%B3%95%E7%9A%84%E8%AF%81%E6%98%8E/