前言需要
明天咱们学习的是克鲁斯尔算法，咱们还是从一个场景里引入看看
有7个村庄(A, B, C, D, E, F, G) ，当初须要修路把7个村庄连通
1.各个村庄的间隔用边线示意(权) ，比方 A – B 间隔 5公里
问：如何修路保障各个村庄都能连通，并且总的建筑公路总里程最短?
一、什么是克鲁斯尔算法？
克鲁斯卡尔(Kruskal)算法：用来求加权连通图的最小生成树的算法。
根本思维：依照权值从小到大的程序抉择n-1条边，并保障这n-1条边不形成回路
具体做法：首先结构一个只含n个顶点的森林，而后依权值从小到大从连通网中抉择边退出到森林中，并使森林中不产生回路，直至森林变成一棵树为止
那么什么是回路？接下来请看示例解析
二、通过示例来意识算法
在含有n个顶点的连通图中抉择n-1条边，形成一棵极小连通子图，并使该连通子图中n-1条边上权值之和达到最小，则称其为连通网的最小生成树
那么咱们依据G4这张图来看看有哪些不同连贯形式
举例进去的三张图代表了G4有多种的不同连贯形式，阐明是多样化的
那么什么时候是最小生成树呢？
就是泛滥连贯形式中里：最小的，则成为最优的，是最小生成树
图解思路剖析克鲁斯尔算法
咱们以上图G4举例，来应用克鲁斯尔算法进行演示
假如：咱们以后应用数组R来保留最小的生成树后果
第一步：选取G4图中最小的权值边E-F开始，因为它的权值为2
第二步：选取G4图中第二小的权值边C-D，因为它的权值为3
第三步：选取G4图中第三小的权值边D-E，因为它的权值为4
这时咱们选取G4图中第四小的权值边C-E，因为它的权值为5
这时咱们选取G4图中第五小的权值边C-F，因为它的权值为6
咱们发现这会造成回路，然而什么是回路？咱们先来剖析看看
当咱们将E-F、C-D、D-E退出到数组R中时，这几条边都有了起点
对于起点的阐明：
一、将所有顶点依照从小到大的顺序排列好之后；某个顶点的起点就是"与它连通的最大顶点"。
- C的起点是F
- D的起点是F
- E的起点是F
- F的起点是F
二、之前<C,E>尽管是权值最小的边，然而C和E的起点都是F，即它们的起点雷同。
咱们退出的边的两个顶点不能都指向同一个起点，否则将形成回路。
若将<C,E>退出最小生成树的话，会造成回路。这就是判断回路的形式。
第四步：选取G4图中第六小的权值边B-F，因为它的权值为7
第五步：选取G4图中第七小的权值边E-G，因为它的权值为8
这时咱们选取G4图中第八小的权值边F-G，因为它的权值为9
这时咱们选取G4图中第九小的权值边F-G，因为它的权值为10
第六步：选取G4图中第十小的权值边A-B，因为它的权值为12
权值12、14会造成回路，至此最小生成树结构实现
它包含的边顺次是：<E,F> <C,D> <D,E> <B,F> <E,G> <A,B>
克鲁斯算法思路小结
依据后面的图解算法，咱们可能理解到，克鲁斯卡尔算法重点须要解决的以下两个问题：
问题一：对图的所有边依照权值大小进行排序。
问题二：将边增加到最小生成树中时，怎么样判断是否造成了回路。
克鲁斯算法代码思路
1.应用邻接矩阵来示意图所之间连贯关系与权重值
//应用邻接矩阵形容权重值示意0 代表无int[][] weight = new int[][]{ {00,12,00,00,00,16,14}, {12,00,10,00,00,07,00}, {00,10,00,00,05,06,00}, {00,00,03,00,04,00,00}, {00,00,05,04,00,02,08}, {16,07,06,00,02,00,09}, {14,00,00,00,00,07,00}}; 2.须要一个寄存顶点的char数组
//char[] 数组寄存顶点个数char[] data = new char[]{'A','B','C','D','E','F','G'};3.创建对象寄存节点数据、邻接矩阵、节点个数
public class KruskaCase { private int edgeNum;//示意边个数 private char[] data;//寄存结点数据 private int[][] weight;//寄存邻接矩阵 //用来代替00 示意不能连通 private static final int INF = Integer.MAX_VALUE;}4.创立初始化办法将寄存顶点的数组与矩阵初始化
public class KruskaCase { //....省略要害代码 public KruskaCase(char[] vertexs,int[][] matrix) { //初始化顶点个数和边的个数 int len = vertexs.length; //初始化顶点寄存数组 this.data = new char[len]; for(int i = 0; i<len; i++){ this.data[i] = vertexs[i]; } //初始化邻接矩阵 this.weight = new int[len][len]; for (int i =0;i<len;i++){ for (int j =0; j<len;j++){ this.weight[i][j] = matrix[i][j]; } } //统计边的个数 for (int i =0;i<len;i++){ for (int j = i+1; j<len;j++){ if(matrix[i][j]!=INF){ edgeNum++; } } } } //打印矩阵信息 public void printShow(){ for (int i =0;i<data.length;i++){ for (int j =0; j<data.length;j++){ System.out.printf("%10d",weight[i][j]); } System.out.println(); } }}接下来咱们应用demo 实现图的创立与输入
public static void main(String[] args) { //char[] 数组寄存顶点个数 char[] data = new char[]{'A','B','C','D','E','F','G'}; int[][] weight ={ {0,12,INF,INF,INF,16,14}, {12,0,10,INF,INF,7,INF}, {INF,10,0,INF,5,6,INF}, {INF,INF,3,0,4,INF,INF}, {INF,INF,5,4,0,02,8}, {16,7,6,INF,2,0,9}, {14,INF,INF,INF,INF,7,0} }; KruskaCase kruskaCase = new KruskaCase(data,weight); kruskaCase.printShow();}刚刚问题一：对图的所有边依照权值大小进行排序
所以咱们须要创立一个边的对象保留一个点、另一个点、权值
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 "Edata{" +"start=" + start +", end=" + end +", weight=" + weight +'}'; }}举个例子比方：A-B/B-A 这两条边 做示范
咱们这里统计上图所中的边数办法，还须要解说一下
//统计边的个数for (int i =0;i<len;i++){ for (int j = i+1; j<len;j++){ if(matrix[i][j]!=INF){ edgeNum++; } }}第二个for为什么要从j = i+1 开始呢，这里其实能够看我画的矩阵图
咱们从G4 这张图里呢，能数的进去其实是十二条边，那么咱们怎么失去？
如果从每个地位都获取一遍，那么就会呈现问题，能够看看上面代码
//统计边的个数for (int i =0;i<len;i++){ for (int j = 0; j<len;j++){ if(matrix[i][j]!=INF){ edgeNum++; } }}这种办法会将A-B、B-A都统计进来，就会变成24条边。但其实他们是一条边
所以咱们只须要i+1 采纳红色斜线开始统计，这样就能够统计进去了
接下来咱们应用冒泡解决问题一，当然你回顾：往期文章
比照不同的排序形式，抉择你喜爱的形式进行排序
总而言之就是将他们的权值值进行从小到大的排序
class KruskaCase{ //...省略之前要害代码 private void sortEdges(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; } } } }}当初咱们有了边的对象，也有排序的办法，然而没有组合边的数组办法
咱们须要将（A-B，或者B-A）权值为12 这样的边对象寄存到一个数组中
class KruskaCase{ //省略之前要害代码.... private Edata[] getEdata(){ int index = 0; //依据统计的边条数寄存节点 Edata[] edata = new Edata[edgeNum]; for (int i = 0; i<data.length;i++){ for (int j = i+1; j<data.length;j++){ if(weight[i][j] !=INF){ edata[index++] = new Edata(data[i],data[j],weight[i][j]); } } } return edata; }}为什么是j = i + 1 ？
因为咱们下面讲过不要防止反复统计，A-B/B-A 只须要统计一遍即可
为什么weighti !=INF？
因为咱们下面采纳INF来代表它们之前不可连通，咱们须要连通的边
接下来咱们采纳Demo将G4图中的矩阵，转换成边数组输入看看
public static void main(String[] args) { //char[] 数组寄存顶点个数 char[] data = new char[]{'A','B','C','D','E','F','G'}; int[][] weight ={ {0,12,INF,INF,INF,16,14}, {12,0,10,INF,INF,7,INF}, {INF,10,0,INF,5,6,INF}, {INF,INF,3,0,4,INF,INF}, {INF,INF,5,4,0,02,8}, {16,7,6,INF,2,0,9}, {14,INF,INF,INF,INF,7,0} }; KruskaCase kruskaCase = new KruskaCase(data,weight); //kruskaCase.printShow();//输入G4图的矩阵 System.out.println(Arrays.toString(kruskaCase.getEdata()));}运行后果如下：[Edata{start=A, end=B, weight=12},Edata{start=A, end=F, weight=16},Edata{start=A, end=G, weight=14},Edata{start=B, end=C, weight=10},Edata{start=B, end=F, weight=7},Edata{start=C, end=E, weight=5},Edata{start=C, end=F, weight=6},Edata{start=D, end=E, weight=4},Edata{start=E, end=F, weight=2},Edata{start=E, end=G, weight=8},Edata{start=F, end=G, weight=9}]然而咱们没有解决完第一个问题，咱们来看看是什么？
问题一：对图的所有边依照权值大小进行排序
依据咱们的输入后果阐明咱们还须要将其进行排序，从小到大
public static void main(String[] args) { //char[] 数组寄存顶点个数 char[] data = new char[]{'A','B','C','D','E','F','G'}; int[][] weight ={ {0,12,INF,INF,INF,16,14}, {12,0,10,INF,INF,7,INF}, {INF,10,0,INF,5,6,INF}, {INF,INF,3,0,4,INF,INF}, {INF,INF,5,4,0,02,8}, {16,7,6,INF,2,0,9}, {14,INF,INF,INF,INF,7,0} }; KruskaCase kruskaCase = new KruskaCase(data,weight); //kruskaCase.printShow();//输入G4图的矩阵 Edata[] edata = kruskaCase.getEdata(); kruskaCase.sortEdges(edata);//进行排序 System.out.println(Arrays.toString(edata));}运行后果如下：[Edata{start=E, end=F, weight=2},Edata{start=D, end=E, weight=4},Edata{start=C, end=E, weight=5},Edata{start=C, end=F, weight=6},Edata{start=B, end=F, weight=7},Edata{start=E, end=G, weight=8},Edata{start=F, end=G, weight=9},data{start=B, end=C, weight=10},Edata{start=A, end=B, weight=12},Edata{start=A, end=G, weight=14},Edata{start=A, end=F, weight=16}]至此咱们解决了第一个问题，接下来咱们须要看看第二个问题
问题二：将边增加到最小生成树中时，怎么样判断是否造成了回路。
咱们的解决思路形式是：
1.抉择一条边的时候，求这条边的起点
2.将这条边的起点与最小生成树的起点进行重合判断，重合则回路
比如说咱们之前的将E-F、C-D、D-E退出到数组R中时，这几条边都有了起点
- C的起点是F
- D的起点是F
- E的起点是F
- F的起点是F
当咱们放入C-E的时候，咱们需要求起点是什么点
这样就能够判断退出的边的两个顶点的起点是否与最小生成树里的起点重合
//获取传入下标为i的顶点的起点()，用于前面判断两个顶点的起点是否雷同//ends 数组就是记录了各个顶点对应的起点是哪个,ends 数组是在遍历过程中，逐步形成private int getEnd(int[] ends,int i){ while (ends[i]!=0){ i = ends[i]; } return i;}咱们的思路是传入顶点的下标，那么就须要一个办法返回对应的顶点下标
public int getPosition(char ch){ for (int i =0;i<data.length;i++){ if(data[i] == ch){ return i;//找到返回该下标 } } return -1;//代表找不到;}那么获取传入下标为i的顶点的起点，这个办法是什么意思？
会不会有小伙伴说这写的是什么？我怎么看不懂？
不急，咱们进行举例剖析解说，为什么是这样
咱们以以后的这个图，来举例说明剖析解说
依据后面的剖析，咱们也晓得了图共有12条边
咱们创立一个数组来保留每个顶点在最小生成树中的起点，初始化为0
int[] ends = new int[edgeNum]; //十二条边edgeNum=12咱们创立一个数组来保留最小生成树中
EData[] rets= new EData[ edgeNum] ;//保留最小生成树那么咱们对应的边汇合对象是不是这样获取的呀？
//获取图中所有边的汇合，一共有12边Edata[] edges =getEdges();//进行从小到大的排序sortEdges(edges);咱们回过头来看看过后的图解思路步骤第一步增加E-F 这条边
带入进咱们之前的边汇合是Edata{start=E, end=F, weight=2}
这时咱们的E、F在咱们之前数组中的下标地位是什么？
//原数组传入进来//char[] data = new char[]{'A','B','C','D','E','F','G'};int p1 = getPosition('E');//下标为4int p2 = getPosition('F');//下标为5这时咱们调用办法求他们的起点，不满足while条件则代表起点是本人
int m1 = getEnd(ends,p1);//E的起点是自个int m2 = getEnd(ends,p2);//F的起点是自个而后咱们须要判断E与F是否形成回路，没有则赋值新的起点
if(m!=n）{ ends[m]=n; rets[0] = E-F;}这就示意E顶点在ends数组中，它的起点为：F顶点（下标）
同时咱们最小生成树下标[0] 等于咱们选中的E-F边
当初有没有一点点思路明确之前获取传入下标为i的顶点的起点的办法
这时一样，先获取顶点下标，在获取他们对应的起点是什么
若是不相等则赋值为新的起点
接下来咱们剖析一下这步骤，为什么咱们能晓得他们对应的顶点是
- C的起点是F
- D的起点是F
- E的起点是F
- F的起点是F
如果咱们退出的C-F，这时候咱们须要先找到C、F的下标
int p1 = getPosition('C');//下标为2int p2 = getPosition('F');//下标为5这时咱们调用办法求他们的起点，不满足while条件则代表起点是本人
int m1 = getEnd(ends,p1);//E的起点是自个int m2 = getEnd(ends,p2);//F的起点是自个当咱们传入m1下标的时候，它满足while条件则进行循环判断
会一直指向新的起点，直至不满足while条件判断，返回对应的起点下标
这就是为什么C的起点指向F，D的起点也指向F
当初你懂这两个辅助办法是什么意思了吗？
咱们将这两个辅助办法，放入KruskaCase 类中，开始咱们的算法编写
三、克鲁斯算法代码编写
public void kruskal(){ int[] ends = new int[edgeNum];//用于保留顶点的起点 Edata[] rets = new Edata[edgeNum];//用于保留最小生成树的边 Edata[] edata = getEdata();//获取所有边的汇合 sortEdges(edata);//将边汇合排序 //System.out.println("图的边汇合 =>"+Arrays.toString(edata)); int index = 0;//最小生成树边的下标 //遍历edata数组，将边增加到最小生成树中 for (int i = 0; i<edgeNum;i++){ //获取第i条边的一个顶点的下标 int p1 = getPosition(edata[i].start); //获取第i条边的另一个顶点的下标 int p2 = getPosition(edata[i].start); //获取p1的顶点的起点 int m = getEnd(ends,p1); //获取p2的顶点的起点 int n = getEnd(ends,p2); if(m!=n){ ends[m] = n; rets[index++] = edata[i]; } } System.out.println("最小生成树为："); for (int i = 0; i<index;i++){ System.out.println(rets[i]); }}接下来咱们应用demo测试看看，输入后果看看
public static void main(String[] args) { //char[] 数组寄存顶点个数 char[] data = new char[]{'A','B','C','D','E','F','G'}; int[][] weight ={ {0,12,INF,INF,INF,16,14}, {12,0,10,INF,INF,7,INF}, {INF,10,0,INF,5,6,INF}, {INF,INF,3,0,4,INF,INF}, {INF,INF,5,4,0,02,8}, {16,7,6,INF,2,0,9}, {14,INF,INF,INF,INF,7,0} }; KruskaCase kruskaCase = new KruskaCase(data,weight); kruskaCase.printShow();//输入G4图的矩阵 kruskaCase.kruskal();}运行后果如下：最小生成树为：Edata{start=E, end=F, weight=2}Edata{start=D, end=E, weight=4}Edata{start=C, end=E, weight=5}Edata{start=B, end=F, weight=7}Edata{start=E, end=G, weight=8}Edata{start=A, end=B, weight=12}参考资料
- 尚硅谷：数据结构与算法（韩顺平老师）：克鲁斯尔算法