Kruskal算法求解最小生成树问题(java代码实现)

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]