5.3.2 最小生成树

最小生成树是一个无向连通图中的一颗包含图中所有顶点的树（即无环），且具有最小总权重

而图的两个基本元素是点和边，与此对应，有两种算法可以构造MST，这两种算法都基于贪心法:

Kruskal（加边）：排序+DSU，适合稀疏图（）

Prim（加点）：优先队列，适合稠密图（）

Kruskal

对图中所有边进行贪心。从最短的边开始，把它加入T中；在剩下的边中找最短的边，加入T中；继续这个过程，直到T中包含n-1条边，或者所有点都在T中。

必备概念

记下三种核心结构：

struct Edge：用于存储每一条边的起点、终点和权重，并重载 < 运算符

fa[x]：DSU的父节点数组，用于计入点x属于哪个连通块

find[x]：DSU的寻根函数，并带有路径压缩功能

下面让我们代入一个场景：

你是一名极其抠门的包工头，要把个深山里的村庄连通起来，你手里有一本账本，上面记录了所有可以修的路以及它们的报价

你的策略极其简单粗暴：便宜的先修，能省则省。

沙盘推演：A、B、C 三个村庄，AB 要 1 万，BC 要 2 万，AC 要 10 万

我们跟着思路走一遍这个三角圈：

第一步：账本排序

你把账本按报价从小到大排好：第一名 AB(1万)，第二名 BC(2万)，第三名 AC(10万)。

一开始，所有村庄各自为政，A 的老大是 A，B 的老大是 B，C 的老大是 C。

第二步：看最便宜的 AB(1万)

你翻开账本第一页，是 AB。

你查了一下并查集，发现 find(A) 是 A，find(B) 是 B。老大不一样！

说明 A 和 B 还没连通。你果断拍板：”修！”

花费 +1万。现在 B 认 A 做老大（fa[B] = A），A 和 B 连通了。

第三步：看第二便宜的 BC(2万)

你翻开账本第二页，是 BC。

你查了一下并查集，find(B) 顺着找到了 A，而 find(C) 还是 C。老大不一样！

说明 B 所在的圈子和 C 还没连通。拍板：”修！”

花费 +2万。现在 C 认 A 做老大（fa[C] = A），A、B、C 全连通了。

第四步：看第三便宜的 AC(10万)

你翻到了 AC。

你查了一下，发现 find(A) 是 A，而 find(C) 也是 A。

两者相等！（对应代码：if(find(u) == find(v))）

这就是 Kruskal 算法最核心的 Aha Moment！

当一条边两端端点的”终极老大”是同一个人时，意味着什么？意味着这两个村庄早就通过别的暗道连通了！如果你现在花这 10 万把 AC 连起来，图里就会出现一个 A-B-C-A 的环，纯属浪费钱。

既然老大一样，包工头大喊一声：”这条路撕掉，不修！”

第五步：收网

你发现你已经修了条路了，村庄全连通了。算法直接结束，最省钱方案就是 3 万。

代码解析

初始化

记录我们的边集、并查集数组和最终的花费

const int N = 5005;
const int M = 200005;
struct Edge{
    int u,v,w;
    bool operator<(const Edge& o) const {
        return w < o.w;
    }
}edges[M];
int fa[N];
int n,m;

并查集

void init(){
    for(int i = 1;i <= n;++i) fa[i] = i;
}

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

Kruskal

接下来先进行预处理

sort(edges+1,edges+m+1);
init();
int res = 0; //记录总花费
int cnt = 0; //记录已经修了多少条路

遍历

for(int i = 1;i <= m;++i){
    int u = edges[i].u,v = edges[i].v,w = edges[i].w;
    u = find(u),v = find(v);
    if(u != v){
        fa[u] = v;
        res += w;
        cnt++;
        if(cnt == n-1) break;
    }
}

退出

1 2	if(cnt < n-1) return -1; //说明图不连通 return res;

综合

const int N = 5005;
const int M = 200005;

struct node{
    int u,v,w;
    bool operator < (const node& o) const{
        return w < o.w;
    }
}e[M];

int fa[N];
int n,m;

void init(){
    for(int i = 1;i <= n;++i) fa[i] = i;
}

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

int Kruskal(){
    sort(e+1,e+m+1);
    init();

    int res = 0;
    int cnt = 0;
    for(int i = 1;i <= m;++i){
        int u = e[i].u,v = e[i].v,w = e[i].w;
        u = find(u),v = find(v);
        if(u != v){
            fa[u] = v;
            res += w;
            cnt++;
            if(cnt == n-1) break;
        }
    }
    if(cnt < n-1) return -1;
    return res;
}

Prim

