专栏首页JavaEE克鲁斯卡尔算法(公交站问题)

克鲁斯卡尔算法(公交站问题)

1. 是什么?

克鲁斯卡尔算法其实也是生成最小生成树的一种算法,和普里姆算法一样,解决同一类问题的。

有7个公交站(A, B, C, D, E, F, G) ,现在需要修路把7个公交站连通,各个公交站之间的距离如下。问如何修路,能使各个公交站连通且修路的总里程数最小?

公交站问题

这个和上次说到的普里姆算法修路问题是一样的,下面来看看用克鲁斯卡尔算法怎么解决。

2. 算法步骤:

  • 首先对边的权值进行排序,选择权值最小的一条边,即EF;
  • 选择权值第二小的边,即CD;
  • 选择权值第三小的边,即DE;
  • 选择权值第四小的边,即CE,但是,如果选择CE,那就形成回路了。什么叫回路呢?CDE这个三角形三条边都修了路,那就是回路。所以不能选择CE,那就尝试选择第五小的边,即CF,但是CF也不能选,如果选了,四边形CFED就形成回路了。所以继续选择第六小的边,BF,这个是可以选择的;
  • 接下来依次选择EG、AB。7个顶点总共要选择6条边,这6条边分别是:EF、CD、DE、BF、EG、AB。

克鲁斯卡尔算法的难点在于,怎么判断选择了这条边是否会形成回路。

  • 判断是否形成回路的方法:记录顶点在最小生成树中的终点,顶点的终点是“在最小生成树中与它连通的最大顶点”。然后每次需要将一条边添加到最小生成树时,判断该边的两个顶点终点是否相同,相同就会构成回路。

看了这段话,可能还是一脸蒙逼,还是以上面的图为例,看步骤:

  • 首先ABCDEFG这7个顶点,在顶点集合中应该是按照顺序存放的;
  • 按照上面的分析,第一次选择的是EF,毫无疑问这一条边的终点是F;
  • 第二次选择的CD的终点D;
  • 第三次选择的DE,终点是F,因为此时D和E相连,D又和F相连,所以D的终点是F。而且,因为C和D是相连的,D和E相连,E和F也是相连的,所以C的终点此时变成了F。也就是说,当选择了EF、CD、DE这三条边后,C、D、E的终点都是F。当然F的终点也是F,因为F还没和后面的哪个顶点连接。
  • 本来接下来应该选择CE的,但是由于C和E的终点都是F,所以就会形成回路。

3. 代码实现:

首先还是定义一个类,用来表示图,如下:

/**
 * 图
 * @author zhu
 *
 */
class Graph{
    List<String> vertexs; // 存放顶点
    int[][] edges; // 邻接矩阵,存放边
    
    public Graph(List<String> vertexs, int[][] edges) {
        this.vertexs = vertexs;
        this.edges = edges;
    }
    
}

然后,再定义一个最小生成树类,写上一些基础方法,比如生成图,打印图的邻接矩阵等,如下:

/**
 * 最小生成树
 * @author zhu
 *
 */
class MinTree{
    
    
    /**
     * 创建图
     * @param vertex 顶点集合
     * @param edges 邻接矩阵
     */
    public Graph createGraph(List<String> vertex, int[][] edges) {
        return new Graph(vertex, edges);
    }
    
    /**
     * 打印图的二维数组
     * @param graph
     */
    public void printGraph(Graph graph) {
        int[][] edges = graph.edges;
        for (int i=0; i<edges.length; i++) {
            System.out.println(Arrays.toString(edges[i]));
        }
    }
}

因为我们上面的分析说了,要对边进行排序。现在边是保存在邻接矩阵中的,不太好处理,所以再定义一个类,用来表示边:

/**
 * 边的对象
 * @author zhu
 *
 */
class EdgeObject{
    String start; // 边的端点
    String end; // 边的另一个端点
    int weight; // 边的权值
    
    public EdgeObject(String start, String end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "EdgeObject [start=" + start + ", end=" + end + ", weight=" + weight + "]";
    }
}

有了这个类来表示边,接下来就可以写一个方法,将图的邻接矩阵转成边对象,即在MinTree类中加如下方法:

/**
* 将图的边,即邻接矩阵,转成边对象
* @param graph
* @return
*/
public List<EdgeObject> transfer2Object(Graph graph){
    List<EdgeObject> edgeList = new ArrayList<>();
    for (int i=0; i<graph.edges.length; i++) {
        for (int j=i+1; j<graph.edges[0].length; j++) {
            if (graph.edges[i][j] != 100) {
                EdgeObject edgeObject = new EdgeObject(graph.vertexs.get(i), graph.vertexs.get(j), graph.edges[i][j]);
                edgeList.add(edgeObject);
            }
        }
    }
    return edgeList;
}

获取到了边对象的集合,就可以对其进行排序了,所以中MinTree类中增加一个排序的方法:

/**
* 对边进行排序
* @param edgeObject
*/
public void sortEdges(List<EdgeObject> edgeObjects) {
    Collections.sort(edgeObjects, new Comparator<EdgeObject>() {
        @Override
        public int compare(EdgeObject o1, EdgeObject o2) {
            return o1.weight - o2.weight;
        }
    });
}

至此,对边进行排序的准备工作就做完了。接下来还需要中MinTree类中新增两个方法,即实现克鲁斯卡尔算法的方法,如下:

