prim 算法的证明

缘起

RT.

分析

其实Prim算法的正确性只需要考虑一个连通子图S. 那么断言——所有不属于S的顶点连到S的最短边一定属于MST. 因为你考虑任何一棵ST，一定得包含S吧? 令整个图为G，则G\S可以分成若干连通子图(G\S未必连通了). 那么G\S的连通分支们都需要有边能连接到S上. 因为这些连通分支彼此都不连通, 如果还没有边与S连通的话, 则G就不连通了. 这是不行的. (MST求的是连通图的MST) . 而连接到S的最短边e的不属于S的那个顶点记做u, 则u一定属于某个组成G\S的连通分支T. 如果e不属于MST的话，那么T和S在MST中一定得连通吧? 如果不是e的话, 我可以换成e缩小代价总和. 所以我们知道了一条重要性质

对于G的连通子图S，则G\S中到达S的最短边一定属于MST.

所以我们从任何一个顶点开始，它作为S（即伊始的S仅仅是单点集），则外界到S的最短边一定属于MST. 所以将这条边的另一个不属于S的端点加入S，使得S成为拥有2个顶点的集合. 则外界到S的最短边一定属于MST，所以再扩张一个顶点，这样扩张了n-1步之后，S=G. 已经不能再扩张了. 我们已经断言了n-1条边一定属于MST. 而MST就是n-1条边. 所以我们恰好求得了n-1条边. prim算法正确.