minispantree.java

java 实现的一些算法： 赛选法求素数

package daniel.graph_theory;
import static java.lang.System.out;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
/**
 * 
 * @author DanielCao
 *
 */
public class MiniSpanTree {

	public static final int MAX_SIZE = 8;
	
	public static int map[][] = new int[MAX_SIZE][MAX_SIZE];
	
	static List<Edge> edges = new ArrayList<Edge>(MAX_SIZE*MAX_SIZE);
	
	public static void init(){
		map[0][1] = map[1][0] = 3;
		map[1][2] = map[2][1] = 2;
		map[1][3] = map[3][1] = 3;
		map[2][6] = map[6][2] = 7;
		map[3][4] = map[4][3] = 4;
		map[3][5] = map[5][3] = 2;
		map[3][6] = map[6][3] = 2;
		map[3][7] = map[7][3] = 10;
		map[5][7] = map[7][5] = 5;
		
		edges.add(new Edge(0,1,3));
		edges.add(new Edge(1,2,2));
		edges.add(new Edge(1,3,3));
		edges.add(new Edge(2,6,7));
		edges.add(new Edge(3,4,4));
		edges.add(new Edge(3,5,2));
		edges.add(new Edge(3,6,2));
		edges.add(new Edge(3,7,10));
		edges.add(new Edge(5,7,5));
		Collections.sort(edges, new Comparator<Edge>(){

			@Override
			public int compare(Edge o1, Edge o2) {
				if(o1.length > o2.length)return 1;
				else if(o1.length < o2.length)return -1;
				return 0;
			}});
		for(Edge e:edges){
			System.out.println(e.length);
		}
	}
	
	public static void prim(){
		int sum = 0;
		// 关键点： v[] 表示剩余点到已成树的 最短距离（而不是值到哪一个点）
		int v[] = new int [MAX_SIZE];
		for(int i = 1;i<MAX_SIZE;i++){
			v[i] = map[0][i];
		}
		//表示已经是树中的点
		v[0] = -1;
		for(int i = 1;i<MAX_SIZE ;i++){
			int min = 9999999;
			int point = 0;
			for(int j=0;j<MAX_SIZE;j++){
				if(v[j] > 0 && v[j] < min){
					min = v[j];
					point = j;
					//TODO 保存路径
				}
			}
			v[point] = -1;
			sum += min;
			for(int j=0;j<MAX_SIZE;j++){
				if(v[j] == 0  || v[j] != 0 && map[j][point] !=0 && map[j][point] < v[j]){
					//和dijkstra不同之处在这里（当然v[]的含义也不同）
					v[j] = map[j][point];
				}
			}
		}
		out.println(sum);
	}
	public static void kruskal(){
		//MAX_SIZE个集合
		int v[] = new int[MAX_SIZE];
		for(int i = 0 ;i < MAX_SIZE ;i ++){
			v[i] = i;
		}
		int sum = 0;
		for(Edge e: edges){
			if(v[e.s] != v[e.t]){
				sum += e.length;
				combine(v,v[e.s],v[e.t]);
			}
		}
		System.out.println(sum);
	}
	//合并集合
	private static void combine(int[] v,int vs,int vt){
		for(int i = 0;i<v.length;i++){
			//将t集合的元素都放到s集合
			if(v[i] == vt){
				v[i] = vs;
			}
		}
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		init();
		prim();
		kruskal();
	}

}

class Edge{
	public Edge(int s,int t,int length){
		this.s = s;
		this.t = t;
		this.length = length;
	}
	public int s;
	public int t;
	public int length;	
}
/*class Point{
	public int x;
	public int y;
	public String name;
	
	public int hashCode(){
		if(name == null){
			return x*100000+y;
		}
		else {
			return name.hashCode();
		}
	}
	
	public boolean equals(Object o){
		if(!(o instanceof Point)){
			return false;
		}
		Point p = (Point)o;
		if(x == p.x && y == p.y && p.name == name){
			return true;
		}
		return false;
	}
}*/