自学内容网 自学内容网

Acwing 最小生成树

最小生成树

最小生成树:由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.对比总结

在这里插入图片描述


原文地址:https://blog.csdn.net/qq_43060884/article/details/142553938

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!