最小生成树之Prim算法

最小生成树之Prim算法2015-09-18Prim算法：

假设N = （V，{E}）是连通网，TE是N上最小生成树中边的集合。算法从U={u0}（u0属于V），TE={}开始，重复执行下述操作：在所有u属于U，v属于V-U的边（u,v）属于E中找到一条代价最小的边（u0,v0）并入集合TE,同时v0并入U，直至U=V为止，此时TE中必有n-1条边，则T=（V，{TE}）为N的最小生成树.

为实现这个算法，需附设一个辅助数组closedge,以记录从U到V-U具有最小代价的边。对每个顶点vi属于V-U,在辅助数组中存在一个相应分量closedge[i-1],它包括两个域，lowcost域存储该边的权,vex域存储该边依附的在U中的顶点。