图论算法篇：最小生成树（MST）——Kruskal 算法、贪心思想及经典例题总结

目录

本文内容概要

一、认识最小生成树

1.1 什么是生成树

1.2 什么是最小生成树

1.3 最小生成树的基本性质

二、Kruskal 算法

2.1 Kruskal 算法的核心思想

2.3 Kruskal 算法的代码实现

2.4 Kruskal 算法的时间复杂度与空间复杂度

三、Kruskal 算法的正确性分析

3.1 最小生成树的切分性质

3.2 Kruskal 算法的正确性证明

四、Prim 算法简介

五、最小生成树的常见变形与经典例题

5.1 最小生成森林——P1195「口袋的天空」

5.2 最小瓶颈问题——P1991「无线通讯网」

5.3 虚拟源点与集合状态——P1550「Watering Hole」

方法一：虚拟源点建图

方法二：维护每个集合的最低挖井费用

5.4 反向贪心——P2700「逐个击破」

直接思考：选择哪些边进行删除？

换个角度：选择哪些边应该保留？

为什么按照边权降序？

5.5 稠密图与算法选择——P1265「公路修建」

六、其他值得掌握的最小生成树题型

七、最小生成树专题的学习总结

7.1 正确理解题意，再建立算法模型

7.2 学会转换贪心的角度

7.3 并查集不仅能够维护连通关系

7.4 不要忽略算法的适用条件

7.5 从会写模板到理解正确性

7.6 总结

---

本文内容概要

本文主要介绍图论中的最小生成树（Minimum Spanning Tree，简称 MST），重点讲解 Kruskal 算法的贪心思想、并查集实现及其正确性原理，同时简单介绍 Prim 算法及两种算法的适用场景。

在掌握基础算法之后，结合洛谷中的经典题目，进一步探讨最小生成森林、最小瓶颈生成树、虚拟源点建图、集合状态维护以及反向贪心等应用，最后对实际解题中容易遇到的问题进行总结。

---

一、认识最小生成树

1.1 什么是生成树

对于一张无向连通图，如果从原图中选择一部分边，使得这些边能够连接原图中的全部顶点，并且不存在环，那么由这些顶点和边构成的图就称为原图的一棵生成树。

生成树具有以下几个基本性质：

1. 包含原图中的全部顶点

2. 任意两个顶点之间都存在直接路径或间接路径

3. 不存在环

4. 如果原图包含 N 个顶点，那么生成树必然包含 N - 1条边

为什么恰好是 N - 1 条边

我们可以从连通分量的角度进行理解。

最开始，假设每个顶点都是一个独立的连通分量，那么共有 N 个连通分量。

每添加一条连接不同连通分量的边，就能够将两个连通分量合并成一个，此时连通分量的数量减少 1。当所有顶点都连通时，连通分量数量变成 1，因此需要： N - 1 次有效合并。

与此同时，由于每次连接的都是不同的连通分量，因此不会形成环。

所以，一棵包含 N 个顶点的生成树，必然恰好具有 N - 1 条边。

1.2 什么是最小生成树

对于一张带权无向连通图，可能存在多棵不同的生成树。

虽然这些生成树都满足连通、无环以及包含全部顶点的要求，但是它们所选择的边不同，因此所有边的权值之和也可能不同。

我们将所有生成树中，边权之和最小的生成树称为最小生成树。

注：最小生成树所追求的是所有选中边的权值之和最小，并不要求任意两个顶点之间的路径都是最短路径。

这是最小生成树与最短路径问题的本质区别。

1.3 最小生成树的基本性质

性质	说明
图的类型	带权无向连通图
顶点数量	包含全部 N 个顶点
边的数量	恰好为 N-1
连通性	任意两个顶点之间均可到达
是否存在环	不存在
优化目标	选中边的权值之和最小
是否唯一	不一定唯一

其中有几个容易混淆的问题。

问题一：最小生成树一定唯一吗？

不一定。

如果所有边的权值互不相同，那么最小生成树一定唯一。但是，存在相同权值的边，并不意味着最小生成树一定不唯一。

问题二：最小生成树允许负权边吗？

允许。

需要注意的是，即使加入某条负权边能够让总权值更小，如果加入之后形成环，也不能选择这条边。

