python/TangDou/Topic/【最小生成树】专题.md

最小生成树专题

Prim算法和Kruskal算法都是用于 求解最小生成树的算法，但它们的使用场景和应用领域存在一些差异。

一、算法概述

Prim算法

① Prim算法是一种贪心算法，基于顶点的方式构建最小生成树。 ② Prim算法 适用于稠密图，即边的数量接近于完全图(n*(n-1)/2)的图。 ③ Prim算法从一个起始顶点开始逐步扩展，直到生成一个包含所有顶点的最小生成树。 ④ Prim算法的时间复杂度为O(ElogV)，对于稠密图有较好的性能。

AcWing 858. Prim 算法求最小生成树

Code模板

#include <bits/stdc++.h>

using namespace std;
const int N = 510;
const int INF = 0x3f3f3f3f;

int n, m;
int g[N][N]; // 稠密图，邻接矩阵
int dis[N];  // 这个点到集合的距离
bool st[N];  // 是不是已经使用过
int res;     // 最小生成树里面边的长度之和
int pre[N];  // 前驱结点

// 普利姆算法求最小生成树
int prim() {
    memset(dis, 0x3f, sizeof dis);
    memset(pre, -1, sizeof pre); // 记录前驱路径
    dis[1] = 0;

    for (int i = 0; i < n; i++) { // 迭代n次
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!st[j] && (t == -1 || dis[t] > dis[j])) t = j;
        if (i && dis[t] == INF) return INF; // 非连通图，没有最小生成树
        if (i) res += dis[t];
        for (int j = 1; j <= n; j++)
            if (!st[j] && g[t][j] < dis[j]) {
                dis[j] = g[t][j];
                pre[j] = t; // 记录是由谁转移而来
            }
        st[t] = true;
    }
    return res;
}

int main() {
    cin >> 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);
    }
    int t = prim();
    if (t == INF)
        puts("impossible");
    else
        cout << t << endl;

    // 输出前驱结点
    for (int i = 1; i <= n; i++) printf("%d ", pre[i]);
    return 0;
}

Kruskal算法

① Kruskal算法是一种基于边的方式构建最小生成树的算法。 ② Kruskal算法 适用于稀疏图，即边的数量远小于完全图(n*(n-1)/2)的图。 ③ Kruskal算法按权值递增的顺序选择边，并通过判断是否构成环来决定是否将边加入最小生成树。 ④ Kruskal算法的时间复杂度为O(ElogE)，对于稀疏图有较好的性能。

AcWing 859. Kruskal 算法求最小生成树

Code模板

#include <bits/stdc++.h>

using namespace std;
const int N = 100010, M = N << 1;
const int INF = 0x3f3f3f3f;

int n, m; // n条顶点,m条边
int res;  // 最小生成树的权值和
int cnt;  // 最小生成树的结点数

// Kruskal用到的结构体
struct Node {
    int a, b, c;
    bool const operator<(const Node &t) const {
        return c < t.c; // 边权小的在前
    }
} edge[M]; // 数组长度为是边数

// 并查集
int p[N];
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// Kruskal算法
void kruskal() {
    // 1、按边权由小到大排序
    sort(edge, edge + m);
    // 2、并查集初始化
    for (int i = 1; i <= n; i++) p[i] = i;
    // 3、迭代m次
    for (int i = 0; i < m; i++) {
        int a = edge[i].a, b = edge[i].b, c = edge[i].c;
        a = find(a), b = find(b);
        if (a != b)
            p[a] = b, res += c, cnt++; // cnt是指已经连接上边的数量
    }
    // 4、特判是不是不连通
    if (cnt < n - 1) res = INF;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        edge[i] = {a, b, c};
    }
    kruskal();
    if (res == INF)
        puts("impossible");
    else
        printf("%d\n", res);
    return 0;
}

二、最小生成树练习题题单

AcWing 1140. 最短网络

Prim或者Kruskal祼题,直接套模板即可

AcWing 1141. 局域网

最小生成森林，需要注意与最小生成树的区别,两种方法，推荐使用Kruskal

AcWing 1142. 繁忙的都市

Kruskal的简单应用,求分值最大的那条道路

AcWing 1143. 联络员

Kruskal的简单应用，先把必选的边放到并查集中，然后将可选的边由小到大排序，再进行Kruskal即可。

AcWing 1144. 连接格点

• 按边权先小后大建图，这样省的排序，当然，如果你愿意排序，顺序也不重要。
• 序号都是连着的，所以需要一个 get(x,y)的转换函数
• 注意最右边那列节点是无法向右引出边的，需要判断一下
• 现成的，必须有的边需要提前放到并查集中，其它的再跑Kruskal

三、最小生成树的扩展应用题单

AcWing 1146. 新的开始

• 利用超级源点将点权转为边权
• 注意加入超级源点后，遍历的节点数量+1

AcWing 1145. 北极通讯网络

• 魔改Kruskal算法，利它的框架，增加一点代码，检查剩余的连通块个数是不是 \leq cnt

AcWing 346. 走廊泼水节

• 由最小生成树扩展成完全图，这是我们的知识盲区，没有这样的定理或算法
• 逆向思维，是不是可以由一个完全图思考如何求它的最小生成树？这可以用Kruskal算法！
• 对边权由小到大排序，一个个进行讨论，当第一个不在集合中的边出现时，此边将为最小生成树的一条边。 那么，对于两个家族的其它成员而言，要想形成完全图，就需要笛卡尔积条边，对了，还需要把这条最小生成树的边去掉才行。
• 加上去的那些边，条边最小都需要比当前枚举到的边长大1才行,因为这样才能保证求出的是唯一最小生成树，并且这种补全办法的成本最低！

知识点 ① 并查集+维护个数 ② 逆向思维 ③ 最小生成树Kruskal算法

AcWing 1148. 秘密的牛奶运输