Prim算法的实现及应用( 最小生成树)

网友投稿 302 2022-08-27

Prim算法的实现及应用( 最小生成树)

关于prim算法

先把有的点放于一个集合(或者数组)里,这个集合里存放的是所有走过的点。初始值为0或者false表示还没有点

具体执行过程:

再看下图,从下图分析:

1、

先选取一个点作起始点,然后选择它邻近的权值最小的点(如果有多个与其相连的相同最小权值的点,随便选取一个)。如1作为起点。

isvisited[1]=1;   //表明把1加进来说明是已经访问过

pos=1; //记录该位置

//用dist[]数组不断刷新最小权值,dist[i](0

dist[1]=0;  //起始点i到邻近点的最小距离为0

dist[2]=map[pos][2]=4;

dist[3]=map[pos][3]=2;

dist[4]==map[pos][4]=3;

dist[5]=map[pos][5]=MaxInt;  //无法直达

dist[6]=map[pos][6]=MaxInt;

2、

再在伸延的点找与它邻近的两者权值最小的点。

//dist[]以3作当前位置进行更新

isvisited[3]=1;

pos=3;

dist[1]=0;   //已标记,不更新

dist[2]=map[pos][2]=4;  //比5小,不更新

dist[3]=2;  //已标记,不更新

dist[4]=map[pos][4]=3;   //比1大,更新

dist[5]=map[pos][5]=MaxInt;

dist[6]=map[pos][6]=MaxInt;

3、最后的结果:

当所有点都连同后,结果最生成树如上图所示。

所有权值相加就是最小生成树,其值为2+1+2+4+3=12。

prim算法的实现:

//prim算法int prim(int n){ int i,j,min,pos; int sum=0; memset(isvisited,false,sizeof(isvisited)); //初始化 for(i=1;i<=n;i++){ dist[i]=map[1][i]; } //从1开始 isvisited[1]=true; dist[1]=MAX; //找到权值最小点并记录下位置 for(i=1;imap[pos][j]){ dist[j]=map[pos][j]; } } } return sum;}

算法的应用:

应用上面的这个模板基本上能解决一些常见的最小生成树的算法,例如像杭电上的ACM题目:

题目链接地址:

HDOJ1863:​​http://acm.hdu.edu.cn/showproblem.php?pid=1863​​

HDOJ1875:​​http://acm.hdu.edu.cn/showproblem.php?pid=1875​​

HDOJ1879:​​http://acm.hdu.edu.cn/showproblem.php?pid=1879​​

HDOJ1233:​​http://acm.hdu.edu.cn/showproblem.php?pid=1233​​

HDOJ1162:​​http://acm.hdu.edu.cn/showproblem.php?pid=1162​​

HDOJ1301:​​http://acm.hdu.edu.cn/showproblem.php?pid=1301​​

版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系我们jiasou666@gmail.com 处理,核实后本网站将在24小时内删除侵权内容。

上一篇:营销要学会适可而止!(如何做到适可而止)
下一篇:最小树(一)(prim最小生成树)
相关文章

 发表评论

暂时没有评论,来抢沙发吧~