图论-最小生成树<Kruskal>

2019-10-28 16:00:50来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

图论-最小生成树<Kruskal>

昨天: 图论-最小生成树<Dijkstra,Floyd>

以上是昨天的Blog,有需要者请先阅读完以上再阅读今天的Blog。

可能今天的有点乱,好好理理,认真看完相信你会懂得

然而,文中提到的所有的算法在本人Blog中都会后期有讲解。推荐Blog


分割线


第三天

引子:昨天我们简单讲了讲最小生成树<Dijkstra,Floyd>算法,今天的课程就开始啦!

今天我们要讲的是:最小生成树

Top1:最小生成树的概念

最小生成树,听起来好像是树呀,为什么会是图论呢?其实,处理最小生成树问题前给出的东西,就是一个图,只不过进行操作后要求变成一个最小生成树罢了。

那什么是最小生成树呢?

我们把这个词语拆开来看。

,我们都好理解,父亲儿砸祖先啥的如果不知道的话......先百度完树再来看吧 ,那么我们根据树的特性可以得出一个结论:

最小生成树是没有环的

生成树 ,就是一个点到另一个点的路径是 唯一的 ,(可以通过树的无环性质证明),也就是 一个用N-1条边连接的树,且所有点到其他点的路径唯一

最小 代表最终生成树的边权和最小(不知道什么是边权的到博主的Blog里面去看吧)。


这里就有一个问题了:为什么会是N-1条边呢,而不是N-2或者N+1条边?

既然要把N个点用最少数量的边(这里不是上面“最小”的定义)将所有点连接起来,(忽略边权)上过小学的都知道,将两个点连起来是要一条边,三个点要两条边,哪里见过三个点用一条边连起来的?用N条边或N+1条边(即上述例子的三条边或四条边),自然就会浪费边了。


### 主要还是靠自己动手画图思考。

Top2:算法-Kruskal

概念我们讲完了,进入正题。

其实最小生成树还有个算法叫做Prim,Prim算法和Kruskal算法在于,一个在稀疏图中更快,一个在稠密图中更快。然而,Kruskal在比赛中会更好用。

那讲了这么多,Kruskal到底怎么用呢?

我们都知道了数没有环,那么只需要每次取权值最小的边,只要加入这条边之后不行成环,就可以。

有点像贪心,但是要判断有没有环。

怎么判断有环没环呢?

——并查集

所以代码就很简答啦!

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 5000 + 10;

struct Line{
    int x, y;
    int dis;
    bool operator < (const Line& next) const {
        return dis > next.dis;
    }
};
priority_queue<Line> line;
int n, m, now;
int fa[MAXN];
int ans;

inline int read(){
    int f = 1, x = 0;
    char c = getchar();

    while (c < '0' || c > '9')
    {
        if (c == '-')
            f = -1;
        c = getchar();
    }

    while (c >= '0' && c <= '9')
    {
        x = x * 10 + c - '0';
        c = getchar();
    }

    return f * x;
}

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

int main(){
    n = read(),m = read(); 
    for(int i = 1;i <= m; i++){
        int x,y,z;
        x = read(),y = read(),z = read();
        Line tot = {x,y,z};
        line.push(tot);
    }
    
    for(int i = 1;i <= n; i++){
        fa[i] = i;
    }
    
    while(!line.empty()){
        Line tot = line.top();
        line.pop();
        int nx = tot.x, ny = tot.y;
        if(find(nx) == find(ny)){
            continue;
        } 
        fa[find(nx)] = find(ny);
        ans += tot.dis;
        now++;
        if(now == n - 1){
            printf("%d",ans);
            return 0;
        }
    } 
    
    puts("orz");
    return 0;
}

原文链接:https://www.cnblogs.com/CJYBlog/p/MST.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:c++作业题sin公式

下一篇:CF785D Anton and School - 2