因为我们的目标并不是单纯让所有选中边的权值之和尽可能小，而是在满足生成树性质的前提下，使边权之和最小。

问题三：原图不连通怎么办？

如果原图本身不连通，那么不存在覆盖全部顶点的生成树。

不过，我们可以对原图的各个连通分量分别求最小生成树，最终得到最小生成森林（Minimum Spanning Forest）。

二、Kruskal 算法

2.1 Kruskal 算法的核心思想

Kruskal 是一种基于贪心思想的最小生成树算法。

核心思想：每次优先选择当前权值最小、且不会形成环的边，将其加入生成树，直到成功选择      N - 1 条边。

整个过程可以分为以下几个步骤：

1. 将所有边按照权值从小到大排序。

2. 初始化并查集，每个顶点独立构成一个集合。

3. 按照排序后的顺序依次考虑每条边。

4. 如果这条边连接的两个顶点已经属于同一个集合，则跳过，否则选择该边并合并两个集合。

5. 当成功选择 N - 1 条边时，最小生成树构建完成。

从本质上来说，Kruskal 可以理解为：

贪心策略负责选择当前代价最小的合法边，并查集负责判断这条边是否会形成环。

并查集本身不负责寻找最优解，而是用于快速维护连通关系。

2.3 Kruskal 算法的代码实现

下面给出一份基于并查集的 Kruskal 模板。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/*
    Kruskal 最小生成树
    1. 将所有边按照权值升序排序
    2. 使用并查集判断两个节点是否连通
    3. 如果不连通，则合并集合，并累加当前边权
    4. 成功选择 n - 1 条边后结束
*/
struct edge
{
    int u;
    int v;
    ll w;
};

int n, m;
vector<int> f;
vector<edge> edges;

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

int find(int pos)
{
    if(pos != f[pos])
        f[pos] = find(f[pos]);
    return f[pos];
}

bool unite(int x, int y)
{
    int fx = find(x);
    int fy = find(y);

    if(fx == fy)
        return false;

    f[fx] = fy;
    return true;
}

void solve()
{
    cin >> n >> m;

    f.resize(n + 1);
    edges.resize(m);
    Init();

    for(int i = 0; i < m; ++i)
        cin >> edges[i].u >> edges[i].v >> edges[i].w;

    sort(edges.begin(), edges.end(),
    [](const edge &x, const edge &y)
    {
        return x.w < y.w;
    });

    ll ans = 0;
    int cnt = 0;

    for(int i = 0; i < m; ++i)
    {
        if(unite(edges[i].u, edges[i].v))
        {
            ans += edges[i].w;
            ++cnt;
        }

        if(cnt == n - 1)
            break;
    }

    if(cnt == n - 1)
        cout << ans << "\n";
    else
        cout << "orz\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;
    while(t--)
        solve();

    return 0;
}

其中，cnt 表示已经成功选择的边数。

如果遍历结束后：

cnt != n - 1

说明原图不存在包含所有顶点的生成树。

注：这里使用 orz 作为输出，仅对应洛谷 P3366 等题目的要求，实际解题时需要根据题目修改。

2.4 Kruskal 算法的时间复杂度与空间复杂度

假设图中有 N 个顶点、M 条边。

1. 时间复杂度

Kruskal 算法主要包含以下操作：

• 初始化并查集： 需要遍历 N 个顶点，时间复杂度为 O(N)。

• 读取所有边： 需要读取 M 条边，时间复杂度为 O(M)。

• 按照边权排序： 对 M 条边进行排序，时间复杂度为 O(M log M)。

• 并查集操作： 最多遍历 M 条边，每条边执行查找或合并操作。如果使用路径压缩，通常效率很高；结合按秩合并时，总时间复杂度为 O(M α(N))。

因此，Kruskal 算法的总时间复杂度为：

O(N) + O(M) + O(M log M) + O(M α(N))

由于边排序通常是主要的时间开销，因此对于一般的连通图，可以简化为：

总时间复杂度：O(M log M)

其中，α(N) 表示反阿克曼函数，其增长速度极其缓慢，在实际数据范围内可以近似看作一个很小的常数。

2. 空间复杂度

Kruskal 算法主要需要以下存储空间：

• 并查集数组： 存储 N 个顶点的集合关系，空间复杂度为 O(N)。

• 边数组： 存储 M 条边的信息，空间复杂度为 O(M)。

