共计 8693 个字符，预计需要花费 22 分钟才能阅读完成。
前言需要
明天咱们学习的是克鲁斯尔算法，咱们还是从一个场景里引入看看
有 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');// 下标为 4
int 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');// 下标为 2
int 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}参考资料
- 尚硅谷：数据结构与算法（韩顺平老师）：克鲁斯尔算法