首页 / 算法 / 算法起步之Prim算法
算法起步之Prim算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法起步之Prim算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1796字,纯文字阅读大概需要3分钟。
内容图文
![算法起步之Prim算法](/upload/InfoBanner/zyjiaocheng/1131/37794e3c5cd54eb2957f9d5d6a3f28cc.jpg)
prim算法是另一种最小生成树算法。他的安全边选择策略跟kruskal略微不同,这点我们可以通过一张图先来了解一下。
prim算法的安全边是从与当前生成树相连接的边中选择一条最短的一条,并且该边是应是生成树与生成树外一点的连接。
所以我们prim算法用汉字描述的过程应为:1初始化2构造最小优先队列,将所有节点都加入到最小优先队列中,所有节点的key设置为无穷大,开始节点设置成0。3循环,直到队列为空{取出key值最小的节点加入到生成树中,变量与key相连接的边,看是否是于树中的节点相连,如果不是且key值比队列中节点的key值小则更新队列中该节点的key值,最小优先队列排序}结束。
下面的代码就是按照刚才的过程实现的,有很多需要优化的地方,当然算法还需要根据具体的题目,选择最好的写法,这里只是给出思想。
public class Prim { private int MAX=1000; private int NULL=-1; public void prim(int[][]map){ Node[] nodes=new Node[map.length]; ArrayList list=new ArrayList(); for (int i = 1; i < map.length; i++) { list.add(new Node(i, NULL, MAX)); } list.add(new Node(0,NULL,0)); while(!list.isEmpty()){ Collections.sort(list); Node n=(Node) list.remove(1); System.out.println(n.getValue()+","+n.getLink()+","+n.getKey()); nodes[n.getValue()]=n; for (int i = 0; i < map.length; i++) { if(map[n.getValue()][i]!=0&&nodes[i]==null){ for (Object o : list) { Node node=(Node) o; if(node.getKey()==i&&map[n.getLink()][i]<node.getValue()){ node.setLink(n.getValue()); node.setKey(map[n.getLink()][i]); } } } } } } } class Node implements Comparable<Node>{ private int value; private int link; private int key; public int getValue() { return value; } public void setValue(int value) { this.value = value; } public int getLink() { return link; } public void setLink(int link) { this.link = link; } public int getKey() { return key; } public void setKey(int key) { this.key = key; } public Node(int value, int link, int key) { this.value = value; this.link = link; this.key = key; } @Override public int compareTo(Node o) { if (this.key>o.getKey()) { return -1; } return 1; } }
友情提示:转载请注明出处【作者idlear 博客http://blog.csdn.net/idlear/article/details/19577841】
原文:http://www.cnblogs.com/lonelyxmas/p/3561995.html
内容总结
以上是互联网集市为您收集整理的算法起步之Prim算法全部内容,希望文章能够帮你解决算法起步之Prim算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。