最小生成树
给定一无向带权图,顶点数是n,要使图连通只需n-1条边,若这n-1条边的权值和最小,则称有这n个顶点和n-1条边构成了图的最小生成树(minimum-cost spanning tree)。
Prim算法
Prim算法是解决最小生成树的常用算法。它采取贪心策略,从指定的顶点开始寻找最小权值的邻接点。图G=<V,E>,初始时S={V0},把与V0相邻接,且边的权值最小的顶点加入到S。不断地把S中的顶点与V-S中顶点的最小权值边加入,直到所有顶点都已加入到S中。
算法说明
为了方便寻找最小权值的边,构建一最近边结构体CloseEdge:
- //最近边
- typedef struct closeedge_tag
- {
- int adjvex; //邻接点
- int weight; //权值
- }CloseEdge;
实例
从V0开始
- int minTree(int n)
- {
- int i,j;
- memset(v,0,sizeof(v));
- v[0]=1;
- sum=0;
- for(i=1;i<n;i++)
- {
- min=max;
- for(j=0;j<n;j++) //在剩余定点中,找到最小路径值的定点
- {
- if(!v[j]&&map[0][j]<min)
- {
- min=map[0][j];
- flag=j;
- }
- }
- sum+=min;
- v[flag]=1;
- for(j=0;j<n;j++) //加入新定点后,导致连通分量到其他顶点距离变化
- {
- if(!v[j]&&map[0][j]>map[flag][j])
- {
- map[0][j]=map[flag][j];
- }
- }
- }
- return sum;
- }