克鲁斯卡尔算法

克鲁斯卡尔算法介绍

克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。

==基本思想==：按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路

（福利推荐：阿里云、腾讯云、华为云服务器最新限时优惠活动，云服务器1核2G仅88元/年、2核4G仅698元/3年，点击这里立即抢购>>>）

==具体做法==：首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止

克鲁斯卡尔最佳实践-公交站问题

有北京有新增7个站点(A, B, C, D, E, F, G) ，现在需要修路把7个站点连通

    各个站点的距离用边线表示(权) ，比如 A – B 距离 12公里     问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短? 

代码示例

package com.wxit.kruskal;  import java.util.Arrays;  /**  * @Author wj  **/ public class KruskalCase {      private int edgeNum; //边的个数     private char[] vertexs; //顶点数组     private int[][] matrix; //邻接矩阵     //使用INF 表示两个顶点不能联通     private static final int INF = Integer.MAX_VALUE;     public static void main(String[] args) {         char[] vertexs = {'A','B','C','D','E','F','G'};         //克鲁斯卡尔算法的邻接矩阵         int matrix[][] = {                 {0,12,INF,INF,INF,16,14},                 {12,0,10,INF,INF,7,INF},                 {INF,10,0,3,5,6,INF},                 {INF,INF,3,0,4,INF,INF},                 {INF,INF,5,4,0,2,8},                 {16,7,6,INF,2,0,9},                 {14,INF,INF,INF,8,9,0}         };          //创建KruskalCase对象         KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);         kruskalCase.print();         System.out.println("xx" + Arrays.toString(kruskalCase.getEdges()));         kruskalCase.kruskal();     }      //构造器     public KruskalCase(char[] vertexs,int[][] matrix){         //初始化顶点数和边的个数         int vlen = vertexs.length;          //初始化顶点         this.vertexs = new char[vlen];         for (int i = 0; i < vertexs.length; i++) {             this.vertexs[i] = vertexs[i];         }          //初始化边，使用的是复制拷贝的方式         this.matrix = new int[vlen][vlen];         for (int i = 0; i < vlen; i++) {             for (int j = 0; j < vlen; j++) {                 this.matrix[i][j] = matrix[i][j];             }         }          //统计边         for (int i = 0; i < vlen; i++) {             for (int j = i + 1; j < vlen; j++) {                 if (this.matrix[i][j] != INF){                     edgeNum++;                 }             }         }     }      //打印邻接矩阵     public void print(){         System.out.println("邻接矩阵为:n");         for (int i = 0; i < vertexs.length; i++) {             for (int j = 0; j < vertexs.length; j++) {                 System.out.printf("%10d",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 - 1 - i; j++) {                 if (edges[j].weight >edges[j + 1].weight){ //交换                     EData tmp = edges[j];                     edges[j] = edges[j + 1];                     edges[j + 1] = tmp;                 }             }         }     }      /**      *      * @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[]数组中，后面我们需要遍历该数组      * 是通过matrix 邻接矩阵来获取      * EData[]  形式[['A],'B',12],      * @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;     }      /**      * 功能:获取下标为i的顶点终点（），用于后面判断两个顶点的终点是否相同      * @param ends  数组就是记录了各个顶点对应的终点是哪个。end数组是在遍历过程中逐步形成的      * @param i 表示传入的顶点对应的下标      * @return 返回的就是下标为i的这个顶点对应的终点下标      */     private int getEnd(int[] ends,int i){         while (ends[i] != 0){             i = ends[i];         }         return i;     }      //     public void kruskal(){         int index = 0; //表示最后结果数组的索引         int[] ends = new int[edgeNum];//用于保存“已有生成树"中的每个顶点在最小生成树中的终点         //创建结果数组，保存最后的最小生成树         EData[] rets = new EData[edgeNum];          //获取图中,所有的边的集合，一共有12边         EData[] edges = getEdges();         System.out.println("图的边的集合=" + Arrays.toString(edges) + "共" + edges.length);          //按照边的权值排序。从小到大         sortEdges(edges);          //遍历edges数组，将边添加到最小生成树时，判断准备加入的边是否形成回路，如果没有，就加入rets，否则不能加入         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];//有一条边加入到rets数组             }         }          //统计并打印"最小生成树"输出rets         System.out.println("最小的生成树为");         for (int i = 0; i < index; i++) {             System.out.println(rets[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;     }      //重写toString,便于输出边     @Override     public String toString() {         return "EData{" +                 "start=" + start +                 ", end=" + end +                 ", weight=" + weight +                 '}';     } } 

你还在原价购买阿里云、腾讯云、华为云、天翼云产品？那就亏大啦！现在申请成为四大品牌云厂商VIP用户，可以3折优惠价购买云服务器等云产品，并且可享四大云服务商产品终身VIP优惠价，还等什么？赶紧点击下面对应链接免费申请VIP客户吧：

1、点击这里立即申请成为腾讯云VIP客户

2、点击这里立即注册成为天翼云VIP客户

3、点击这里立即申请成为华为云VIP客户

4、点击这里立享阿里云产品终身VIP优惠价

喜欢 (0)赏

[[email protected]]

分享 (0)