精选优质文档-倾情为你奉上最小生成树算法 问题描述设G=(V,E)是一个无向连通带权图，E中每条边(v,w)的权为c(v,w)。如果G的一个子图G是一棵包含G的所有顶点的书，则称G为G的生成树。生成树上各边权的总和称为该生成树的耗费，在G的所有生成树中，耗费最小的生成树就称为G的最小生成树。给定一个无向连通带权图，构造一个最小生成树。 设计思想利用Prim算法求最小生成树，Prim算法是利用贪心策略设计的算法。设G=(V,E)是一个连通带权图，V=1，2，n。构造G的一棵最小生成树的Prim算法的基本思想是：首先置U=1,然后，只要U是V的真子集，就做如下的贪心选择：选取满足条件iU,jV-U,且使c(i,j)达到最小的边(i,j),并将顶点j添加到U中。这个过程一致进行到U=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。 时间复杂度Prim算法的Pascal语言描述如下：Procedure PRIM(c:array1.n,1.n of real);Varlowcost:array
