最小生成树算法——普里姆算法

普里姆算法

假设G=(V,E)是一个具有n个顶点的连通网,T=(U,TE)是Ｇ的最小生成树，其中U是T的顶点集，TE是Ｔ的边集，U和TE的初始值为空。算法过程：

1. 首先从V中任取一个顶点（假定v₁)，将它并入U中，此时U={v₁}
2. 然后只要Ｕ是Ｖ的真子集（即U⊂Ｖ），就从那些一个端点已在Ｔ中，别一个端点仍在Ｔ外的所有边中，找一条最短（即权值最小）边，假定为(v_i,v_j)，其中v_i ∈U,v_j ∈V-U，并把边(v_i,v_j)和顶点v_j分别并入Ｔ的边集TE和顶点集Ｕ，如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后把所有n个顶点都并入到生成树T的顶点集，此时U=V，TE中包含n-1条边，T就是最后得到的最小生成树。

prim算法的步骤：

1.将顶点集合分成两个部分——Ｕ（选中的部分），Ｖ（未选中的部分）

2.每次从两个部分中找出权值最小的边

3.相连的顶点划入Ｕ中

4.重复１，直到顶点全部划入Ｕ中。

为了方便实现算法，附设一个辅助数组minedge[vtxptr]，记录从U到V-U具有最小代价的边（即权值最小的边）。对每个顶点v∈V-U，在辅助数组中存在一个minedge[v]分量。每个分量包括两个域：ver域存储该边附在Ｕ中的顶点，lowcost域则存储该边上的权值。

具体算法如下：

#include <stdio.h>
// 最大顶点数
#define MaxVertexNum 50

typedef char VertexType;
typedef int Adjmatrix;
// 邻接矩阵
typedef struct { VertexType vex[MaxVertexNum];// 顶点数组,类型假定为char Adjmatrix arcs[MaxVertexNum][MaxVertexNum];// 邻接矩阵,类型假定为int
}MGraph;

typedef int VRType;
typedef struct{ VertexType ver; VRType lowcost;
}MinEdge[MaxVertexNum];
MinEdge minedge;// 从顶点集U到V-U的代价最小的边的辅助数组

// 返回顶点u在MGraph的vex数组中的下标，以此作为顶点u在辅助数组中的下标
// 若G中存在顶点u，则返回该顶点在图中的位置；否则返回-1
int vtxNum(MGraph G,int u,int n){ // u是顶点，n是图Ｇ的顶点总数 int k; for(k = 0;k < MaxVertexNum;k++){ if(G.vex[k] == u){ return k; } } return -1;
}
int min(MGraph G,MinEdge MINI,int n){ int i=0,j,k,min; while(!MINI[i].lowcost){ i++; } min = MINI[i].lowcost;// 第一个不为0的值 k=i; for(j = i+1;j < n;j++){ if(MINI[j].lowcost > 0 && MINI[j].lowcost<min){ min = MINI[j].lowcost; k=j; } } return k;// 返回最小值在辅助数组中的序号
}
void prim(MGraph G,VertexType u,int n){ // G是采用邻接矩阵存储结构表示的图,u是顶点，n是顶点个数,以u作为出发点 int k,v,j; k=vtxNum(G,u,n);// 取顶点u在辅助数组中的下标 for(v = 0;v<n;v++){// 辅助数组初始化,v是每个顶点,此处是初始顶点u与顶点v的关系 if(v!=k){ minedge[v].ver = u;//顶点域全部赋值为u点 minedge[v].lowcost = G.arcs[k][v];//距离域全部赋值为u到其他点的距离 } } // 初始化，U={u} minedge[k].lowcost = 0; for(j = 0;j < n;j++){ k=min(G,minedge,n);//k为辅助数组中值最小的点对应的序号 printf("edge:%d-%d",minedge[k].ver,G.vex[k]);// 输出生成树的边 minedge[k].lowcost = 0;// 第k顶点并入U集合 for(v=0;v<n;v++){ if(G.arcs[k][v] < minedge[v].lowcost){ // 新顶点并入Ｕ集合后，重新选择最小边 minedge[v].ver=G.vex[k]; minedge[v].lowcost=G.arcs[k][v]; } } }
}
  
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
 

推荐看一个视频：https://b23.tv/BV19J411n76b

文章来源: blog.csdn.net，作者：WongKyunban，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/weixin_40763897/article/details/105487546