java怎么实现跳转到指定页面
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;i
算法的应用:
应用上面的这个模板基本上能解决一些常见的最小生成树的算法,例如像杭电上的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小时内删除侵权内容。
发表评论
暂时没有评论,来抢沙发吧~