计科院20级刘磊

用户名：1579364808

访问量：4391

签　名：

写代码困了，就喝杯Java咖啡提提神

等　　级
排　　名	2500
经　　验	2278
参赛次数	6
文章发表	16
年　　龄	19
在职情况	学生
学　　校	怀化学院
专　　业	计算机科学与技术

　　自我简介：

计算机科学与技术专业的一名小码农

TA的其他文章

回溯法解决全排列
浏览：323

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （Java代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

国王的烦恼(并查集)--kruskal算法实现最小生成树(JAVA)

　　作者: 计科院20级刘磊　　　　发表时间：2021-10-07 14:16:49 浏览：399　|　评论：0　

原题链接：蓝桥杯历届试题-国王的烦恼

###解题思路:
①首先我们来了解一下什么是最小生成树:
**假设图包含有V个顶点和E条无向(也就是双向)有权边,最少需要 V-1 条边才能连通所有顶点,这 V-1 条边和 V 个顶点构成的树,称为生成树**;像图dfs和bfs遍历都会有相应的生成树;**如果某棵树包含的 V-1 条边的权重和最小,那么对应的这颗生成树就位最小生成树**
②怎样生成最小生成树呢?:
两种比较经典的算法:Kruskal算法和Prim算法([配合视频和以下文字](https://www.bilibili.com/video/BV1Eb41177d1 "配合视频和以下文字"))。它们都用到贪心算法思想,Kruskal算法较为简单,它需要用到[并查集(如果你还不会的话,请先了解)](https://www.bilibili.com/video/BV1jv411a7LK?from=search&seid=6941188642067466287&spm_id_from=333.337.0.0 "并查集(如果你还不会的话,请先了解)"),我们将用它来实现最小生成树.
初始时,每个顶点对应一个集合.按照权重从小到大依次考察每条边.如果某条边对应的两个顶点不在同一个集合中,那么我们就将这条边选入最小生成树中,并将两个对应的集合合并。如果某条边对应的两个顶点在同一个集合中,也就是两个顶点是连通的,若再添加这条边就会形成环了,故我们选择不放入最小生成树中。依次类推,直到最小生成树中包含V-1条边为止。
上述处理思路对应代码:
```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Graph {
    private int v;//节点的个数
    private int e;//边的个数

private List<Edge> edges = new ArrayList<>();
    private List<Edge> mst = new ArrayList<>();

public void kruskal(){
       UnionFindSet unionFindSet = new UnionFindSet();
       //从小到大排序

Collections.sort(edges);
        for (int i = 0; i < e; i++) {
            if(mst.size()==v-i){
                break;
            }
            Edge edge = edges.get(i);
            //边的两个点是否在同一个集合中
            if(!unionFindSet.isSameR(edge.ui,edge.vi)){
                mst.add(edge);
                unionFindSet.union(edge.ui, edge.vi);
            }
        }
    }
    public class Edge implements Comparable<Edge> {
        public int ui;
        public int vi;
        public int weight;

@Override
        public int compareTo(Edge o) {
            return o.weight - this.weight;//按权重从小到大排序
        }
    }
}
//并查集模板
class UnionFindSet {
    private int p[];
    private int rank[];

public void unionFindSet(int n) {
        p = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = i;
            rank[i] = 1;
        }
    }
    public void union(int i,int j){
        i = findR(i);
        j = findR(j);
        if(rank[i]<rank[j]){
            p[i]=j;
        }else if(rank[i]>rank[j]){
            p[j] =i;
        }else{
            p[i]=j;
            rank[j]++;
        }
    }
    public boolean isSameR(int i,int j){
        return findR(i)==findR(j);
    }
    public int findR(int x) {
        if (p[x] == x) return x;
        p[x] = findR(p[x]);
        return -1;
    }
}
```
③回到该题  
无非就是将桥的使用天数看作权重,只不过相当于天数越多权重越小(才是关键桥,没它就会抗议)
###注意事项:
同一天断两座桥,居民也只会抗议一天

### 代码实现
**这里代码在C语言网码上去有些显示不了,我就放图片了,正好自己码一遍增加印象吧~~~**
![](https://i.loli.net/2021/10/07/qTMr9lHpxAimf8h.png)

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

计科院20级刘磊

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （Java代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

国王的烦恼(并查集)--kruskal算法实现最小生成树(JAVA)

评论区

精彩推荐

【偶数求和】（C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

A+B for Input-Output Practice （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

计科院20级刘磊

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （Java代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

2006年春浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

国王的烦恼(并查集)--kruskal算法实现最小生成树(JAVA)

评论区

精彩推荐

【偶数求和】 （C语言代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

C语言程序设计教程（第三版）课后习题10.4 （C语言代码）

A+B for Input-Output Practice （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.7 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

　　评论区

【偶数求和】（C语言代码）