因此，总空间复杂度为：

O(N + M)

综上，Kruskal 算法主要的性能开销集中在边的排序操作上，因此通常比较适合处理边数相对较少的稀疏图。

三、Kruskal 算法的正确性分析

学习 Kruskal 算法时，有一个值得深入思考的问题：

为什么每次选择当前权值最小、且不会形成环的边，就一定能够得到全局最优解？

需要注意的是，局部最优并不一定意味着全局最优。因此，我们不能仅仅因为每次选择的边权值最小，就直接认为最终构造的生成树一定最优。

对于 Kruskal 算法，可以利用最小生成树的切分性质和交换论证来证明其贪心策略的正确性。

3.1 最小生成树的切分性质

假设将一张无向连通图的所有顶点划分成两个非空集合：

• S：其中一部分顶点。

• V - S：剩余的所有顶点。

所有连接这两个集合的边，都称为跨越该切分的边（跨切分边）。

例如，假设集合 S 中包含顶点 A、B，集合 V - S 中包含顶点 C、D。

那么，连接 A 与 B 的边属于集合内部的边，而连接 A 与 C、B 与 D 的边则属于跨切分边。

切分性质：

对于任意一个切分，至少存在一棵最小生成树包含该切分中权值最小的边。

进一步地：

• 如果最小跨切分边有多条，那么任意一条都可以包含在某棵最小生成树中。

• 如果最小跨切分边唯一，那么这条边必然存在于每一棵最小生成树中。

这条性质实际上说明：

选择某个切分中的最小权值边，不会破坏构造最小生成树的可能性。

Kruskal 算法正是利用这一性质，不断选择安全的边，逐步构造最小生成树。

3.2 Kruskal 算法的正确性证明

下面利用交换论证，说明 Kruskal 的贪心策略为什么能够得到全局最优解。

第一步：假设当前选择一条边

假设 Kruskal 当前准备选择一条边：

e = (u, v)

其中，顶点 u 和 v 属于两个不同的连通分量。

由于所有边已经按照权值升序排序，因此 e 是当前可以连接不同连通分量的最小权值边。

第二步：假设某棵最小生成树没有选择这条边

假设存在一棵最小生成树 T，它包含此前 Kruskal 已经选择的所有边，但是没有包含当前准备选择的边 e。

由于 T 是一棵生成树，因此顶点 u 和 v 之间必然存在一条路径。

此时，如果将边 e 加入 T，就会形成一个环。

第三步：寻找环中可以替换的边

由于 u 和 v 原本属于两个不同的连通分量，因此在新形成的环中，必然存在另一条边 e'，连接 u 所在的当前连通分量与外部顶点。

因为 Kruskal 选择的是当前权值最小的合法边，所以：

