无向图的最小生成树（克鲁斯卡尔算法 Kruskal）

引子：

克鲁斯卡尔算法的作用是：构建图的最小生成树。

克鲁斯卡尔算法 Kruskal的构造过程：

1、初始化图：n个顶点，n个连通分量（如果两个顶点的连通分量相同，表示两点在同一个连通图中）。把所有的边（包含这个边两端的两个顶点）放入优先级队列中，按照权重从小到大。

2、选择最小权重的边，如果这个边的头顶点的和尾顶点的连通分量不同，则合并头和尾两个分量（整个连通图的点都需要修改，具体看代码）。舍弃该边。（连通分量用整数表示）

3、重复第二步，直到所有的顶点都连接着同一个连通分量里面。

package minTree;

import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Queue;

public class MinTree_KruskalTest {

public static void main(String[] args) {
MinTree_Kruskal m = new MinTree_Kruskal();
m.addEdge(0, 1, 6);
m.addEdge(0, 2, 1);
m.addEdge(0, 3, 5);
m.addEdge(0, 4, 10000);
m.addEdge(1, 2, 5);
m.addEdge(1, 3, 10000);
m.addEdge(1, 4, 3);
m.addEdge(1, 5, 10000);
m.addEdge(2, 3, 5);
m.addEdge(2, 4, 6);
m.addEdge(2, 5, 4);
m.addEdge(3, 4, 10000);
m.addEdge(3, 5, 2);
m.addEdge(4, 5, 6);

m.doKruskal();
}
}

class MinTree_Kruskal{

private Queue<Edge> edges = null;

public MinTree_Kruskal(){
this.edges = new PriorityQueue<>(new MyComparator());
}

public void addEdge(int head, int tail, int weigth){
this.edges.add(new Edge(head, tail, weigth));
}

public void doKruskal(){
//优先级队列，按照权重从小到大排列
Queue<Edge> tempQueue = new PriorityQueue<>(new MyComparator());
Iterator<Edge> iter = edges.iterator();
//复制队列
while(iter.hasNext()){
tempQueue.add(iter.next());
}

int len = tempQueue.size();

//表示各顶点自成一个连通分量
int[] vexSet = new int[len];
for(int i = 0; i < len; i++){
vexSet[i] = i;
}

for(int i = 0; i < len; i++){
Edge e1 = null;
//队列中权重最小的边
e1 = tempQueue.poll(); 

if(e1 != null){
if(vexSet[e1.head] != vexSet[e1.tail]){
System.out.println(e1.head+" --> "+e1.tail+"; weigth = "+e1.weigth);
int t = vexSet[e1.tail];
int h = vexSet[e1.head];
//合并头和尾的连通分量
for(int j = 0; j < len; j++){
if(vexSet[j] == t){
vexSet[j] = h;
}
}
}
}
}
}


class Edge{
//头顶点
int head;
//尾顶点
int tail;
//两点的权重
int weigth;

public Edge(int head, int tail, int weigth){
this.head = head;
this.tail = tail;
this.weigth = weigth;
}
}

/**
 * 自定义比较器
 * @author LiangYH
 *
 */
class MyComparator implements Comparator<Edge>{

@Override
public int compare(Edge o1, Edge o2) {
return o1.weigth - o2.weigth;
}

}
}