当前位置: 首页 > >

普里姆算法(Prim算法求最小生成树)

发布时间:

普里姆算法的基本思想:普里姆算法是一种构造最小生成树的算法,它是按逐个将顶点连通的方式来构造最小生成树的。时间复杂度为O(n^2)。
从连通网络N = { V, E }中的某一顶点u0出发,选择与它关联的具有最小权值的边(u0, v),将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中,而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把该边加入到生成树的边集TE中,把它的顶点加入到集合U中。如此重复执行,直到网络中的所有顶点都加入到生成树顶点集合U中为止。
假设G=(V,E)是一个具有n个顶点的带权无向连通图,T(U,TE)是G的最小生成树,其中U是T的顶点集,TE是T的边集,则构造G的最小生成树T的步骤如下:
(1)初始状态,TE为空,U={v0},v0∈V;
(2)在所有u∈U,v∈V-U的边(u,v)∈E中找一条代价最小的边(u′,v′)并入TE,同时将v′并入U;
重复执行步骤(2)n-1次,直到U=V为止。
假设图G采用邻接矩阵g存储,对应的Prim(g,v)算法如下:
/*注:closest[j]存储该边依附的在U中的顶点编号。对于每一个顶点v∈V-U,closest[v]为U中距离v最*的一个邻接点。
lowcost域存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值;即边(v,closest[v])是在所有与顶点v相邻、且其另一顶点j∈U的边中具有最小权值的边,其最小权值为lowcost[v],即lowcost[v]=cost[v][closest[v]
adjvex域记录生成树顶点集合外各顶点距离集合内哪个顶点最*(即权值最小)。
*/
void Prim(MatGraph g,int v) //输出求得的最小生树的所有边
{
int lowcost[MAXVEX]; //建立数组lowcost
int closest[MAXVEX]; //建立数组closest
int min,i,j,k;
for (i=0;i



友情链接: