乐趣区

关于java:我所知道的十大常用算法之克鲁斯尔算法

前言需要


明天咱们学习的是克鲁斯尔算法,咱们还是从一个场景里引入看看

有 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}

参考资料


  • 尚硅谷:数据结构与算法(韩顺平老师):克鲁斯尔算法
退出移动版