当前位置： 首页 > article >正文

Acwing 最小生成树

article 2024/9/30 14:42:50

最小生成树

最小生成树:由n个节点，和n-1条边构成的无向图被称为G的一棵生成树，在G的所有生成树中，边的权值之和最小的生成树，被称为G的最小生成树。（换句话说就是用最小的代价把n个点都连起来）

  • Prim 算法（普利姆）
    • 朴素版Prim(时间复杂度 O ( n 2 ) O(n^2) O(n2),适用于稠密图；
    • 堆优化版Prim(时间复杂度 O ( m l o g n ) O(m log n) O(mlogn),适用于稀疏图),基本不用；
  • Kruskal算法，适用于稀疏图，时间复杂度 O ( m l o g m ) O(m log m) O(mlogm).$

如果是稠密图，通常选用朴素版Prim算法，因为其思路比较简洁，代码比较短；如果是稀疏图，通常选用Kruskal算法，因为其思路比Prim简单清晰。堆优化版的Prim通常不怎么用。

1.Prim

朴素Prim
与朴素dijkstra思想几乎一样，只不过Prim算法的距离指得是点到最小生成树的集合的距离，而Dijkstra算法的距离是点到起点的距离。适合用于稠密图
Prim 算法过程：

  • 初始化 dist 数组，表示各点到最小生成树的距离。开始时设为无穷大（INF）。
  • 使用贪心策略，每次选取距离集合最近的点 t，并将其加入最小生成树。
  • 若该点距离 INF 且不是第一个节点，表示图不连通，直接返回 INF。
  • 更新其余未加入集合的点与最小生成树的最短距离。
  • 最终返回最小生成树的总权值，若图不连通则输出 impossible。

实现思路：

  • 初始化各点到集合的距离INF；
  • n次循环，每次找到集合外且距离集合最近的点t，需要先判断除第一个点外找到的距离最近的点t距离是不是INF；
    • 若是则不存在最小生成树了，结束；否则还可能存在，继续操作，用该点t来更新其它点到集合的距离（这里就是和Dijkstra最主要的区别），然后将该点t加入集合；
  • 关于集合到距离最近的点：实际上就是不在集合的点与集合内的点的各个距离的最小值，每次加入新的点都会尝试更新一遍（dist[j] = min(dist[j],g[t][j]).在Dijkstra中是dist[j] - min(dits[j],dist[t] + g[t][j]));
    在这里插入图片描述

板子：

const int N = 510, INF = 0x3f3f3f3f; // 定义最大节点数 N 和无穷大 INF
int g[N][N], dist[N]; // g[i][j] 表示从节点 i 到节点 j 的边权，dist[i] 表示当前生成树到节点 i 的最短距离
bool st[N]; // st[i] 表示节点 i 是否已经加入到最小生成树中

int n, m; // n 表示节点数量，m 表示边的数量

// 返回最小生成树的权值之和。如果图不连通，返回 INF
int prim() {
    memset(dist, 0x3f, sizeof dist); // 初始化所有节点的最短距离为 INF（即无穷大）
    
    int res = 0; // 最终的最小生成树权值之和
    
    // Prim 算法的核心，循环 n 次，每次找到一个未加入集合的最近节点
    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;
        }
        
        // 如果当前是第一个节点或者找到的节点距离集合为 INF，说明图不连通
        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]); // 使用该节点 t 更新其他节点的最短距离
        }
        st[t] = true; // 标记该节点已经加入生成树
    }
    
    return res; // 返回最小生成树的总权值
}

Acwing 858.Prim 算法求最小生成树
在这里插入图片描述
注意：本题干未设起点所以要迭代n次，并且图中可能存在负的自环，因此计算最小生成树的总距离要在更新各点到集合距离之前。且该图为无向图，含重边，则构建边需要注意。

具体实现代码（详解版）：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 510, INF = 0x3f3f3f3f; // 定义最大节点数 N 和无穷大 INF
int g[N][N], dist[N]; // g[i][j] 表示从节点 i 到节点 j 的边权，dist[i] 表示当前生成树到节点 i 的最短距离
bool st[N]; // st[i] 表示节点 i 是否已经加入到最小生成树中

