数据结构之算法|数据结构之算法 [Java版本] 克鲁斯卡尔(Kruskal)算法数据结构之算法[Java版本]克鲁

应用场景-公交站问题 【数据结构之算法|数据结构之算法 [Java版本] 克鲁斯卡尔(Kruskal)算法】看一个应用场景和问题：

文章图片
案例

文章图片
案例
某城市新增7个站点(A, B, C, D, E, F, G) ，现在需要修路把7个站点连通
各个站点的距离用边线表示(权) ，比如 A – B 距离 12公里
问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短?
克鲁斯卡尔算法介绍克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
基本思想：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路
具体做法：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止
代码实现

package cn.icanci.algorithm.kruskal; import java.util.Arrays; /** * @Author: icanci * @ProjectName: AlgorithmAndDataStructure * @PackageName: cn.icanci.algorithm.kruskal * @Date: Created in 2020/3/19 12:27 * @ClassAction: Kruskal 算法解决公交问题 */ public class Kruskal {//边的个数 private int edgeNum; //顶点数组 private char[] vertexs; //邻接矩阵 private int[][] matrix; //表示两个顶点不能联通 private static final int INF = Integer.MAX_VALUE; public static void main(String[] args) { char[] vertexs = new char[]{'A', 'B', 'C', 'D', 'E', 'F', 'G'}; //克鲁斯卡尔算法的邻接矩阵 int matrix[][] = { /*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}}; Kruskal kruskal = new Kruskal(vertexs, matrix); kruskal.print(); //System.out.println("没有排序..."); //System.out.println(Arrays.toString(kruskal.getEdges())); //System.out.println("排序只后...."); //EData[] edges = kruskal.getEdges(); //kruskal.sortEdges(edges); //System.out.println(Arrays.toString(edges)); kruskal.kru(); }public Kruskal(char[] vertexs, int[][] matrix) { this.vertexs = vertexs; this.matrix = matrix; //初始化顶点 //统计边 for (int i = 0; i < matrix.length; i++) { for (int j = i + 1; j < matrix.length; j++) { if (this.matrix[i][j] != INF) { this.edgeNum++; } } } }/** * 打印邻接矩阵 */ 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\t", matrix[i][j]); } System.out.println(); } }/** * 对边进行排序处理冒泡 * * @param edges 需要排序的边 */ private void sortEdges(EData[] edges) { for (int i = 0; i < edges.length; i++) { for (int j = 0; j < edges.length - i - 1; j++) { if (edges[j].weight > edges[j + 1].weight) { EData temp = edges[j]; edges[j] = edges[j + 1]; edges[j + 1] = temp; } } } }/** * 编写一个方法 * * @param ch 顶点的值 * @return */ private int getPosition(char ch) { for (int i = 0; i < vertexs.length; i++) { if (vertexs[i] == ch) { return i; } } return -1; }/** * 获取图中的边放到 EData数组后面需要遍历此数组 * * @return */ private EData[] getEdges() { int index = 0; EData[] edges = new EData[edgeNum]; for (int i = 0; i < vertexs.length; i++) { for (int j = i + 1; j < vertexs.length; j++) { if (matrix[i][j] != INF) { edges[index++] = new EData(vertexs[i], vertexs[j], matrix[i][j]); } } } return edges; }public void kru() { //表示最后结果数组的索引 int index = 0; //用户保存"已有的最小生成树"中的每个节点在最小生成树的重点 int[] ends = new int[edgeNum]; //创建结果数组保存最后的最小生成树 EData[] rets = new EData[edgeNum]; //获取图中所有边的集合 EData[] edges = getEdges(); System.out.println(Arrays.toString(edges)); //按照边的大小进行排序 sortEdges(edges); //遍历数组判断是否是回路 for (int i = 0; i < edgeNum; i++) { //获取第 i 条边的第一个顶点 int p1 = getPosition(edges[i].start); //获取第i 的第二顶点 int p2 = getPosition(edges[i].end); //获取 p1 在已有的最小生成树的终点 int m = getEnd(ends, p1); //获取 p2 在已有的最小生成树的终点 int n = getEnd(ends, p2); //判断是否构成回路 if (m != n) { //没有构成 ends[m] = n; rets[index++] = edges[i]; } } //打印最小生成树 System.out.println(); System.out.println("最小生成树为"); System.out.println(); for (int i = 0; i < rets.length; i++) { if (rets[i] != null) { System.out.println(rets[i]); } } }/** * 获取获取下标为 i 的顶点的重点 * * @param ends * @param i * @return */ private int getEnd(int[] ends, int i) { while (ends[i] != 0) { i = ends[i]; } return i; } }//创建一个 EData 对象实例就是表示一个边 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 + '}'; } }

测试

打印邻接矩阵 0122147483647214748364721474836471614 120102147483647214748364772147483647 21474836471003562147483647 2147483647214748364730421474836472147483647 2147483647214748364754028 16762147483647209 14214748364721474836472147483647890 [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=D, weight=3}, 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}] 最小生成树为EData{start=E, end=F, weight=2} EData{start=C, end=D, weight=3} EData{start=D, end=E, weight=4} EData{start=B, end=F, weight=7} EData{start=E, end=G, weight=8} EData{start=A, end=B, weight=12}