关于prim算法
先把有的点放于一个集合(或者数组)里,这个集合里存放的是所有走过的点。初始值为0或者false表示还没有点
声明一个一维数组用于记录各点的权值[可理解为起始点到目标点的距离],
声明一个二维数组用于记录某点到某一点的权值,如果这两点不可达到,则设置为无穷大
具体执行过程:
先从某一点开始,把这一个开始的点放于声明的一个数组或者集合里,表明这一点已经被访问过。然后再从余下的n-1个点里去找那个权值最小的点并记录该点的位置然后再加上这一点的权值,同时将该点放于集合里表明该点已初访问。再更新权值
再看下图,从下图分析:
1、
先选取一个点作起始点,然后选择它邻近的权值最小的点(如果有多个与其相连的相同最小权值的点,随便选取一个)。如1作为起点。
isvisited[1]=1; //表明把1加进来说明是已经访问过
pos=1; //记录该位置
//用dist[]数组不断刷新最小权值,dist[i](0<i<=点数)的值为:i点到邻近点(未被标记)的最小距离。
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算法的实现:
算法的应用:
应用上面的这个模板基本上能解决一些常见的最小生成树的算法,例如像杭电上的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
关于这些题目在我的博客里都有详细的代码
我的博客链接地址:
HDOJ1863:http://blog.csdn.net/jiahui524/article/details/6642903
HDOJ1875:http://blog.csdn.net/jiahui524/article/details/6642912
HDOJ1879:http://blog.csdn.net/jiahui524/article/details/6642916
HDOJ1233:http://blog.csdn.net/jiahui524/article/details/6642920
HDOJ1162:http://blog.csdn.net/jiahui524/article/details/6642895
HDOJ1301:http://blog.csdn.net/jiahui524/article/details/6642924
分享到:
相关推荐
代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小生成树Prim算法代码代码 最小...
最小生成树_Prim算法实现C++ 最小生成树_Prim算法实现C++ 最小生成树_Prim算法实现C++
基于MATLAB的最小生成树Prim算法 源代码程序.rar
最小生成树prim最小生成树prim最小生成树prim最小生成树prim
普里姆算法通过寻找无向图中权值最小的边,并且将其组合成最小生成树,也就是图的相对最短路径,同时将最小生成树以点集的形式输出,便于观察
prim算法 Kruskal算法分别实现最小生成树
图论算法:最小生成树——Prim算法和Kruskal算法C 实现
自己写的Prim算法,求最小生成树,若看不明白,请参看《算法导论》中的详细描述。
本文本采用的是java编写的最小生成树Prim算法,参考书:计算机算法设计与分析
最小生成树的prim算法
最小生成树Prim算法朴素版 C语言实现最小生成树Prim算法朴素版 C语言实现
基于matlab的最小生成树的prim算法,有详细的解释,可直接运行
acm 最小生成树 prim算法 用并查集实现 思路简单清晰,适合初学最小生成树的人
PRIM算法,C语言,VC6.0通过,直接复制。数据结构(清华版)实验。输入事例: 5 8//中间要空格 ABCDE AB 8 //中间要空格 AC 4 AE 3 BD 8 BE 6 CD 10 CE 13 DE 12 输出 AE 3 AC 4 BE 6 BD 8
使用Prim算法编写的最小生成树(C语言),为更好地学习数据结构
图的应用————图的最小生成树prim算法
最小生成树prim算法与克鲁斯算法实现,通过图的遍历和生成树求解实现(邻接矩阵、邻接表 —图的深度广度遍历算法的实现和最小生成树PRIM和KRUSCAL算法的实现)
输入数据: 7 11 A B 7 A D 5 B C 8 B D 9 B E 7 C E 5 D E 15 D F 6 E F 8 E G 9 F G 11 输出: A - D : 5 D - F : 6 A - B : 7 B - E : 7 E - C : 5 E - G : 9 Total:39
第1关求图(邻接矩阵存储)最小生成树的普里姆(Prim)算法 第2关求图(邻接表存储)最小生成树的普里姆(Prim)算法 第3关求图(邻接矩阵存储)最小生成树的克鲁斯卡尔(Kruskal)算法 第4关求图(邻接表存储)最小...
MATLAB源码集锦-最小生成树Prim算法代码