最小生成树

概念讲解

什么是 MST？

最小生成树（Minimum Spanning Tree）是连通图的一棵生成树，使得所有边的权值之和最小。

性质

1. 边数 = 顶点数 - 1
2. 不唯一（可能有多个 MST）
3. 切割性质：任意切割，穿越的最小边一定在 MST 中

Kruskal 算法

思路

1. 将所有边按权值排序
2. 依次选边，如果不成环则加入 MST
3. 使用并查集判断是否成环

代码

123456789101112131415161718192021struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

int kruskal(vector<Edge>& edges, int n) {
    sort(edges.begin(), edges.end());
    init(n);
    int mst = 0, cnt = 0;
    for (auto& [u, v, w] : edges) {
        if (find(u) != find(v)) {
            unite(u, v);
            mst += w;
            cnt++;
            if (cnt == n - 1) break;
        }
    }
    return cnt == n - 1 ? mst : -1;
}

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

Prim 算法

思路

1. 选一个起点加入集合
2. 每次选连接集合内外的最小边
3. 将新点加入集合

代码

1234567891011121314151617181920int prim(vector<vector<pair<int,int>>>& graph, int n) {
    vector<bool> visited(n+1, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, 1});
    int mst = 0, cnt = 0;
    
    while (!pq.empty() && cnt < n) {
        auto [w, u] = pq.top();
        pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        mst += w;
        cnt++;
        
        for (auto& [v, w2] : graph[u]) {
            if (!visited[v]) pq.push({w2, v});
        }
    }
    return cnt == n ? mst : -1;
}

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

考点分析

初赛考查方式

1. 程序阅读： MST 算法
2. 编程题： MST 应用

常见考点

• Kruskal 算法
• Prim 算法
• 切割性质

例题精讲

例题 1：Kruskal

题目： 求图的 MST。

解答：

按边权排序，依次选边，用并查集判环。

练习题

1. Kruskal 和 Prim 的区别是什么？

2. MST 的边数是多少？

3. 如何判断 MST 是否唯一？

易错点

⚠️ 注意：

1. Kruskal 要先排序
2. Prim 用优先队列优化
3. 注意判断图是否连通
4. MST 可能不唯一