前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >克鲁斯卡尔算法(公交站问题)

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

作者头像
贪挽懒月
发布2021-03-04 10:22:24
4340
发布2021-03-04 10:22:24
举报
文章被收录于专栏: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. 代码实现:

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

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

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

代码语言:javascript
复制
/**
 * 最小生成树
 * @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]));
        }
    }
}

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

代码语言:javascript
复制
/**
 * 边的对象
 * @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类中加如下方法:

代码语言:javascript
复制
/**
* 将图的边,即邻接矩阵,转成边对象
* @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类中增加一个排序的方法:

代码语言:javascript
复制
/**
* 对边进行排序
* @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类中新增两个方法,即实现克鲁斯卡尔算法的方法,如下:

代码语言:javascript
复制
/**
* 获取索引为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这个方法不太好理解,调试一下就很清晰了。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档