Kruskal算法是最小生产树算法
算法的步奏:
初始情况下:
把所有的节点看成是独立的一颗森林。
算法的核心就是尽可能找出权值最小的边把这些分散的森林组合成一个完整的包含所有顶点的森林。
使用的是贪心算法,贪心的证明可以参看算法导论。
使用一个以边的权值为基准的优先级队列来维护所有的边 edges
for(Edge edge:edges){
node src = deg.src;
node des = des.des;
// 判断src 和des 是否在同一个森林
如果不在同一个森林,则找到一条贪心边,
把src 对应的森林 和 des对应的森林 合并成一个森林
}
上述算法需要 判断两个节点是否属于同一个森林,也需要对森林进行合并,。
这用到了数据结构中 集合操作的知识, 即判断一个点属于哪个集合,合并两个集合
本文使用的是 set来存储集合节点, set中所有node 的id和作为集合标识。
unio的时间复杂度为 o( v),所以 对于 E 个操作,上述的复杂度为 o(EV)
更优秀的数据结构为 采用压缩路径的并查集结构。 E 个操作的时间复杂度能到 aE.
参考算法导论高级数据结构,不相交的数据集。
所以kruskal算法时间复杂度是可以为 ElogV的。 主要在于排序。 完整的代码如下:
import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; import java.util.TreeSet; /** * Kruskal spanning tree * @author slj * */ public class Kruskal { TreeSet<Edge> edges = new TreeSet<Edge>(); Set<Edge> spaningTree = new TreeSet<Edge>(); Map<String,Node> nodes= new HashMap<String,Node>(); public void addNode(String[] ids){ for(int i=0;i<ids.length;i++){ nodes.put(ids[i],new Node(ids[i])); } } public void addEdge(String src,String des,int weight){ Node srcN = nodes.get(src); Node desN = nodes.get(des); Edge edge = new Edge(srcN,desN,weight); edges.add(edge); } public void SpTree(){ for(Edge edge:edges){ Node src = edge.src; Node des = edge.des; // 判断src 和des 是否在一个森林中 String src_id = src.getMySetIndentifer(); String des_id = des.getMySetIndentifer(); if(src_id.equals(des_id)){ continue; }else{ // unino (src_forest,des_forest) Set<Node> src_forest = src.getMysets(); Set<Node> des_forest = des.getMysets(); Set<Node> union = new HashSet<Node>(); StringBuilder unionId = new StringBuilder(); for(Node node:src_forest){ unionId.append(node.id); union.add(node); } for(Node node:des_forest){ unionId.append(node.id); union.add(node); } //set the new relationship for(Node node:union){ node.setMysets(union); node.setMySetIndentifer(unionId.toString()); } spaningTree.add(edge); } } } public static void main(String[] args) { Kruskal ins = new Kruskal(); ins.addNode(new String[]{ "a","b","c", "d","e","f", "g","i","h"}); ins.addEdge("a", "b", 4); ins.addEdge("a", "h", 8); ins.addEdge("b", "h", 11); ins.addEdge("b", "c", 8); ins.addEdge("c", "d", 7); ins.addEdge("c", "f", 4); ins.addEdge("c", "i", 2); ins.addEdge("d", "f", 14); ins.addEdge("d", "e", 9); ins.addEdge("e", "f", 10); ins.addEdge("f", "g", 2); ins.addEdge("g", "i", 6); ins.addEdge("g", "h", 1); ins.addEdge("i", "h", 7); ins.SpTree(); for(Edge edge:ins.spaningTree){ System.out.println(edge); } } } class Node { String id =""; /** * 每个节点所在的集合 */ String mySetIndentifer ; Set<Node> mysets = new HashSet<Node>(); public Node(String id ){ this.id = id; mySetIndentifer = id; mysets.add(this); } public String getId() { return id; } public void setId(String id) { this.id = id; } public String getMySetIndentifer() { return mySetIndentifer; } public void setMySetIndentifer(String mySetIndentifer) { this.mySetIndentifer = mySetIndentifer; } public Set<Node> getMysets() { return mysets; } public void setMysets(Set<Node> mysets) { this.mysets = mysets; } } class Edge implements Comparable<Edge>{ Node src = null; Node des = null; int weight = 0; public Edge(Node srcN, Node desN, int weight) { this.src = srcN; this.des = desN; this.weight = weight; } @Override public int compareTo(Edge o) { if(this.weight >= o.weight){return 1;} else{return -1;} } @Override public String toString() { // TODO Auto-generated method stub return src.id+"<-->"+des.id +" weight: "+weight; } }
相关推荐
代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal算法离散型优化问题代码代码 最小生成树kruskal...
Kruskal算法,用C语言进行描述,有注释
Kruskal算法python实现,包括无向图的绘制,需要自己在桌面上先建关于无向图的TXT
Prim算法与Kruskal算法 求最小生成树 源代码 实验报告 完整
编写算法能够建立带权图,并能够用Kruskal算法求该图的最小生成树。最小生成树能够选择图上的任意一点做根结点。最小生成树输出采用顶点集合和边的集合的形式。
用matlab编写的kruskal算法,已编译
prim算法 Kruskal算法分别实现最小生成树
图论算法:最小生成树——Prim算法和Kruskal算法C 实现
最小生成树kruskal算法并查集版 C语言实现 - Slyar Home
(1)、实验题目:给定一个地区的n 个城市间的距离网,用Prim算法或Kruskal算法建立最小生成树,并得到的最小生成树的代价。 (2)、实验要求: 1、城市间的距离网采用的邻接矩阵表示,邻接矩阵的存储结构定义采用...
封装DFS、BFS算法、Prim算法、Kruskal算法、Dijstra算法、Floyd算法 上机作业: 定义采用邻接矩阵存储的图结构
最小生成树kruskal算法 最小生成树kruskal算法
本文讨论了Kruskal算法的基本思想,然后提出了一种新的改进算法-两分支Kruskal算法,该算法经过改进以选择中间值。 最后,由于减少了时间复杂度,并且处理更加方便,因此可以得出结论,改进的Kruskal算法在大多数...
代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树Kruskal算法代码代码 最小生成树...
邻接矩阵 Kruskal 算法的相关实现。代码完美可运行。
Prim与Kruskal算法的最小生成树matlab实现
实现了kruskal的算法,测试可行。
《算法导论》之图论章节中最小生成树的Kruskal算法。
Kruskal算法的一种改进--二分Kruskal算法,黄荣明,,最小生成树是数据结构中图的一个重要部分,它有许多重要的实际应用。如何方便快捷地找到最小生成树,具有极其重要的现实经济意义