何为 Kruskal 算法?
该算法功能:求取加权连通图的最小生成树。假设加权连通图有 n 个顶点,那么其最小生成树有且仅有 n - 1 条边。
该算法核心思想:从给定加权连通图中,选择当前未被选择的,不能形成回路且权值最小的边,加入到当前正在构造的最小生成树中。
下面请看一个具体示例:
给定一个加权连通图,其包含 5 个顶点,分别为:1,2,3,4,5。包含 7 条边,按照从小到大排序依次为:
1-2,5
2-3,5
3-5,6
2-4,12
4-5,12
2-5,15
3-4,17
那么可知,使用 kruskal 算法构造该加权连通图的最小生成树,则需要选择出这 7 条边中满足定义的 4 条边。
(1) 原始图
(2) 添加第 1 条边
此时未选中任何一条边,那么直接选择 7 条边中最小的一条边,2-3,5。(PS:当权值最小的边有多个时,只要满足定义,可以随意选择一条边即可。例如,此处也可以选择 1-2,5)
(2) 添加第 2 条边
此时,从剩余的 6 条边中选择最小权值的边,可以轻易知道为 1-2,5。加入此边后,检查此时的正在构造的最小生成树,没有回路,符合定义,即可以确认加入。
(3) 添加第 3 条边
此时,从剩余的 5 条边中选择最小权值且不会生成环的边,轻易可知,3-5,6 符合要求。
(4) 添加第 4 条边(PS:此时也是最小生成树的最后一条边)
从剩余的 4 条边中选择最小权值且不会生成回环的边,发现 2-4,12、4-5,12 均符合要求,此时,任意选择其中一条边即可。这里,我选择的是 4-5,12。
(5) 最小生成树以及构造完毕,结束构造。
该算法在开始的时候,会将给定连通图所有边的权值进行从小到大排列。然后,从一个空子图开始,它会扫描这个这个有序列表,并试图把列表中的下一条边加入到当前正在构造的子图(或者说是最小生成树)中。当前,这种添加不能形成一个回路,如果产生了回路,则把这条边跳过。
- Kruskal(G) {
- //构造最小生成树的Kruskal算法
- //输入:加权连通图G = <V, E>,其中V为顶点数,E为具体边集合
- //其中E中边已经经过处理,按照权值从小到大排列
- //输出:Et,组成G的最小生成树的边的集合
- Et = 空集;int count = 0; //用于计算进行已构造的边的总数
- int k = 0; //表示从E中第一条边序号
- while (count <= V - 1) {
- k = k + 1;
- if (Et U {
- ek
- }) { //集合Et加入第k条边不产生回路
- Et = Et U {
- ek
- };
- count++;
- }
- }
- return Et;
- }
通过以上的伪码,可以知道,Kruskal 算法的时间效率取决于两点:
(1)对给定连通图所有边权值进行排序的时间效率;
(2)对新加入边,进行是否形成回路判断的时间效率。
首先,谈谈(1)的时间效率。对于排序算法,一般的时间效率分为 O(n^2)(例如,选择排序和冒泡排序)和 O(nlogn)(例如,合并排序和快速排序)。由于合并排序,相对于快速排序要稳定,所以,此处我们可以选择合并排序来处理问题(1),即时间效率为 O(nlogn),其中 n 为顶点总数。
其次,谈谈(2)的时间效率。对于问题(2)中要实现的功能,有一些高效的算法可以实现这种功能,这些算法的核心就是对两个顶点是否属于同一棵树的关键性检查,它们被称为并查算法,而该算法能够达到的最优时间效率为 O(eloge),其中 e 为具体边总数。
最后,我们来探讨一下使用并查算法实现(2)中要求的功能。
使用并查算法实现检查回环问题,这里涉及的是一种抽象数据类型,这种数据类型是由某个有限集的一系列不相交子集以及下面这些操作构成的。
例如,其中 S = {1, 2, 3, 4, 5, 6}。首先使用 id(x),初始化结果:{1},{2},{3},{4},{5},{6}。
现在执行 union(1,4)得到 {1,4},执行 union(4,5) 得到{1,4,5},此时集合结果:{1,4,5},{2},{3},{6}。
那么此时执行 find(1)或者 find(4)或者 find(5)返回子集 {1,4,5},执行 find(3) 返回子集{3}。
上面就是并查算法的应用思想,那么影响并查算法的时间效率,就是 id(x) 和 union(x) 函数的具体实现来决定。
此处对于 id(x) 和 union(x) 的实现,我采用树的性质来实现,把已经构造的边形成一棵树,当有新增的边时,且新增的边所在树的层数或者所有节点总数小于当前构造的树,那么我们就把新增的边所在树的根节点改变成当前正在构造的树的根节点的直接子节点。
例如合并子集 {1,4,5,2}(PS:该子集构成的树根节点为 1)} 和{3,6}(PS:该子集构成的树的根节点为 3),那么可以把根节点 3 直接转换为 1 的一个直接子节点即可。具体如下图所示:
讲完上面的定义及思想,下面就来具体看看对于 2.1 中示例图实现的编码应用。
首先,是初始化 id(x),这里我首先令每一个单节点树的 id(x) 值为 - 1。
- for(int i = 0;i < n;i++)
- id[i] = -1; //初始化id(x),令所有顶点的id值为-1,即表示为根节点
然后,是 find(x) 的实现:
- //获取节点a的根节点编号
- public int find(int[] id, int a) {
- int i,
- root,
- k;
- root = a;
- while (id[root] >= 0) root = id[root]; //此处,若id[root] >= 0,说明此时的a不是根节点,因为唯有根节点的值小于0
- k = a;
- while (k != root) { //将a节点所在树的所有节点,都变成root的直接子节点
- i = id[k];
- id[k] = root;
- k = i;
- }
- return root;
- }
最后,是 union(x) 的实现:
- //判断顶点a和顶点b的根节点大小,根节点值越小,代表其对应树的节点越多,将节点少的树的根节点作为节点多的树的根节点的直接子节点
- public void union(int[] id, int a, int b) {
- int ida = find(id, a); //得到顶点a的根节点
- int idb = find(id, b); //得到顶点b的根节点
- int num = id[ida] + id[idb]; //由于根节点值必定小于0,此处num值必定小于零
- if(id[ida] < id[idb]) {
- id[idb] = ida; //将顶点b的根节点作为顶点a的直接子节点
- id[ida] = num; //更新根节点的id值
- } else {
- id[ida] = idb; //将顶点a的根节点作为顶点b的直接子节点
- id[idb] = num; //更新根节点的id值
- }
- }
到这里后,看一下,构造树型 id(x) 值的具体图:
首先顶点 1 到 5 的 id(x) = {-1, -1, -1, -1, -1},即表示刚开始,所有顶点均为根节点。(PS: 后面示例 id(x)、find(x) 和 union(x, y) 中对于数组中元素均为 1 开始,不是 0 开始计算数组中元素,这样是方面描述,请大家不要见怪哟。注意,下面图中 id = 2 表示根节点为顶点 3)
(1)选择第 1 条边,2-3,5
此时 id(2) = -1,find(2) = 2 根节点为 2。id(3) = -1,find(3) = 3 根节点为 3。根据 union(x) 函数可知,由于 id(find(2)) >= id(find(3)),所以 id(find(2)) = idb = 2,id(find(3)) = num = -2
此时 id(x) = {-1, 2, -2, -1, -1}
(2)选择第 2 条边,1-2,5
此时,id(1) = -1,find(1) = 1 根节点为 1。Id(2) = 2,find(2) = 3 根节点为 3。根据 union(x) 函数可知,由于 id(find(1)) > id(find(2)),所以 id(find(1)) = idb = 2,id(find(2)) = num = -3
此时 id(x) = {2, 2, -3, -1, -1}
(3)选择第 3 条边,3-5,6
此时,id(3) = -3,find(3) = 3 根节点为 3。Id(5) = -1,find(5) = 5 根节点为 5。根据 union(x) 函数可知,由于 id(find(3)) <id(find(5)),所以 id(find(5)) = ida = 2,id(find(3)) = num = -4
此时 id(x) = {2, 2, -4, -1, 2}
(4)选择第 4 条边,4-5,12(此处也是最小生成树的最后一条边)
此时,id(4) = -1,find(4) = 4 根节点为 4。Id(5) = 2,find(5) = 3 根节点为 3。根据 union(x) 函数可知,由于 id(find(4)) > id(find(5)),所以 id(find(4)) = idb = 2,id(find(5)) = num = -5
此时 id(x) = {2, 2, -5, 2, 2}
具体代码如下:
- package com.liuzhen.systemExe;
- import java.util.ArrayList;
- import java.util.Scanner;
- public class Kruskal {
- //内部类,其对象表示连通图中一条边
- class edge {
- public int a; // 开始顶点
- public int b; //结束顶点
- public int value; //权值
- edge(int a, int b, int value) {
- this.a = a;
- this.b = b;
- this.value = value;
- }
- }
- //使用合并排序,把数组A按照其value值进行从小到大排序
- public void edgeSort(edge[] A){
- if(A.length > 1) {
- edge[] leftA = getHalfEdge(A, 0);
- edge[] rightA = getHalfEdge(A, 1);
- edgeSort(leftA);
- edgeSort(rightA);
- mergeEdgeArray(A, leftA, rightA);
- }
- }
- //judge = 0返回数组A的左半边元素,否则返回右半边元素
- public edge[] getHalfEdge(edge[] A, int judge) {
- edge[] half;
- if(judge == 0) {
- half = new edge[A.length / 2];
- for(int i = 0;i < A.length / 2;i++)
- half[i] = A[i];
- } else {
- half = new edge[A.length - A.length / 2];
- for(int i = 0;i < A.length - A.length / 2;i++)
- half[i] = A[A.length / 2 + i];
- }
- return half;
- }
- //合并leftA和rightA,并按照从小到大顺序排列
- public void mergeEdgeArray(edge[] A, edge[] leftA, edge[] rightA) {
- int i = 0;
- int j = 0;
- int len = 0;
- while(i < leftA.length && j < rightA.length) {
- if(leftA[i].value < rightA[j].value) {
- A[len++] = leftA[i++];
- } else {
- A[len++] = rightA[j++];
- }
- }
- while(i < leftA.length) A[len++] = leftA[i++];
- while(j < rightA.length) A[len++] = rightA[j++];
- }
- //获取节点a的根节点编号
- public int find(int[] id, int a) {
- int i, root, k;
- root = a;
- while(id[root] >= 0) root = id[root]; //此处,若id[root] >= 0,说明此时的a不是根节点,因为唯有根节点的值小于0
- k = a;
- while(k != root) { //将a节点所在树的所有节点,都变成root的直接子节点
- i = id[k];
- id[k] = root;
- k = i;
- }
- return root;
- }
- //判断顶点a和顶点b的根节点大小,根节点值越小,代表其对应树的节点越多,将节点少的树的节点添加到节点多的树上
- public void union(int[] id, int a, int b) {
- int ida = find(id, a); //得到顶点a的根节点
- int idb = find(id, b); //得到顶点b的根节点
- int num = id[ida] + id[idb]; //由于根节点值必定小于0,此处num值必定小于零
- if(id[ida] < id[idb]) {
- id[idb] = ida; //将顶点b作为顶点a的直接子节点
- id[ida] = num; //更新根节点的id值
- } else {
- id[ida] = idb; //将顶点a作为顶点b的直接子节点
- id[idb] = num; //更新根节点的id值
- }
- }
- //获取图A的最小生成树
- public ArrayList getMinSpanTree(int n, edge[] A) {
- ArrayList list = new ArrayList();
- int[] id = new int[n];
- for(int i = 0;i < n;i++)
- id[i] = -1; //初始化id(x),令所有顶点的id值为-1,即表示为根节点
- edgeSort(A); //使用合并排序,对于图中所有边权值进行从小到大排序
- int count = 0;
- for(int i = 0;i < A.length;i++) {
- int a = A[i].a;
- int b = A[i].b;
- int ida = find(id, a - 1);
- int idb = find(id, b - 1);
- if(ida != idb) {
- list.add(A[i]);
- count++;
- union(id, a - 1, b - 1);
- }
- //输出每一次添加完一条边后的所有顶点id值
- for(int j = 0;j < id.length;j++)
- System.out.print(id[j]+" ");
- System.out.println();
- if(count >= n - 1)
- break;
- }
- return list;
- }
- public static void main(String[] args){
- Kruskal test = new Kruskal();
- Scanner in = new Scanner(System.in);
- System.out.println("请输入顶点数a和具体边数p:");
- int n = in.nextInt();
- int p = in.nextInt();
- edge[] A = new edge[p];
- System.out.println("请依次输入具体边对于的顶点和权值:");
- for(int i = 0;i < p;i++) {
- int a = in.nextInt();
- int b = in.nextInt();
- int value = in.nextInt();
- A[i] = test.new edge(a, b, value);
- }
- ArrayList list = test.getMinSpanTree(n, A);
- System.out.println("使用Kruskal算法得到的最小生成树具体边和权值分别为:");
- for(int i = 0;i < list.size();i++) {
- System.out.println(list.get(i).a+"——>"+list.get(i).b+", "+list.get(i).value);
- }
- }
- }
运行结果:
- 请输入顶点数a和具体边数p:
- 5 7
- 请依次输入具体边对于的顶点和权值:
- 1 2 5
- 2 3 5
- 2 4 12
- 3 4 17
- 2 5 15
- 3 5 6
- 4 5 12
- -1 2 -2 -1 -1
- 2 2 -3 -1 -1
- 2 2 -4 -1 2
- 2 2 -5 2 2
- 使用Kruskal算法得到的最小生成树具体边和权值分别为:
- 2——>3, 5
- 1——>2, 5
- 3——>5, 6
- 4——>5, 12
参考资料:
1.《算法设计与分析基础》第 3 版 (美)Anany Levitin 著 潘彦 译
2.
来源: http://www.cnblogs.com/liuzhen1995/p/6519646.html