int n, m; // n 表示节点数量，m 表示边的数量

// 返回最小生成树的权值之和。如果图不连通，返回 INF
int prim() {
    memset(dist, 0x3f, sizeof dist); // 初始化所有节点的最短距离为 INF（即无穷大）
    
    int res = 0; // 最终的最小生成树权值之和
    
    // Prim 算法的核心，循环 n 次，每次找到一个未加入集合的最近节点
    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;
        }
        
        // 如果当前是第一个节点或者找到的节点距离集合为 INF，说明图不连通
        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]); // 使用该节点 t 更新其他节点的最短距离
        }
        st[t] = true; // 标记该节点已经加入生成树
    }
    
    return res; // 返回最小生成树的总权值
}

int main() {
    cin >> n >> m; // 输入节点数 n 和边数 m
    memset(g, 0x3f, sizeof g); // 初始化邻接矩阵，所有边权值设为无穷大（表示节点间无边）
    
    // 输入每条边的信息，构建邻接矩阵
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c); // 无向图，所以 g[a][b] 和 g[b][a] 相同
    }
    
    int t = prim(); // 调用 Prim 算法计算最小生成树的权值
    
    // 输出结果。如果返回的是 INF，说明图不连通，输出 "impossible"
    if (t == INF) puts("impossible");
    else cout << t << endl; // 否则输出最小生成树的权值
    
    return 0;
}

堆优化Prim：思路和堆优化的Dijkstra思路基本一样，且基本不用，对于稀疏图，不如用Kruskal，这里略过

2. Kruskal

适用于稀疏图，时间复杂度 O ( m l o g m ) O(m log m) O(mlogm).Kruskal 算法是求解无向连通图的 最小生成树（MST）的经典算法。它的核心思想是通过贪心策略，按权值从小到大逐步选择边，确保不会产生环，直到选出 n-1 条边为止。整个过程涉及使用 并查集 来判断是否形成环

  • 先将所有的边按照权重，从小到大排序；
  • 从小到大枚举每条边（a,b,w)若a，b不连通，则将这条边加入集合中(将a点和b点连接起来）实质上是一个并查集的应用（两点之间加边，看两点是否存在一个连通块）
  • 无需用邻接表、邻接矩阵存储图，直接使用结构体，表示边及其权值

在这里插入图片描述
板子：

const int N = 200010, INF = 0x3f3f3f3f;
int p[N]; // 并查集的父节点数组
int n, m; // n 表示节点数，m 表示边数

// 边的结构体，表示一条边及其权值
struct Edge {
    int a, b, w; // a, b 为连接的两个节点，w 为权值
    
    // 重载小于运算符，用于按边权值升序排序
    bool operator<(const Edge &W) const {
        return w < W.w;
    }
} edges[N]; // 存储所有边

// 并查集：寻找节点 x 所在集合的根节点
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]); // 路径压缩，找到根节点并直接连接
    return p[x];
}

// Kruskal 算法求最小生成树
int kruskal() {
    sort(edges, edges + m); // 按照边的权值升序排序
    for (int i = 1; i <= n; i++) p[i] = i; // 初始化并查集，每个节点的父节点是自己
    
    int res = 0, cnt = 0; // res 存储最小生成树的权值之和，cnt 记录最小生成树的边数
    
    // 遍历所有边
    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) { // 如果两点不在同一个集合中，说明它们不连通
            p[a] = b; // 将两点所在的集合合并
            res += w; // 累加这条边的权值
            cnt++; // 增加计数
        }
    }
    
    // 如果使用的边数不足 n-1，则说明图不连通，无法构成最小生成树
    if (cnt < n - 1) return INF;
    else return res; // 返回最小生成树的权值
}

具体实现代码（详解版）：

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 200010, INF = 0x3f3f3f3f;
int p[N]; // 并查集的父节点数组
int n, m; // n 表示节点数，m 表示边数