/**
* 获取索引为i的顶点的终点
* @param endArray 存放终点的数组
* @param i 传入顶点的索引
* @return 顶点i的终点对应的索引
*/
public int getEnd(int[] endArray, int i) {
    while (endArray[i] != 0) {
        i = endArray[i];
    }
    return i;
}
    
/**
* 克鲁斯卡尔算法创建最小生成树
* @param graph 图
* @param currentVertex 开始处理的顶点
*/
public List<EdgeObject> kruskal(Graph graph) {
    // 最终选择的边的集合
    List<EdgeObject> resultList = new ArrayList<>();
    // 用于保存终点的数组
    int[] ends = new int[graph.vertexs.size()];
    // 将图的邻接矩阵转成边对象集合
    List<EdgeObject> list = transfer2Object(graph);
    // 对边进行排序
    sortEdges(list);
    // 遍历边的集合
    for (EdgeObject e : list) {
        int p1 = graph.vertexs.indexOf(e.start); // 边的第一个顶点的索引
        int p2 = graph.vertexs.indexOf(e.end); // 边的第二个顶点的索引
        int m = getEnd(ends, p1); // 获取p1的终点
        int n = getEnd(ends, p2); // 获取p2的终点
        if (m != n) { // 如果这两个顶点的终点相同,就会构成回路,反之就可以添加这条边
            ends[m] = n; // 将索引为m的顶点的终点设置为索引为n的顶点
            resultList.add(e); // 将这条边加入到保存结果的集合中
        }
    }
    return resultList;
}

解释一下这两个方法,首先看第二个方法:

  • 首先定义保存最终结果的集合;
  • 然后定一个了一个数组,用来保存终点。数组的大小就是图的顶点的个数。下标表示的是顶点,比如下标0,那代表的就是A这个顶点,下标1代表的就是B这个顶点;下标对应的值表示的是该下标对应的顶点的终点的索引。比如ends[0] = 1,表示的是A的终点是B。
  • 再然后调用上面的方法,将邻接矩阵转成边对象的集合,并且进行排序;
  • 接着遍历这个边的集合,每拿到一条边,就判断这条边的两个端点的终点是否相同。比如第一次拿到的边是EF,那么p1 = 4, p2 = 5。接下来用getEnd方法去获取终点。获取p1终点的时候,保存终点的ends数组中还全部都是0,所以ends[p1] = 0,不进入while循环,直接return了p1的值,即m = 4;同理n = 5。m不等于n,这时,就让ends[4] = 5,4对应的是E,5对应的是F,这句话的作用就是将E的终点设置为了F。
  • 拿到的第二条边应该是CD,p1 = 2, p2 = 3m = 2, n = 3ends[2] = 3,将C的终点设置成了D。
  • 拿到的第三条边是DE,p1 = 3, p2 = 4,因为ends[3]、ends[4] = 0,不会进入while循环,所以m = 3, n = 4ends[3] = 4,将D的终点设置成了E。
  • 拿到的第四条边是CE,p1 = 2, p2 = 4,此时,ends[2] = 3 != 0,所以进入while循环,ends[3] = 4 != 0, ends[4] = 5 != 0, ends[5] = 0,所以m = 5,也就是说,C的终点是索引5对应的,即F;接着看n等于多少。ends[4] = 5 != 0,进入while循环,ends[5] = 0,所以n = 5,此时m和n相等,说明终点是同一个,都是F,所以不添加这条边。

……

这里就是getEnd这个方法不太好理解,调试一下就很清晰了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 最小生成树----克鲁斯卡尔算法

    大忽悠爱学习
  • 普利姆(prim)算法和克鲁斯卡尔(kruskal)算法

    连通网的最小生成树算法: 1.普里姆算法——”加点法”。 假设N=(V,{E})是连通网,TE为最小生成树的边集合。 (1)初始U={u0}(...

    Steve Wang
  • 最小生成树算法(下)——Kruskal(克鲁斯卡尔)算法

    在我的上一篇文章最小生成树算法(上)——Prim(普里姆)算法 主要讲解对于稠密图较为合适的Prim算法。那么在接下里这片文章中我主要讲解对于稀疏图较为合适...

    AI那点小事
  • 肯硕(Kensho)揭开华尔街百年赚钱秘诀

    大数据文摘
  • 算法:图解最小生成树之克鲁斯卡尔(Kruskal)算法

    我们在前面讲过的《克里姆算法》是以某个顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树的。同样的思路,我们也可以直接就以边为目标去构建,因为权值为边上,直...

    s1mba
  • 传奇数学家斯梅尔

    源 / 《数学文化》 当代富有色彩的著名数学家,首推长期工作在美国加州伯克利大学的史蒂芬 • 斯梅尔(Stephen Smale)教授。国内一般学术刊物介绍科学...

    顶级程序员
  • 吴晓波:再也不会有德鲁克了

    用户1756920
  • 全球大数据领域20位最顶尖人才

    Pinterest是一家以图片为主的社交网络,数据科学家安德莉亚·伯班克主要负责该公司的A/B测试,评估公司网站、APP的外观或功能变化会对它的6000万全球用...

    华章科技
  • 《财富》精选:2014年大数据行业最顶尖的20位明星人才

    大数据不只是要处理很多的数字,还得要通过这些数字建立模型、深入挖掘,并且寻找那些有可能改变企业运营方式的信息。以下谨为大家介绍20位大数据领域的顶尖人才。 Pi...

    小莹莹

扫码关注云+社区

领取腾讯云代金券