VC驿站

 找回密码
 加入驿站

QQ登录

只需一步,快速开始

搜索
查看: 624|回复: 0

[分享] 上课了解析Prim算法的具体C语言编程实现

[复制链接]
79_avatar_middle
在线会员 发表于 2017-5-31 10:37:48 | 显示全部楼层 |阅读模式
以下是具体代码:
  1. #include <stdio.h>
  2. #include <cstdlib>
  3. #include<memory.h>
  4. const int Max =0x7fffffff;
  5. const int N=50;

  6. int n;
  7. int g[N][N],dis[N],visited[N];

  8. int prim()
  9. {
  10.     int i,j;
  11.     int pos,min;
  12.     int ans=0;
  13.     memset(visited,0,sizeof(visited));
  14.     visited[1]=1;pos=1;
  15.     //assign a value to the dis[N] first
  16.     for(i=2;i<=n;i++)
  17.         dis[i]=g[pos][i];
  18.     for(i=1;i<n;i++)
  19.     {
  20.         min=Max;
  21.         for(j=1;j<=n;j++)
  22.         {
  23.             if(visited[j]==0&&min>dis[j])
  24.             {
  25.                 min=dis[j];
  26.                 pos=j;
  27.             }
  28.         }
  29.         printf("The node being traversed is :%d\n",pos);
  30.         ans+=min;
  31.         printf("The value of ans is %d\n",ans);
  32.         //mark the node
  33.         visited[pos]=1;
  34.         //update the weight
  35.         for(j=1;j<=n;j++)
  36.             if(visited[j]==0&&dis[j]>g[pos][j])
  37.                 dis[j]=g[pos][j];
  38.     }
  39.     return ans;
  40. }

  41. int main()
  42. {
  43.     int i=1,j=1;
  44.     int ans=0;
  45.     int w;
  46.     printf("Please enter the number of the nodes:\n");
  47.     scanf("%d",&n);
  48.     for(i=1;i<=n;i++)
  49.         for(j=1;j<=n;j++)
  50.         {
  51.             if(i==j)
  52.                 g[i][j]=0;
  53.             else
  54.                 g[i][j]=Max;
  55.         }
  56.     printf("Please enter the number of the edges:\n");
  57.     int edgenum;
  58.     scanf("%d",&edgenum);
  59.     int v1,v2;
  60.     printf("Please enter the number and the corresponding weight:\n");
  61.     for(i=1;i<=edgenum;i++)
  62.     {
  63.         scanf("%d%d%d",&v1,&v2,&w);
  64.         g[v1][v2]=g[v2][v1]=w;
  65.     }
  66.     ans=prim();
  67.     printf("The sum of the weight of the edges is:%d\n",ans);
  68.     system("pause");
  69.     return 0;
  70.      
  71. }
复制代码


上课了给出的程序运行后的结果截图
上课了解析Prim算法的具体C语言编程实现




上一篇:C++中多线程与Singleton(单例)的那些事儿
下一篇:Linux下C++访问MySQL
您需要登录后才可以回帖 登录 | 加入驿站 qq_login

本版积分规则

关闭

站长提醒上一条 /2 下一条

QQ|小黑屋|手机版|VC驿站 ( 辽ICP备09019393号tongdun|网站地图wx_jqr

GMT+8, 2019-3-20 16:13

Powered by Discuz! X3.4

© 2009-2019 cctry.com

快速回复 返回顶部 返回列表