Catshao

用户名：Catshao

访问量：28812

签　名：

stO KHIN Orz

等　　级
排　　名	161
经　　验	7130
参赛次数	6
文章发表	46
年　　龄	12
在职情况	学生
学　　校	双语
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2020年第十一届省赛真题-整数小拼接
浏览：1472

蓝桥杯2020年第十一届省赛真题-BST插入节点问题
浏览：546

蓝桥杯2020年第十一届省赛真题-八次求和
浏览：556

你可能喜欢

C语言训练-阶乘和数* （C++代码）（直接输出样例hhhh）

【小白向】kruskal详解

　　作者: Catshao　　　　发表时间：2021-02-12 22:15:27 浏览：537　|　评论：0　

原题链接：数据结构-最小生成树

[TOC]

# Part -1 前置算法

1. 了解图的存储，本文使用邻接表来存储图。

# Part 1 最小生成树

什么是最小生成树？《算法导论》给了我们一个很好的解释

![算法导论部分内容](http://cat-shao.gitee.io/mypic/%E7%AE%97%E6%B3%95%E5%AF%BC%E8%AE%BA%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91.png)

最小生成树在许多领域都有它的作用。譬如网络的连接，每一个节点（计算机）断网后，最小生成树就会重新计算，所以算法的速度还是不容忽视的。

>最小生成树其实是最小权重生成树的简称。
——百度百科

# Part 2 kruskal

kruskal（克鲁斯卡尔）是一种求最小生成树的算法。

## 过程

#### 排序
首先，我们剥离开每一条边（边中有三个数据：`左端点、右端点、权值`），然后让他们从小到大排序。

![动画](http://cat-shao.gitee.io/mypic/克鲁斯卡尔图片1.jpg)

![动画](http://cat-shao.gitee.io/mypic/克鲁斯卡尔图片2.jpg)

最小生成树，自然要保证**边权和最小**的正确性。排序好后我们能保证越早拿到的边在无环的情况下一定是**最优的（`最小->最优`）**。但是，在加入边之前有一个[条件](#判环)。

在本题接我们使用了[**小根堆**](https://blog.dotcpp.com/a/76077)来排序。

#### 遍历

##### 判环

加入的条件为**加入后整棵树无环**。有两种解释：
1. 最小生成树本质上是一棵树，不能出现环。
2. 每添加一条边，其实是将`边左右两侧的集合合拼为一个集合`。如果边的左右两侧属于`一个集合`，那么合拼后会出现环。

我们将每一条边的权值累加`sum`，然后将边舍弃掉。如果需要整棵树的链接方式，使用一个新的图按照节点编号建立一条边即可。

##### 成功&失败条件

联通n个节点只需要**n - 1**条边。将加入过的边进行计数`count`，如果`count`达到了`n - 1`，

如果边始终没到`n - 1`个，无法构成最小生成树（边太少了不连通），返回`-1`表示失败。

----------

下面这个动画演示了克鲁斯卡尔的全过程：

![动画](http://cat-shao.gitee.io/mypic/克鲁斯卡尔360p.gif)

>动画为[WAY_zhong](https://space.bilibili.com/401818121)所做，转载自[最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示](https://www.bilibili.com/video/BV1Eb41177d1)

整个算法时间复杂度为$$O(e \log v)$$，与prim相同。

## 判环

在过程中，有一个部分为判环。我们应该使用什么来判环呢？
从上面的动图我们可以看出：`在没有构建完最小生成树之前，是有多个集合的`。
由于有多个集合，使用[**并查集**](https://blog.dotcpp.com/a/76623)可以有效判环。（[**并查集详解（C++代码）（小白向）**](https://blog.dotcpp.com/a/76623)）

每添加一条边，其实是将`边左右两侧的集合合拼为一个集合`。如果边的左右两侧属于`一个集合`，那么合拼后会出现环。 
我们只需要判断是否在同一个集合就可以判断连接后有环了。

## 与prim比较

优：克鲁斯卡尔代码更短。

>劣：在非稀疏图**疑似**克鲁斯卡尔会比prim慢一点。

## 代码

```cpp
#include <cstdio>
#include <deque>
#include <queue>
#include <climits>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

const long long INF = 1000000000;
const int MAX_N = 100;

class edge {
public:
    int to;
    long long cost;
    edge() {
    }

edge(int _to, long long _cost) {
        to = _to;
        cost = _cost;
    }

bool operator < (const edge &e) const {
        return cost > e.cost;
    }
};

class doubleEdge {
public:
    int from, to;
    long long cost;
    doubleEdge() {
    }

doubleEdge(int _from, int _to, long long _cost) {
        from = _from;
        to = _to;
        cost = _cost;
    }

doubleEdge(int _from, edge _edge) {
        from = _from;
        to = _edge.to;
        cost = _edge.cost;
    }

bool operator < (const doubleEdge &e) const {
        return cost > e.cost;
    }
};

typedef deque<edge> graphType;

class disjointSet {
public:
    int parent[MAX_N];

disjointSet() {
        for (int i = 0; i < MAX_N; ++i) {
            parent[i] = i;
        }
    }

int find(int x) {
        if (parent[x] == x) {
            return x;
        } else {
            return parent[x] = find(parent[x]);
        }
    }

bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return false;
        }
        parent[rootY] = rootX;
        return true;
    }

bool same(int x, int y) {
        return find(x) == find(y);
    }
};

long long kruskal(graphType graph[], int n)
{
    disjointSet parent = disjointSet();
    priority_queue<doubleEdge> q;
    for (int i = 1; i <= n; ++i) {
        for (graphType::iterator it = graph[i].begin(); it != graph[i].end(); it++) {
            q.push(doubleEdge(i, *it));
        }
    }

long long sum = 0, count = 0;
    while (!q.empty()) {
        doubleEdge e = q.top();
        q.pop();
        if (parent.unite(e.from, e.to)) {
            sum += e.cost;
            count++;
            if (count == n - 1) {
                return sum;
            }
        }
    }
    return -1;
}

int kruskalMain()
{
    graphType graph[MAX_N];

int n, m;
    scanf("%d", &n);

for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf("%d", &m);
            if (m) {
                graph[i].push_back(edge(j, m));
            }
        }
    }

printf("%lld\n", kruskal(graph, n));
}

int main()
{
    kruskalMain();
}
```

------------

参考：

1. [最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示](https://www.bilibili.com/video/BV1Eb41177d1)

0.0分

3 人评分

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

Catshao

TA的其他文章

你可能喜欢

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

C二级辅导-阶乘数列（C语言代码）

C语言训练-阶乘和数* （C++代码）（直接输出样例hhhh）

C二级辅导-等差数列（C语言代码）

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

【小白向】kruskal详解

评论区

精彩推荐

点我有惊喜！你懂得！

C二级辅导-计负均正（C语言代码）

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

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

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

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

Hello, world! （C语言代码）

Tom数（C语言代码）

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

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

Catshao

TA的其他文章

你可能喜欢

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

C二级辅导-阶乘数列 （C语言代码）

C语言训练-阶乘和数* （C++代码）（直接输出样例hhhh）

C二级辅导-等差数列 （C语言代码）

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

【小白向】kruskal详解

评论区

精彩推荐

点我有惊喜！你懂得！

C二级辅导-计负均正 （C语言代码）

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

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

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

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

Hello, world! （C语言代码）

Tom数 （C语言代码）

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

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

C二级辅导-阶乘数列（C语言代码）

C二级辅导-等差数列（C语言代码）

　　评论区

C二级辅导-计负均正（C语言代码）

Tom数（C语言代码）