克鲁斯卡尔算法(kruskal)

我自己感觉，克鲁斯卡尔算法比普利姆算法更好理解，它就两个要点，排序和判断是否成环。

排序：我们把两两相邻的边根据边的权值，从小到大依次排序，这个十大排序算法可以自己选一个去实现下，刚好还可以回忆下以前的算法，下面我们使用冒泡来实现边的排序。

是否成环：这个也是这个算法里比较难的一个点了，这里使用了并查集，每次添加一条边时候，我们需要去寻找这两个点是否有相同的父节点，如果有说明成环了，我们就可以选择下一条边了，直到有n-1条边。

如果不了解并查集的，可以看看下面这一篇文章，讲的很通俗易懂。 (https://zhuanlan.zhihu.com/p/93647900)

下面依然是给出关键步骤代码，基本的图数据结构可以自己动手实现哦。

//边对象
class Edata {
	private int start;
	private int end;
	private int weight;
	public Edata(int start, int end, int weight) {
		this.start = start;
		this.end = end;
		this.weight = weight;
	}
}

//还是写下图对象，也没有几行
class Graph {
	//结点数量
	private int verxs;
	//结点数组
	private char[] data;
	//矩阵图
	private int[][] weigth; 
}

//记录每个结点的父结点，初始化的时候，每个结点的父节点是它自己
private int[] rank;
//最后我们获取到的边
private Edata[] result;

public void kruskal(Graph graph) {
	//辅助索引，用来存放最后我们获取到的边；
	int index = 0;
	//获取图中所有边
	Edata[] eDatas = getEDates(graph);
	//把边按权值进行排序
	sort(edatas)
	//依次取出边
	for(int i = 0; i < eDatas.length; i++) {
		//获取结点的索引
		int m = eDatas[i].getStart();
		int n = eDatas[i].getEnd();
		//获取连个结点的父节点
		int a = getRoot(m);
		int b = getRoot(n);
		//不同就把这条边加入进去
		if（a != b) {
			//这里其实就是合并两个集合
			rank[a] = b;
			result[index++] = eDatas[i];
		}
	}
}

//获取当前结点的根节点，可以想象成一棵树，不断往上找
public int getRoot(int n) {
	while(rank[n] != n) {
		n = rank[n];
	}
	return n;
}

//冒泡排序
public void sort(Edata[] eDatas) {
	Edata[] edatas = getEDates(graph);
}

//获取边的集合
public Edata[] getEDates(Graph graph) {
	int index = 0;
	//n个结点，n-1条边
	Edata eDatas = new Edata[graph.getVerxs - 1];
	//广度遍历
	for(int i = 0; i < graph.getVerxs(); i++) {
		//把自己和前面已经生成的边排除
		for(int j = i + 1; j < graph.getVerxs(); j++) {
			edatas[index++] = new Edata(graph.getData()[i], graph.getData()[j], graph.getWeight()[i][j]);
		}
	}
	return eDatas;
}

到此克鲁斯卡尔算法算是完了，代码虽然比普利姆的多些，但是结构还是很清楚的，记住两个要点排序，是否成环就OK了。