吾爱破解 - 52pojie.cn

 找回密码
 注册[Register]

QQ登录

只需一步,快速开始

查看: 1627|回复: 7
收起左侧

[学习记录] 最小生成树算法:普里姆算法(Prim算法)&克鲁斯卡尔算法(Kruskal算法)

  [复制链接]
RainPPR 发表于 2023-1-1 18:16
学习笔记

最小生成树问题

常用的最小生成树一般是无向图。
一般不对边的负权作要求。

一、普里姆算法(Prim算法)

普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有边的权值之和亦为最小。该算法于1930年由捷克数学家沃伊捷赫·亚尔尼克(英语:Vojtěch Jarník)发现;并在1957年由美国计算机科学家罗伯特·普里姆(英语:Robert C. Prim)独立发现;1959年,艾兹格·迪科斯彻再次发现了该算法。因此,在某些场合,普里姆算法又被称为DJP算法、亚尔尼克算法或普里姆-亚尔尼克算法。

1. 朴素版Prim算法

适用情况:稠密图
时间复杂度:O(n^2^)

思路
  1. 初始化距离(INF)
  2. 迭代 n 次
    1. 找到不在连通块中的距离最小的点
    2. 用这个点更新其他点到连通块(注意与迪杰斯特拉算法的区别)的距离
    3. 加入连通块
详解

见代码注释

代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 510;
const int INF = 0x3f3f3f3f;

int n, m;
int g[N][N];    // 稠密图用邻接矩阵存储
int dist[N];    // 每个点到连通块的距离
bool st[N];     // 这个点是否在连通块内

int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;    // 所有边的长度之和
    for (int i = 0 ; i < n ; ++i)
    {
        int t = -1;
        for (int j = 1 ; j <= n ; ++j)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        // 图不连通,没有最小生成树
        if (i && dist[t] == INF)
            return INF;
        if (i)              // 如果不是第一个点
            res += dist[t]; // 结果中加入边

        // 更新距离
        for (int j = 1 ; j <= n ; ++j)
            dist[j] = min(dist[j], g[t][j]);

        // 加入连通块
        st[t] = true;
    }

    return res;
}

int main()
{
    // 初始化距离为正无穷
    memset(g, 0x3f, sizeof g);

    // 输入
    scanf("%d %d", &n, &m);

    int a, b, c;
    while (m--)
    {
        scanf("%d %d %d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);
    }

    // Prim算法
    int t = prim();

    // 输出
    if (t == INF)
        printf("impossible\n");
    else
        printf("%d\n", t);
    return 0;
}

2. 堆优化Prim算法【不常用】

适用情况:稀疏图(不如下一个常用)
时间复杂度:O(m log n)

优化与迪杰斯特拉的堆优化类似,此处略

二、Kruskal(克鲁斯卡尔)算法

克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同,它的时间复杂度为O(e log e)(e为网中的边数),所以,适合于求边稀疏的网的最小生成树。

适用情况:稀疏图
时间复杂度:O(m log m)

思路
  1. 将所有边按权重从小到大排序(此处调用 sort 就可以)
  2. 枚举每一条边
  3. 如果这一条边两边不连通,加入这一条边
详解

见代码注释

代码
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 200010;

int n, m;
int p[N];

// 用结构体存储图
struct Edge
{
    int a, b, w;

    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
} edges[N];

// 并查集-查找祖宗
int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

int main()
{
    // 输入
    scanf("%d %d", &n, &m);
    int a, b, w;
    for (int i = 0 ; i < m ; ++i)
    {
        scanf("%d %d %d", &a, &b, &w);
        edges[i] = {a, b, w};
    }

    // 排序
    sort(edges, edges + m);

    // 初始化并查集
    for (int i = 1 ; i <= n ; ++i)
        p[i] = i;

    // 从小到大枚举所有边
    int res = 0, cnt = 0;
    for (int i = 0 ; i < m ; ++i)
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        // 查找祖宗
        a = find(a), b = find(b);

        // 如果不连通
        if (a != b)
        {
            res += w, ++cnt;
            // 合并并查集
            p[a] = b;
        }
    }

    // 输出
    if (cnt < n - 1)
        printf("impossible\n");
    else
        printf("%d\n", res);
    return 0;
}


NO MORE, THANKS!

免费评分

参与人数 3吾爱币 +1 热心值 +3 收起 理由
soenluzy + 1 + 1 有没有对象数组转树的算法
p9rsu9 + 1 欢迎分析讨论交流,吾爱破解论坛有你更精彩!
HWinZnieJ + 1 用心讨论,共获提升!

查看全部评分

发帖前要善用论坛搜索功能,那里可能会有你要找的答案或者已经有人发布过相同内容了,请勿重复发帖。

小丶白丶丶 发表于 2023-1-1 19:11
学习一下
kanxue2018 发表于 2023-1-1 20:07
yxrhy_ming 发表于 2023-1-1 20:43
陌语mua 发表于 2023-1-1 20:49
当年奥赛支配的恐惧.......
 楼主| RainPPR 发表于 2023-1-2 08:42
yxrhy_ming 发表于 2023-1-1 20:43
你也是Y总的学生?

啊对对对!
学习使我快乐1 发表于 2023-1-2 13:00
不错不错,get到了
aimomoshen 发表于 2023-1-3 09:09
感谢分享,很实用的算法
您需要登录后才可以回帖 登录 | 注册[Register]

本版积分规则

返回列表

RSS订阅|小黑屋|处罚记录|联系我们|吾爱破解 - LCG - LSG ( 京ICP备16042023号 | 京公网安备 11010502030087号 )

GMT+8, 2024-11-1 07:36

Powered by Discuz!

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表