prim算法的贪心策略,证明prim算法构造的就是最小生成树

Prim算法是一种贪心算法，它的贪心策略是每次选取当前生成树的边集与剩余边集之间权值最小的边作为生成树的一条边，直到生成树包含所有顶点为止。

我们可以采用反证法证明Prim算法构造的就是最小生成树。

假设Prim算法构造的不是最小生成树，而是另一棵生成树T'，则T'的权值和一定大于最小生成树T的权值和。

设T'与T的边集分别为E'和E，根据Prim算法的贪心策略，每次选取的边在E'和E之间一定是权值最小的边，因此，对于任意一条边e'∈E'，一定存在一条边e∈E，使得e'的权值大于e的权值。

将T'中的一条边e'用e替换掉，得到一棵新的生成树T''。由于e的权值小于e'的权值，因此T''的权值和一定小于T'的权值和。

重复以上过程，直到T''等于T为止。因此，Prim算法构造的就是最小生成树。

综上所述，Prim算法的贪心策略可以保证构造出最小生成树。