Kruskal算法求解最小生成树问题(java代码实现)
Kruskal算法求解上面的公交问题(即求解该图的最小生成树)的思路分析
在含有n个顶点的连通图中选择n-1条边，构成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树。
例如，对于如上图所示的连通网可以有多棵权值总和不相同的生成树。
以上图为例，来对克鲁斯卡尔进行演示(假设，用数组R保存最小生成树结果)。
图解分析
文字描述:
第1步：将边<E,F>加入R中。
边<E,F>的权值最小，因此将它加入到最小生成树结果R中。
第2步：将边<C,D>加入R中。
上一步操作之后，边<C,D>的权值最小，因此将它加入到最小生成树结果R中。
第3步：将边<D,E>加入R中。
上一步操作之后，边<D,E>的权值最小，因此将它加入到最小生成树结果R中。
第4步：将边<B,F>加入R中。
上一步操作之后，边<C,E>的权值最小，但<C,E>会和已有的边构成回路；因此，跳过边<C,E>。同理，跳过边<C,F>。将边<B,F>加入到最小生成树结果R中。
第5步：将边<E,G>加入R中。
上一步操作之后，边<E,G>的权值最小，因此将它加入到最小生成树结果R中。
第6步：将边<A,B>加入R中。
上一步操作之后，边<F,G>的权值最小，但<F,G>会和已有的边构成回路；因此，跳过边<F,G>。同理，跳过边<B,C>。将边<A,B>加入到最小生成树结果R中。
此时，最小生成树构造完成！它包括的边依次是：<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>。
上面的步骤在算法实现中的两个需要解决的问题
问题一 对图的所有边按照权值大小进行排序。
问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路。
问题一很好解决，采用排序算法进行排序即可。
问题二，处理方式是：记录顶点在"最小生成树"中的终点，顶点的终点是"在最小生成树中与它连通的最大顶点"。然后每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。
Java代码实现
package com.bingym.kruskal;
import java.util.Arrays;
public class KruskalCase {
/*
* 克鲁斯卡尔(Kruskal)算法求最小生成树:
* 克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
* (1)基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路
* (2)具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止
* */
//定义若干属性
//1.定义边的个数
private int edgeNum;
//2.定义顶点的数组:用来存储从顶点'A' 到 'G'的数组元素
private char[] vertexs;
//3.使用INF表示两个顶点之间是无法连通的:即两个顶点的边的长度取Integer的最大值
private static final int INF = Integer.MAX_VALUE;
//4.定义邻接矩阵
private int[][] matrix;
//定义构造器
public KruskalCase(char[] vertexArr,int[][] matrixArr) {
int vlen = vertexArr.length;//初始化顶点数和边的个数
//初始化顶点:利用拷贝的方法:即初始化vertexs
this.vertexs = new char[vlen];
for (int i = 0; i < vertexs.length; i++) {
this.vertexs[i] = vertexArr[i];//将传入的顶点数据保存到KruskalCase的vertexs的顶点数组中
}
//初始化边:也使用复制拷贝的方式:即初始化matrix
this.matrix = new int[vlen][vlen];//行和列均为vlen长度
for (int i = 0; i < vlen; i++) {
for (int j = 0; j < vlen; j++) {
this.matrix[i][j] = matrixArr[i][j];
}
}
//统计边的个数:即初始化edgeNum
for (int i = 0; i < vlen; i++) {
for (int j = i + 1; j < vlen; j++) {
if (this.matrix[i][j] != INF) {
edgeNum++;
}
}
}
}
public static void main(String[] args) {
char[] vertexsArr = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
//克鲁斯卡尔算法的邻接矩阵
int[][] matrixArr = {
/*A*//*B*//*C*//*D*//*E*//*F*//*G*/
/*A*/ { 0, 12, INF, INF, INF, 16, 14},
/*B*/ { 12, 0, 10, INF, INF, 7, INF},
/*C*/ { INF, 10, 0, 3, 5, 6, INF},
/*D*/ { INF, INF, 3, 0, 4, INF, INF},
/*E*/ { INF, INF, 5, 4, 0, 2, 8},
/*F*/ { 16, 7, 6, INF, 2, 0, 9},
/*G*/ { 14, INF, INF, INF, 8, 9, 0}};
//创建KruskalCase实例
KruskalCase kruskalCase = new KruskalCase(vertexsArr,matrixArr);
//进行最小生成树的构建
kruskalCase.print();//图的邻接矩阵的输出打印
kruskalCase.kruskal();//通过Kruskal算法进行最小生成树的构建
}
//Kruskal算法方法
public void kruskal() {
//创建索引:表示最后数组的缩影
int index = 0;
int[] ends = new int[edgeNum];//用于保存"已有最小生成树" 中的每个顶点在最小生成树中的终点
//创建结果数组,保存最后得到的最小生成树结果
EdgeData[] minTree = new EdgeData[edgeNum];
//1.首先获取图中所有边的对象的集合
EdgeData[] edgeArr = getEdgeArr();
System.out.println("图的边的集合=" + Arrays.toString(edgeArr) + " 共有边(条数):"+ edgeArr.length);
//2.对这些边进行排序处理:按从小到大排序
sortEdge(edgeArr);
//输出排序后的边的集合:
System.out.println("排序以后图的边的集合=" + Arrays.toString(edgeArr) + " 共有边(条数):"+ edgeArr.length);
//3.遍历edgeArr数组:将边添加到最小生成树中
//因为已经进行了排序:所以我们依次添加即可
//只要注意每次添加时判断是否形成回路,若形成回路,则放弃该条边
for (int i = 0; i < edgeNum; i++) {
//首先获取到边的第一个顶点
int start = getPosition(edgeArr[i].start);
//再获取到边的第二个顶点
int end = getPosition(edgeArr[i].end);
//分别获取两个顶点的终点
int dest1 = getEnd(ends,start);
int dest2 = getEnd(ends,end);
//判断是否构成回路:也就是这两个顶点的终点是否相同
if (dest1 != dest2) { //此时没有构成回路
//第一次E和F,通过getEnd方法:dest1 = 4;dest2 = 5,则将ends[4] = 5:即将E的终点设置为F
ends[dest1] = dest2;//将此时dest1在"已有的最小生成树"中的终点设置为dest2
//注意:我们无需对dest2的终点进行设置
//并将此时有效的边加入到minTree数组中
minTree[index++] = edgeArr[i];
}
}
//最终通过for循环的遍历添加处理得到最小生成树:
System.out.println("得到的最小生成树为:");
for (int i = 0; i < index; i++) {//将打印的上界设为index:即最终最小生成树的边的个数
System.out.println(minTree[i]);
}
}
//定义方法1:打印邻接矩阵
public void print() {
System.out.println("图的邻接矩阵为:");
for (int i = 0; i < vertexs.length; i++) {
for (int j = 0; j < vertexs.length; j++) {
System.out.printf("%12d",matrix[i][j]);//将邻接矩阵数据输出打印:格式化
}
System.out.println();//换行处理
}
}
//定义方法2:对边进行排序处理:这里采用较为简单的冒泡排序法
private void sortEdge(EdgeData[] edgeArr) {//edgeArr存储每个有效边的对象的集合
for (int i = 0; i < edgeArr.length - 1; i++) {//冒泡排序排序次数:edgeArr.length - 1次
for (int j = 0; j < edgeArr.length - 1 - i; j++) {
if (edgeArr[j].weight > edgeArr[j + 1].weight) {
//进行交换,则按照从小到大排序
EdgeData temp = edgeArr[j];
edgeArr[j] = edgeArr[j + 1];
edgeArr[j + 1] = temp;
}
}
}
}
//定义方法3:根据指定的顶点的值返回其对应的下标
private int getPosition(char vertex) {
for (int i = 0; i < vertexs.length; i++) {
if (vertexs[i] == vertex) {
return i;
}
}
//找不到则返回-1
return -1;
}
//定义方法4:获取图中的边:将其放到EdgeData[] 数组中,后面需要进行遍历
//通过邻接矩阵martrix邻接矩阵得到
//得到的结果EdgeData[] 形式 [['A','B', 12], ['B','F',7], .....]
private EdgeData[] getEdgeArr() {
int index = 0;
EdgeData[] edgeArr = new EdgeData[edgeNum];//数组大小为当前给出的图的所有的边的个数
for (int i = 0; i < vertexs.length; i++) {
for (int j = i+1; j < vertexs.length; j++) {
if (matrix[i][j] != INF) {
//说明两个顶点存在边
edgeArr[index++] = new EdgeData(vertexs[i],vertexs[j],matrix[i][j]);
}
}
}
return edgeArr;//将得到的所有的边的对象的数组返回
}
//定义方法5:获取下标为i的顶点的终点:用来后面判断两个顶点的终点是否相同
private int getEnd(int[] ends,int i) {
//ends:该数组用来记录各个顶点对应的终点是哪一个:刚开始均为0
//i:即表示传入的查询终点的顶点的下标
//很巧妙的计算终点
while (ends[i] != 0) {
i = ends[i];//若当前i的终点不为0,则将其赋值给i
}
return i;//若当前i的终点为0,即i的顶点刚加入,则自己即为其顶点
}
}
//定义一个类EdgeData:表示一条边:里面保存一条边的两个顶点以及这条边的长度(即权值)
class EdgeData {
//定义边的属性
public char start;//边的一个顶点
public char end;///边的另一个顶点
public int weight;//边的权值
public EdgeData(char start, char end, int weight) {
this.start = start;
this.end = end;
this.weight = weight;
}
@Override
public String toString() {
return "EdgeData [<" + start + "," + end + "> weight=" + weight + ']';
}
}
输出结果:
图的邻接矩阵为:
0 12 2147483647 2147483647 2147483647 16 14
12 0 10 2147483647 2147483647 7 2147483647
2147483647 10 0 3 5 6 2147483647
2147483647 2147483647 3 0 4 2147483647 2147483647
2147483647 2147483647 5 4 0 2 8
16 7 6 2147483647 2 0 9
14 2147483647 2147483647 2147483647 8 9 0
图的边的集合=[EdgeData [<A,B> weight=12], EdgeData [<A,F> weight=16], EdgeData [<A,G> weight=14], EdgeData [<B,C> weight=10], EdgeData [<B,F> weight=7], EdgeData [<C,D> weight=3], EdgeData [<C,E> weight=5], EdgeData [<C,F> weight=6], EdgeData [<D,E> weight=4], EdgeData [<E,F> weight=2], EdgeData [<E,G> weight=8], EdgeData [<F,G> weight=9]] 共有边(条数):12
排序以后图的边的集合=[EdgeData [<E,F> weight=2], EdgeData [<C,D> weight=3], EdgeData [<D,E> weight=4], EdgeData [<C,E> weight=5], EdgeData [<C,F> weight=6], EdgeData [<B,F> weight=7], EdgeData [<E,G> weight=8], EdgeData [<F,G> weight=9], EdgeData [<B,C> weight=10], EdgeData [<A,B> weight=12], EdgeData [<A,G> weight=14], EdgeData [<A,F> weight=16]] 共有边(条数):12
得到的最小生成树为:
EdgeData [<E,F> weight=2]
EdgeData [<C,D> weight=3]
EdgeData [<D,E> weight=4]
EdgeData [<B,F> weight=7]
EdgeData [<E,G> weight=8]
EdgeData [<A,B> weight=12]