Prim算法的基本思想是对图G(V,E)设置集合S来存放已被访问的顶点,然后执行n次下面的步骤。
(1)每次从集合V-S中选择与集合S最近的一个顶点,访问u并将其加入集合S,同时把这条集合S最近的边加入最小生成树中。
(2)令顶点u作为集合S与集合V-S连接的接口,优化从u能到达的未访问顶点v与集合S的最短距离。
代码:
1 #include <iostream> 2 #include <algorithm> 3 using namespace std; 4 const int MAXV = 1000; //最大顶点数 5 const int INF = 100000000; 6 7 int n,m,G[MAXV][MAXV]; //n为顶点数,MAXV为最大顶点数 8 int d[MAXV]; //顶点与集合S的最短距离 9 bool vis[MAXV] = {false}; //标记数组 10 11 int prim(){ 12 fill(d,d+MAXV,INF); 13 d[0]=0; //只有0号顶点到集合S的距离为0,其余全为INF 14 int ans=0; //最小生成树边权之和 15 for(int i=0;i<n;i++){ 16 int u=-1,MIN=INF; //u使d[u]最小,MIN存放该最小的d[u] 17 for(int j=0;j<n;j++){ //找到未访问的顶点中d[]最小的 18 if(vis[j]==false&&d[j]<MIN){ 19 u=j; 20 MIN=d[j]; 21 } 22 } 23 //找不到小于INF的d[u],则剩下的顶点和集合S不连通 24 if(u==-1) 25 return -1; 26 vis[u]=true; 27 ans+=d[u]; 28 for(int v=0;v<n;v++){ 29 //v未访问&& u能到达v &&以u为中介点可以使v离集合S更近 30 if(vis[v]==false&&G[u][v]!=INF&&G[u][v]<d[v]){ 31 d[v]=G[u][v]; 32 } 33 } 34 } 35 return ans; 36 } 37 int main() 38 { 39 int u,v,w; 40 cout<<"请输入顶点个数和边数:"<<endl; 41 cin>>n>>m; //顶点个数 边数 42 cout<<"输入u,v和边权:"<<endl; 43 fill(G[0],G[0]+MAXV*MAXV,INF); 44 for(int i=0;i<m;i++){ 45 cin>>u>>v>>w; //输入u,v,边权 46 G[u][v]=G[v][u]=w; 47 } 48 cout<<"最小生成树边权之和为:"<<prim()<<endl; 49 return 0; 50 }
测试结果:
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论,欢迎说说您的想法!