Kruskal 算法

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;
	}
}

 

评论

2 楼 sunlujing 2013-05-28  

leaow567 写道

虽然看不懂，但会慢慢看，还是要顶下

哥们这个需要你去看看算法导论，上面讲的很详细，我这里主要是用java 实现以下。

1 楼 leaow567 2013-05-28  

虽然看不懂，但会慢慢看，还是要顶下