w(e) ≤ w(e')

也就是说，当前选择的边 e，其权值不会大于可以被替换的边 e'。

第四步：进行边的替换

现在，我们从生成树 T 中删除边 e'，并加入边 e。

由于这两条边位于同一个环中，因此删除 e' 后：

• 所有顶点仍然保持连通。

• 不会存在环。

• 生成树的边数不变。

• 生成树的总权值不会增加。

因此，替换后得到的仍然是一棵最小生成树，而且包含了当前 Kruskal 选择的边 e。

第五步：得出结论

通过上述分析可以发现：

对于 Kruskal 每次选择的最小合法边，都能够找到一棵包含此前所有已选边以及当前边的最小生成树。

因此，每一次贪心选择都是安全的，不会破坏最终得到全局最优解的可能性。

不断重复这一过程，直到成功选择 N - 1 条边，就能够构造出一棵最小生成树。

这也证明了 Kruskal 算法的正确性。

四、Prim 算法简介

除了 Kruskal 之外，Prim 也是一种常见的最小生成树算法。

两者都采用贪心策略，但贪心的角度不同。

Kruskal 从边的角度出发，不断合并不同的连通分量。

Prim 则从一个顶点开始，不断扩展当前生成树。

Prim 的基本过程：

1. 选择任意顶点作为起点。

2. 维护每个未加入顶点到当前生成树的最小连接代价。

3. 每次选择连接代价最小的外部顶点，将其加入生成树。

4. 根据新加入的顶点，更新其他顶点的最小连接代价。

5. 直到所有顶点都加入生成树。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
/*
    堆优化 Prim 算法
    1. 使用邻接表存储图
    2. 使用小根堆维护顶点到当前生成树的最小连接代价
    3. 每次选择距离当前生成树最近的顶点
    4. 利用新加入的顶点更新其他顶点的最小连接代价

    时间复杂度：O(M log N)（常见简化写法）
    空间复杂度：O(N + M)
*/
const ll INF = LLONG_MAX;

struct edge
{
    int v;
    ll w;
};

struct node
{
    int u;
    ll w;

    bool operator>(const node &x) const
    {
        return w > x.w;
    }
};

int n, m;
vector<vector<edge>> g;
vector<ll> dist;
vector<bool> vis;

void Init()
{
    g.resize(n + 1);
    dist.resize(n + 1, INF);
    vis.resize(n + 1, false);
}

void solve()
{
    cin >> n >> m;
    Init();

    for(int i = 1; i <= m; ++i)
    {
        int u, v;
        ll w;
        cin >> u >> v >> w;

        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

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

    dist[1] = 0;
    pq.push({1, 0});

    ll ans = 0;
    int cnt = 0;

    while(!pq.empty())
    {
        node cur = pq.top();
        pq.pop();

        int u = cur.u;

        if(vis[u])
            continue;

        vis[u] = true;
        ans += cur.w;
        ++cnt;

        for(const auto &e : g[u])
        {
            int v = e.v;
            ll w = e.w;

            if(!vis[v] && w < dist[v])
            {
                dist[v] = w;
                pq.push({v, w});
            }
        }
    }

    if(cnt == n)
        cout << ans << "\n";
    else
        cout << "orz\n";
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
    // cin >> t;
    while(t--)
        solve();

    return 0;
}

Kruskal 与 Prim 的对比如下：

对比项	Kruskal	Prim
贪心对象	当前合法的最小权值边	当前生成树到外部顶点的最小连接边
核心数据结构	排序、并查集	dist[]、邻接表、优先队列
常见时间复杂度	O(M * log M)	堆优化 O(M * log N)
常用场景	稀疏图及各类生成森林变形	稠密图、隐式完全图

需要注意的是，并不存在 Kruskal 或 Prim 在所有场景下都绝对更优的情况，应根据具体数据范围和图的结构进行选择。

五、最小生成树的常见变形与经典例题

掌握 Kruskal 的基础实现之后，真正值得学习的是如何将它应用到不同类型的问题中。

下面结合几道经典题目，记录比较有价值的解题思想。

5.1 最小生成森林——P1195「口袋的天空」

题目链接：https://www.luogu.com.cn/problem/P1195

题目核心：

给出 N 个节点和若干条带权边，要求将所有节点划分成恰好 K 个连通分量，使选中边的权值之和最小。

这道题与普通最小生成树非常相似。

普通最小生成树要求最终只剩下一个连通分量，而这道题要求保留 K 个连通分量。

从并查集的角度分析：

• 初始有N个连通分量。

• 每次成功合并，连通分量数量减少 1。

• 当连通分量数量减少至 K 时，停止合并。

因此，成功合并的次数为：n - k

算法仍然是 Kruskal，只需要修改终止条件。

int cnt = 0;
ll ans = 0;

for(const auto &e : edges)
{
    if(unite(e.u, e.v))
    {
        ans += e.w;
        ++cnt;

        if(cnt == n - k)
            break;
    }
}

如果最终成功合并次数不足 N - K，说明无法得到恰好 K 个连通分量。

值得学习的地方：

最小生成树并不一定要求最终只有一个连通分量。

普通最小生成树可以看作最小生成森林在 K=1 时的特殊情况。

5.2 最小瓶颈问题——P1991「无线通讯网」

题目链接：https://www.luogu.com.cn/problem/P1991

这道题与 P1195 有很强的联系。

题目给出若干个哨所及其坐标，以及一定数量的卫星电话，要求确定最小的无线电通信距离，使所有哨所之间能够直接或间接通信。

关键在于：

没有卫星电话的哨所，也可以通过其他哨所进行间接通信。

假设有 S 部卫星电话，那么我们最多可以将无线电网络划分成 S 个连通分量。

只需要让每个连通分量中的一个哨所拥有卫星电话，不同连通分量之间就能够通过卫星通信实现连接。

因此，问题可以转化为：

将全部哨所划分成最多 S 个连通分量，并使所有保留的无线电连接中，最大距离尽可能小。

仍然可以使用 Kruskal。

不同的是，这道题的优化目标不是边权之和，而是：两者之间的距离

按照边权升序进行 Kruskal，每成功合并一次，连通分量数量减少 1。

当连通分量数量变成 S 时，最后一条成功加入的边权，就是所需的最小通信距离。

值得学习的地方：

虽然 P1195 与 P1991 都可以在剩余指定数量的连通分量时停止，但两者的优化目标并不一样。

题目	优化目标
P1195	最小化所选边权之和
P1991	最小化所选边中的最大权值

因此，不能只根据两道题使用相同的算法，就认为它们是完全相同的问题。

5.3 虚拟源点与集合状态——P1550「Watering Hole」

题目链接：https://www.luogu.com.cn/problem/P1550

题目核心：

有若干块田地，每块田地都可以独立挖井，也可以通过修建水道从其他田地获取水源。

已知每块田地的挖井费用，以及不同田地之间修建水道的费用，要求使所有田地都能够获得水源，并使总花费最小。

这道题比较值得深入研究，因为它并不是最直观的最小生成树模型。

方法一：虚拟源点建图

我们可以引入一个虚拟节点 (0)。

对于每块田地 (i)，添加一条连接虚拟节点与田地的边：(0, i, w[i])

其中 w[i] 为田地 i 的挖井费用。

这样一来：

• 选择边 (0,i)，表示在田地 i 挖井。

• 选择边 (i,j)，表示在田地 i、j 之间修建水道。

原本的挖井问题就被转换成了一个普通的最小生成树问题。

值得学习的地方：

在图论建模中，可以通过添加虚拟节点，将原本不同类型的操作转化成统一的边权选择问题。

这种思路并不局限于最小生成树，在其他图论问题中也经常出现。

方法二：维护每个集合的最低挖井费用

除了虚拟源点，还可以从集合合并的角度思考。

假设当前存在两个连通分量 A、B，其内部最低挖井费用分别为：a, b

现在考虑一条连接两个集合的水道，其费用为 c。

如果不进行合并，那么两个集合分别需要一口井，总费用为：a + b

如果进行合并，那么只需要修建这条水道，并在合并后的集合中挖一口井：c + min(a,b)

因此，合并不会增加费用的条件为：c <= max(a, b)

因此，在按照水道费用升序处理边时，我们可以采用如下合并策略：

int fx = find(u);
int fy = find(v);

if(fx != fy && cost <= max(w[fx], w[fy]))
{
    f[fx] = fy;
    w[fy] = min(w[fx], w[fy]);

    ans += cost;
}

最终，每个连通分量内部只需要开凿一口费用最低的井。

将所有水道费用与各个连通分量的最低挖井费用累加，即可得到答案。

这里有两个非常重要的细节。

第一：为什么只需要维护集合中的最低挖井费用？

因为在一个连通分量中，只要有一口井，其余田地就可以通过水道获得水源。

因此，对于一个已经连通的集合，其他更昂贵的挖井方案不会比最低费用的方案更优。

集合合并后，只需要保留：min(a, b)

作为新集合的最低挖井费用即可。

第二：为什么必须按照水道费用升序排序？

虽然合并条件能够判断当前合并是否划算，但如果不按边权顺序处理，就可能提前选择昂贵的水道，错过后续更便宜的连接方式。

仅仅保证每次合并不会增加当前费用，并不能独立保证全局最优。

这套算法的正确性可以从虚拟源点 Kruskal 的角度理解：当水道费用不超过两个集合最低挖井费用的较大值时，按照升序处理，它可以作为当前的安全合并选择。

这道题值得学习的核心不是记住一个判断公式，而是学会为连通分量维护能够支持后续决策的状态信息。

5.4 反向贪心——P2700「逐个击破」

题目链接：https://www.luogu.com.cn/problem/P2700

这是一道非常值得复盘的最小生成树思想变形题。

题目核心：

给出一棵包含 N 个节点的树，其中 K 个节点被敌军占领。

删除树中的道路需要支付对应费用。

要求删除部分道路，使得任意两个敌军占领的节点之间都不存在路径，并使破坏费用之和最小。

直接思考：选择哪些边进行删除？

直观上，我们可能会考虑：

每次选择一条破坏费用最小的道路，同时确保这次破坏是有效的。

但是，这种贪心策略不容易保证全局最优。

因为一条道路被删除后，可能影响多个敌军节点之间的连通关系。

换个角度：选择哪些边应该保留？

由于原图的所有道路费用之和固定，因此：最小破坏费用=总费用-最大保留费用

原问题就可以转换为：

在保证任意两个敌军节点不连通的前提下，尽可能保留权值大的道路。

这样就可以使用类似最大生成树的 Kruskal 贪心策略。

具体步骤：

1. 将所有边按照权值从大到小排序。

2. 使用并查集维护当前连通分量。

3. 每个连通分量额外维护一个状态，表示内部是否存在敌军节点。

4. 如果合并之后会使两个敌军节点连通，则不能保留该边，将其费用计入答案。

5. 否则保留该边，合并两个连通分量。

合并条件如下：

集合 A	集合 B	能否合并
没有敌军	没有敌军	可以
存在敌军	没有敌军	可以
没有敌军	存在敌军	可以
存在敌军	存在敌军	不可以

核心代码：

sort(edges.begin(), edges.end(),
[](const edge &a, const edge &b)
{
    return a.w > b.w;
});

ll ans = 0;

for(const auto &e : edges)
{
    int fx = find(e.u);
    int fy = find(e.v);

    if(flag[fx] && flag[fy])
    {
        // 保留这条边会使两个敌军连通
        ans += e.w;
    }
    else
    {
        // 保留道路，合并集合
        f[fx] = fy;
        flag[fy] = flag[fx] || flag[fy];
    }
}

这里利用了题目给出的原图是一棵树的性质，所以在遍历尚未处理的原始边时，其两端在已保留森林中必然属于不同连通分量。

为什么按照边权降序？

因为我们希望尽量保留破坏代价高的道路。

对于 Kruskal 而言，按照边权升序可以构造最小生成树，而反过来按照边权降序，则可以构造最大生成树。

这道题可以进一步理解为一个带有特殊约束的最大生成森林问题。

当两个连通分量都包含敌军时，说明继续保留当前边会违反约束，因此这条边必须被删除。

值得学习的地方：

当正向考虑删除哪些边比较困难时，可以尝试转化为保留哪些边。

同时，并查集不仅可以维护节点之间是否连通，还可以维护一个连通分量是否满足某种特殊性质。

这种“反向贪心 + 集合状态维护”的思路，在其他题目中也具有很强的迁移价值。

5.5 稠密图与算法选择——P1265「公路修建」

题目链接：https://www.luogu.com.cn/problem/P1265

这道题的关键不在于 Kruskal 的正确性，而在于算法的时间与空间复杂度。

假设图中存在 N 个顶点，并且任意两个顶点之间都存在一条边，那么这张图就是一张完全图。

对于无向完全图，每两个顶点之间只需要一条边，因此总边数为：

M = N × (N - 1) / 2

由此可知，当顶点数量为 N 时，边的数量级为 O(N²)。

如果采用 Kruskal 算法，就需要先枚举并存储所有边，再按照边权从小到大排序。

由于边数最多达到 O(N²)，因此：

• 时间复杂度：O(N² log N)，主要来自所有边的排序操作。

• 空间复杂度：O(N²)，主要用于存储全部候选边。

例如，当 N = 5000 时，完全图的边数为：

M = 5000 × 4999 / 2 = 12,497,500

也就是说，需要存储大约 1250 万条边，不仅占用大量内存，而且排序开销也比较大。

因此，对于这种可以根据顶点坐标直接计算边权的稠密图，使用朴素 Prim 算法通常更加合适。

朴素 Prim 不需要提前存储所有边，只需要维护每个顶点到当前生成树的最小连接代价，因此：

• 时间复杂度：O(N²)

• 额外空间复杂度：O(N)

相比直接枚举全部边的 Kruskal，朴素 Prim 在这种场景下能够有效降低内存开销，并避免对大量边进行排序。

值得学习的地方：

算法选择不能只考虑正确性，还需要根据数据范围以及图的结构分析时间、空间复杂度。

对于隐式完全图，如果每条边的权值都能够根据顶点信息直接计算，那么使用 Prim 往往比显式建出全部边再执行 Kruskal 更合适。

六、其他值得掌握的最小生成树题型

除了上面重点介绍的几道题，其他一些经典题目也可以帮助理解最小生成树的不同性质。

题目	核心思想	值得学习的地方
P3366 最小生成树	Kruskal 模板	并查集、边排序、连通性判断
P1546 最短网络	邻接矩阵建图	读取并转化图结构
P2330 繁忙的都市	最小瓶颈生成树	最小生成树的瓶颈性质
P2820 局域网	保留最小生成树	删除费用等于总权值减去最小生成树权值
P1194 买礼物	特殊建图	将实际费用选择转换为图问题
P2872 道路建设	坐标与已有连接	处理已有连通关系、按距离建边

这些题目虽然都可以使用最小生成树相关算法，但是不同题目对建图方式、贪心目标以及答案统计方法的要求并不一样。

因此，学习时不应该只关注代码模板，更应该关注题目是如何被抽象成图论模型的。

七、最小生成树专题的学习总结

经过这一阶段的学习，可以将最小生成树相关题目归纳成几个主要方向。

题型	核心处理方式
普通最小生成树	Kruskal 升序选边，累计边权
最小生成森林	Kruskal 合并到指定连通分量数量
最小瓶颈问题	关注最后一次成功合并的边权
虚拟源点建图	将特殊操作转化为图中的边
集合状态维护	在并查集中维护连通分量的额外信息
反向贪心	从删除费用最小转化为保留费用最大
稠密图问题	根据复杂度选择 Prim 等算法

在实际解题过程中，我认为有几个方面尤其值得重视。

7.1 正确理解题意，再建立算法模型

图论问题中，首先需要确定：

• 哪些顶点必须包含？

• 最终需要几个连通分量？

• 允许直接连接还是间接连通？

• 优化的是边权总和，还是最大边权？

• 是否对连通分量存在额外限制？

例如 P1195 与 P1991，两道题表面上不同，但理解题意后都可以转化为对连通分量数量的控制。

7.2 学会转换贪心的角度

对于 P2700，直接考虑如何以最低费用删除道路并不容易。

但是利用总权值固定这一性质，可以将最小删除费用转化为最大保留费用，从而找到基于 Kruskal 的贪心方法。

这说明：

当一个问题的直接贪心策略难以设计时，可以考虑它的补集、反问题或者等价优化目标。

7.3 并查集不仅能够维护连通关系

传统并查集主要用于判断两个顶点是否连通。

但在实际题目中，还可以根据需求，为每个集合额外维护信息。

例如：

• P1550：维护集合内部的最低挖井费用。

• P2700：维护集合内部是否存在敌军。

这种集合状态维护思想，在图论以及其他数据结构题目中都十分重要。

7.4 不要忽略算法的适用条件

即使已经熟练掌握某种算法，也不能在所有相关题目中直接套用。

例如 Kruskal 通常需要存储并排序所有候选边，当图非常稠密时，排序和存储的开销可能成为性能瓶颈。

因此，在动手编写代码之前，应先分析图中的顶点数量 N、边的数量 M，以及所选算法的时间复杂度和空间复杂度，再结合题目给出的时间限制与内存限制，选择合适的算法实现。

根据数据范围选择合适的实现方式。

7.5 从会写模板到理解正确性

Kruskal 的代码实现并不复杂，其核心不过是排序、并查集和贪心选择。

但真正值得理解的是：

为什么当前选择的边是安全的？为什么这种局部最优策略能够得到全局最优解？

切分性质与交换论证，是理解 Kruskal 正确性的关键。

掌握这些理论之后，才能更好地分析类似 P1550、P2700 这样的变形题，而不是单纯依赖固定模板。

7.6 总结

最小生成树是图论中比较经典的一类问题，其核心算法 Kruskal 可以概括为：

贪心选择 + 并查集维护连通关系。

但在不同的应用场景中，贪心选择的方向、连通分量需要维护的信息以及最终优化目标都可能发生变化。

通过这一专题的学习，不仅需要掌握最小生成树的基础实现，更需要学会从题目中抽象图结构、分析贪心策略以及利用并查集维护集合状态。

这也是从掌握算法模板，逐渐过渡到独立分析算法问题的重要过程。

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/Felix_kiss_L/article/details/168344002