什么是循环不变式

循环不变式的主体是不变式。它有三个过程:初始、保持、结束:

综上,初始 和 保持 是条件,结束是结论。简而言之,如果不变式,在循环前和每次循环后都成立,那么循环结束时,它仍然是成立的。


证明Prim算法

首先说明Prim算法的执行过程(设v为图g的顶点集):

下面开始证明Prim算法:

综上,d是不存在的,因此,T1是G1的最小生成树。
根据循环不变式,在循环结束时,得到的生成树就是最小生成树。