ITKeyword,专注技术干货聚合推荐

注册 | 登录

数据结构-Prim算法

yisuowushinian 分享于 2012-05-11

推荐:数据结构与算法:链表

数组和链表的区别是什么 找出单链表中的倒数第k个元素 如何检测一个较大的单链表是否有环 判断两个单链表无环是否交叉 删除单链表中的重复结点 如何在不知道头指

2020腾讯云共同战“疫”,助力复工(优惠前所未有!4核8G,5M带宽 1684元/3年),
地址https://cloud.tencent.com/act/cps/redirect?redirect=1053

2020阿里云最低价产品入口,含代金券(新老用户有优惠),
地址https://www.aliyun.com/minisite/goods

#include<stdio.h>
 #include<string.h>
 #define maxn 21
 #define inf 1000000
 int n,m;
 int edge[maxn][maxn];
 int lowcost[maxn];
 int nearvex[maxn];
 void prim(int u0)
 {
     int sumweight=0;
     int i,j;
     for(i=1;i<=n;i++)//顶点是从1开始
     {
         lowcost[i]=edge[u0][i];
         nearvex[i]=u0;
     }
     lowcost[u0]=0;
     nearvex[u0]=-1;
     for(i=1;i<n;i++)//将n-1个顶点加入到顶点集合T2
     {
         int min=inf;
         int v=-1;
         for(j=1;j<=n;j++)
         {
             if(nearvex[j]!=-1&&lowcost[j]<min)
             {
                 min=lowcost[j];
                 v=j;
             }
         }
         if(v!=-1)
         {
             printf("%d %d %d\n",nearvex[v],v,lowcost[v]);
             nearvex[v]=-1;
             sumweight+=lowcost[v];
             for(j=1;j<=n;j++)
             {
                 if(nearvex[j]!=-1&&edge[v][j]<lowcost[j])//j在T1集合中&&满足v到j的距离小于j到T2中顶点的最小值
             
                 {
                     lowcost[j]=edge[v][j];
                     nearvex[j]=v;
                 }
             }
         }
     }
     printf("sumweight of the mst is %d\n",sumweight);
 }
 int main()
 {
   int i,j;
   int u,v,w;
   scanf("%d%d",&n,&m);
   memset(edge,0,sizeof(edge));
   for(i=1;i<=m;i++)
   {
       scanf("%d%d%d",&u,&v,&w);
       edge[u][v]=edge[v][u]=w;
   }
   for(i=1;i<=n;i++)
   {
       for(j=1;j<=n;j++)
       {
           if(i==j)
               edge[i][j]=0;
           else if(edge[i][j]==0)
               edge[i][j]=inf;
 
       }
   }
 prim(1);//从顶点1中构造最小生成树
 return 0;
 }

prim 算法是基于顶点来实现最小生成树的,我们假设使用邻接矩阵来存储图的,在 prim 算法实现的过程中,我们需要知道以下两类信息

1.集合T1内各顶点到集合T2中个顶点的权值最小边的权值    //其中T2集合是表示这些集合中的点已经是最小生成树中的点了

2.集合T1内个顶点距离集合T2中哪个顶点的距离最小

为此,我们用两个数组来实现上面两类信息

lowcost[maxn]:用来实现1.

nearvex[maxn]:用来实现2.

实际上如果只是要计算最小生成树的最小代价是不需要使用nearvex[maxn]这个数组的,这个数组只是用来记录在构造最小生成树中的顶点的顺序。

推荐:数据结构与算法:图

图论是计算机研究的一个重要分支,有关图论的内容可以写很多,但正是因为图论的这种复杂性,在程序员面试笔试中,有关图论的问题并不多见,考察的也并不深奥。本

prim算法的思想:

初始:lowcost[k]=edge[v0][k] , nearvex[k]=v0;其中v0指的是从哪点来构造最小生成树。

当lowcost[i]=-1时我们让它表示i顶点加入到了T2集合,

什么样的情况下我们将i结点加入到T2集合呢?

我们选择那些在T1集合中,距离T2集合中点最小的lowcost[k],将该点k加入到集合T2中,

加入后我们应该改变那些在T1集合中点到T2集合中的最小权值,如果edge[k][i]<lowcost[i]

则将lowcost[i]=edge[k][i];nearvex[i]=k;这就完成了一次操作,进行n-1次后,就能构成一个最小生成树



推荐:数据结构之查找算法

转载请注明出处:http://blog.csdn.net/feng1790291543 顺序查找过程:从表中的最后一个记录开始,逐个进行记录的关键字与给定值进行比较,若某个记录的关键字与

#include<stdio.h> #include<string.h> #define maxn 21 #define inf 1000000 int n,m; int edge[maxn][maxn]; int lowcost[maxn]; int nearvex[maxn]; void prim(int u0) { int

相关阅读排行


相关内容推荐

最新文章

×

×

请激活账号

为了能正常使用评论、编辑功能及以后陆续为用户提供的其他产品,请激活账号。

您的注册邮箱: 修改

重新发送激活邮件 进入我的邮箱

如果您没有收到激活邮件,请注意检查垃圾箱。