对点的最近邻居进行贪心，从任意点u开始，T = {u}，然后把距离它最近的邻居点v加入到T中，T = {u,v}；下一步，把距离{u,v}最近的邻居点w加入T中；继续这个过程，直到所有点都在T中。这个原理和最短路Dijkstra算法几位类似。

必备概念

记三个核心结构：

vis[u]：用来记录一个顶点是否被记录，vis[u] = 1表示已通网，vis[u] = 0表示还在黑暗中

priority_queue：当我们点亮一个据点时，会有很多条路通向黑暗。我们把这些路一股脑扔进优先队列里，它会自动帮我们把最便宜的那条路顶到最前面。

我们代入一个极其具体的沙盘推演：

地图情报：共有 4 个据点 (A, B, C, D)。A-B(2万)，A-C(3万)，B-C(1万)，B-D(4万)，C-D(5万)。

第一步：降落并建立初始光圈

我们任意选择 A 作为起点降落。
A 进入光圈（vis[A] = 1）。
站在 A 往外看，有两条路：通向 B(2万) 和通向 C(3万)。
全部扔进优先队列。此时队列：[B(2), C(3)]。

第二步：第一次扩张

优先队列弹出最便宜的路：去 B，只要 2 万。
检查 B：B 还在黑暗中（vis[B] == 0）。
拍板：花费 2 万！B 被拉入光圈（vis[B] = 1）。已通网：A, B。
站在刚点亮的 B 往外看，有两条新路：通向 C(1万) 和通向 D(4万)。
全部扔进队列。此时队列重新排队：[C(1), C(3), D(4)]。 (注意：队列里现在有两条去 C 的路，没关系，堆会自动处理)。

第三步：第二次扩张（核心防浪费）

优先队列弹出最便宜的路：去 C，只要 1 万（这是 B 带来的路）。
检查 C：C 还在黑暗中。
拍板：花费 1 万！C 被拉入光圈（vis[C] = 1）。已通网：A, B, C。
站在刚点亮的 C 往外看，有一条新路：通向 D(5万)。
扔进队列。此时队列：[C(3), D(4), D(5)]。

第四步：第三次扩张（触发判定）

队列弹出最便宜的路：去 C，3 万（这是最早 A 带来的路）。
检查 C：发现 C 已经在光圈里了！ (vis[C] == 1)
判定：如果花这 3 万，就会形成 A-B-C-A 的环。直接把这条路撕掉（continue）。
队列继续弹出下一条最便宜的路：去 D，4 万。
检查 D：D 在黑暗中。
拍板：花费 4 万！D 变成光圈（vis[D] = 1）。

收网：4 个点都已经点亮，修了 3 条路。总花费：2 + 1 + 4 = 7 万。算法完美结束。

代码解析

const int N = 5005;

struct node{
    int v;
    int w;
    bool operator>(const node& o) const{
        return w > o.w; //因为是优先队列，所以需要重载 >
    }
};

vector<node> e[N];
int vis[N];

Prim

起初。我们要准备好优先队列，并且降落在一号节点

priority_queue<node,vector<node>,greater<node>> pq;

int res = 0; //总花费
int cnt = 0; //已经点亮几个据点了

vis[1] = 1;

for(auto ei : e[1]){
    pq.push(ei);
}

而后，只要还没选够n-1条边，说明报价单里还有路，继续探索

while(!pq.empty() && cnt < n-1){
    node cur = pq.top();
    pq.pop();

    int u = cur.v;
    int w = cur.w;

    if(vis[u] == 1) continue;

    vis[u] = 1;
    res += w;
    cnt++;

    for(auto ei : e[u]){
        if(vis[ei.v] == 0){
            pq.push(ei);
        }
    }
}

退出

1 2	if(cnt == n-1) return res; else return -1;

综合代码

const int N = 5005;
struct node{
    int v,w;
    bool operator>(const node& o) const{
        return w > o.w;
    }
};

vector<node> e[N];
int vis[N];

int prim(int n){
    priority_queue<node,vector<node>,greater<node>> pq;
    vis[1] = 1;
    for(auto ei : e[1]) pq.push(ei);

    int res = 0,cnt = 0;
    while(!pq.empty() && cnt < n-1){
        node cur = pq.top();
        pq.pop();

        int u = cur.v;
        if(vis[u]) continue;

        vis[u] = 1;
        res += cur.w;
        cnt++;

        for(auto ei : e[u]){
            if(!vis[ei.v]){
                pq.push(ei);
            }
        }
    }
    return cnt == n-1 ? res : -1;
}

相关文章

[[5-2-3-Dijkstra]] [[5-2-4-SPFA-Bellman-Ford]] [[5-2-6-Floyd]] [[6-6-DSU]] [[5.2.10 Topological-Sort]]