Kruskal算法是一种用来查找最小生成树的算法，由Joseph Kruskal在1956年发表。用来解决同样问题的还有Prim算法和Boruvka算法等。三种算法都是贪心算法的应用。和Boruvka算法不同的地方是，Kruskal算法在图中存在相同权值的边时也有效。
基本思想
先构造一个只含 n 个顶点、而边集为空的子图，把子图中各个顶点看成各棵树上的根结点，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，即把两棵树合成一棵树，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直到森林中只有一棵树，也即子图中含有 n-1 条边为止。
步骤
1.新建图G，G中拥有原图中相同的节点，但没有边；
2.将原图中所有的边按权值从小到大排序；
3.从权值最小的边开始，如果这条边连接的两个节点于图G中不连通，则添加这条边到图G中；
4.重复3，直至图G中所有的节点都连通。
连通的判定:如果两个顶点的终点相同则连通
图解
1.从上图可看出<B,E>权值最小,同时B,E没有终点即终点就是它本身,所以选取<B,E>,同时将B的终点的终点即B的终点自己设为E
2.从上图可看出<A,D>权值第二小,同时A,D没有终点即终点就是它本身,所以选取<A,D>同时将A的终点的终点即A的终点设为D
3.从上图可看出<C,E>权值第三小,同时C,E没有终点即终点就是它本身,所以选取<C,E>同时将C的终点的终点即C的终点设为E
4.从上图可看出<A,C>权值第四小,同时A的终点是D,C的终点是E不相等,所以选取<A,C>同时将A的终点D的终点设为C的终点E
5.从上图可看出<B,D>权值第四小,同时B,D的终点都是E所以B,D连通不能选择,同理后面两条边也不能选择.
Java代码实现:
package com.yg.algorithm;/*
@author Mu_Mu
@date 2020/3/21 10:02
*/
import javax.swing.text.EditorKit;
import java.util.Arrays;
public class KruskalCase {
private int edgeNum = 0;//边的条数
private char[] vertexs;//存放顶点
//存放每个顶点之间边的长度,0为(A->A)这样顶点到自己的距离
private int[][] matrix;
//MAX表示顶点之间无边相连
private static final int MAX = 10000;
public static void main(String[] args) {
char[] vertexs = {'A', 'B', 'C', 'D', 'E'};
int[][] matrix = {{0, MAX, 7, 5, 10}, {MAX, 0, 12, 9, 4},
{7, 12, 0, MAX, 6}, {5, 9, MAX, 0, MAX}, {10, 4, 6, MAX, 0}};
KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
kruskalCase.kruskal();
}
public KruskalCase(char[] vertexs, int[][] matrix) {
this.vertexs = vertexs;
this.matrix = matrix;
}
//核心代码
public void kruskal() {
int index = 0;//后面存放结果数组的索引
//得到边的条数
int edgeNum = getEdgeNum();
//存放结果的数组
EData[] rest = new EData[edgeNum];
//存放的是每个顶点对应的终点
int[] ends = new int[edgeNum];
//得到存放所有边的数组
EData[] eData = setEdge();
//按照边的权值从小到大排序
sort(eData);
for (int i = 0; i < edgeNum; i++) {
//得到边的顶点在vertexs中对应的下标
int m = getPosition(eData[i].start);
int n = getPosition(eData[i].end);
int j = getEnd(ends, m);
int k = getEnd(ends, n);
//判断如果边的两个顶点的终点不相同,则不连通
if (j != k) {
//每次改变的是顶点终点的终点
ends[j] = k;
rest[index++] = eData[i];
}
}
//打印结果数组
System.out.println(Arrays.toString(rest));
}
//将边按照权值排序
private void sort(EData[] eData) {
for (int i = 0; i < eData.length - 1; i++) {
for (int j = 0; j < eData.length - 1 - i; j++) {
if (eData[j].weight > eData[j + 1].weight) {
EData temp = eData[j];
eData[j] = eData[j + 1];
eData[j + 1] = temp;
}
}
}
}
//构建边
public EData[] setEdge() {
int index = 0;
EData[] eData = new EData[edgeNum];
for (int i = 0; i < vertexs.length; i++) {
for (int j = i + 1; j < vertexs.length; j++) {
if (matrix[i][j] != MAX) {
eData[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]);
}
}
}
return eData;
}
//根据顶点下标获取该顶点的终点,用于判断两顶点的终点是否相同如果相同则构成回路
/*
* @param ends 存放的是每个顶点对应的终点
* @param i 顶点在vertexs中的下标
* @return : int 该顶点的终点在vertexs中的下标
* @date : 2020/3/21 12:30
*/
public int getEnd(int[] ends, int i) {
while (ends[i] != 0) {
i = ends[i];
}
return i;
}
//定位顶点的下标
private int getPosition(char c) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i] == c) {
return i;
}
}
return -1;
}
//得到边的条数
public int getEdgeNum() {
for (int i = 0; i < vertexs.length; i++) {
for (int j = i + 1; j < vertexs.length; j++) {
if (matrix[i][j] != MAX) {
edgeNum++;
}
}
}
return edgeNum;
}
//打印 matrix
private void print() {
for (int[] arr : matrix) {
System.out.println(Arrays.toString(arr));
}
}
}
class EData {
char start;//一条边边的起始端
char end;//一条边边的终端
int weight;//权值
public EData(char start, char end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
@Override
public String toString() {
return "<" +
start +
", " + end +
", " + weight +
">";
}
}