// 边的结构体，表示一条边及其权值
struct Edge {
    int a, b, w; // a, b 为连接的两个节点，w 为权值
    
    // 重载小于运算符，用于按边权值升序排序
    bool operator<(const Edge &W) const {
        return w < W.w;
    }
} edges[N]; // 存储所有边

// 并查集：寻找节点 x 所在集合的根节点
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]); // 路径压缩，找到根节点并直接连接
    return p[x];
}

// Kruskal 算法求最小生成树
int kruskal() {
    sort(edges, edges + m); // 按照边的权值升序排序
    for (int i = 1; i <= n; i++) p[i] = i; // 初始化并查集，每个节点的父节点是自己
    
    int res = 0, cnt = 0; // res 存储最小生成树的权值之和，cnt 记录最小生成树的边数
    
    // 遍历所有边
    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) { // 如果两点不在同一个集合中，说明它们不连通
            p[a] = b; // 将两点所在的集合合并
            res += w; // 累加这条边的权值
            cnt++; // 增加计数
        }
    }
    
    // 如果使用的边数不足 n-1，则说明图不连通，无法构成最小生成树
    if (cnt < n - 1) return INF;
    else return res; // 返回最小生成树的权值
}

int main() {
    cin >> n >> m; // 输入节点数和边数
    for (int i = 0; i < m; i++) {
        int a, b, w;
        cin >> a >> b >> w; // 输入每条边的两个端点 a, b 和边的权值 w
        edges[i] = {a, b, w}; // 存储边的信息
    }
    
    int t = kruskal(); // 调用 Kruskal 算法
    if (t == INF) puts("impossible"); // 如果返回值为 INF，说明图不连通
    else cout << t << endl; // 否则输出最小生成树的权值
    
    return 0;
}

Kruskal 算法的核心思想：

  • 贪心策略：每次选择权值最小的边，且不形成环；
  • 并查集：用于快速检查两个节点是否已经连通，以及合并不同的连通集合。

3.对比总结

在这里插入图片描述


http://www.kler.cn/news/326146.html

相关文章：

  • 每日OJ题_牛客_NC40链表相加（二）_链表+高精度加法_C++_Java
  • 《黑神话:悟空》天命人速通法宝 | 北通鲲鹏20智控游戏手柄评测
  • linux打开桌面软件(wps)、获取已打开的文件名（wps）
  • Ini文件读写配置工具类 - C#小函数类推荐
  • 汽车免拆诊断案例 | 2016 款宾利GT车仪表盘上的多个故障灯点亮
  • 使用TensorFlow实现一个简单的神经网络：从入门到精通
  • 动手学深度学习（李沐）PyTorch 第 3 章 线性神经网络
  • TiDB 性能测试的几个优化点
  • Leetcode热题100-438 找出字符串中所有字母异位数
  • R语言非参数回归预测摩托车事故、收入数据：局部回归、核回归、LOESS可视化...
  • 408算法题leetcode--第19天
  • java通过webhook给飞书发送群消息
  • PTA L1-080 乘法口诀数列
  • C语言线程编程深度解析
  • Elasticsearch UNASSIGNED 怎么修复
  • OJ在线评测系统 后端 用策略模式优化判题机架构
  • MySQL基础篇 - 约束
  • Eclipse Memory Analyzer (MAT)提示No java virtual machine was found ...解决办法
  • Altium Designer脚本的执行方式
  • 【漏洞复现】VEXUS多语言货币交易所存在未授权访问漏洞
  • centos已安装python3.7环境，还行单独安装python3.10环境，如何安装，具体步骤
  • 进程、线程、协程详解：并发编程的三大武器
  • websocket初识
  • 数据集-目标检测系列-兔子检测数据集 rabbit ＞＞ DataBall
  • 中国资产“超级星期四”之后，腰部中概股或成增长“黑马”
  • Linux云计算 |【第四阶段】PROJECT2-DAY1
  • 如何使用开发者工具捕获鼠标右键点击事件
  • Tensorflow2.0
  • Spring Boot 进阶-深入了解SpringBoot条件注解
  • VLAN与三层交换机的原理与配置