最小生成树

最小生成树（Minimum Spanning Tree，MST）是图论中的一种概念，用于找到连接所有顶点且边权总和最小的树（默认带权无向图）

最小生成树模板题

Kruskal 算法

Kruskal 算法是一种贪心算法，其基本思想是从边出发：每次选择权值最小的边，若该边连接的两个顶点不在同一个连通分量中，则将其加入生成树中，直到生成树包含 \(n-1\) 条边为止

从边出发的视角使用边列表存储图 无向图连通性的判断使用并查集

#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class DS // 并查集
{
    vector<int> parent;
public:
    explicit DS(int n)
    {
        parent.resize(n);
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    int find(int x)
    {
        if (parent[x] != x)
        {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    bool unite(int x, int y)
    {
        int xroot = find(x);
        int yroot = find(y);
        if (xroot == yroot) return false;
        parent[xroot] = yroot;
        return true;
    }
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector<tuple<int,int,int>> edges; // 边列表
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--; // 根据题目选择 0/1 based
        // 只需记录连通性，无需考虑方向
        edges.emplace_back(w,u,v);
    }
    ranges::sort(edges); // 权重放 tuple 第一位
    long long ans = 0;
    int cnt = 0; // 边数
    DS ds(n);
    for (auto [w, u, v] : edges)
    {
        if (ds.unite(u, v))
        {
            ans += w;
            cnt++;
            if (cnt == n-1) break;
        }
    }

    if (cnt != n-1) // 不连通
    {
        cout << "orz"; return 0;
    }
    cout << ans;
}

• 时间复杂度：\(O(m\log m)\)，其中 \(m\) 为边数，瓶颈在于排序

Prim 算法

Prim 算法也是一种贪心算法，其基本思想是从点出发：从任意一个顶点开始，每次选择距离生成树最近的顶点，将其加入生成树中，直到生成树包含 \(n\) 个顶点为止

从点出发的视角使用邻接表存储图 最近点的选择使用优先队列

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    vector adj(n, vector<tuple<int,int>>()); // 邻接表
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--; // 根据题目选择 0/1 based
        adj[u].emplace_back(v,w); // 无向图
        adj[v].emplace_back(u,w);
    }

    // 权重，点号
    priority_queue<tuple<int, int>, vector<tuple<int,int>>, greater<>> pq;
    pq.emplace(0,0); // 任意点开始，权重设为 0
    long long ans = 0;
    vector visited(n, false);
    int cnt = 0;
    while (!pq.empty())
    {
        auto [w, u] = pq.top();
        pq.pop();
        if (visited[u]) continue; // 出堆再特判，防死循环
        visited[u] = true;
        ans += w; // 出堆时更新全局最小权重
        cnt++;
        if (cnt == n) break;
        
        for (auto [v, ww] : adj[u])
        {
            if (visited[v]) continue; // 剪枝！
            pq.emplace(ww, v);
        }
    }
    if (cnt != n) // 不连通
    {
        cout << "orz"; return 0;
    }
    cout << ans;
}

• 时间复杂度：\(O(m\log m)\)

Gemini 3.0 pro 的一句话总结：

• 如果图非常稠密（边多），用朴素版 Prim
• 如果是稀疏图（大多数算法题），用 Kruskal

Prim 与 Dijkstra 算法十分类似，故在该总结中的原理也相同（如有需要请移步这里）