Prim 最小生成树CSP-S

💡 核心思想

Prim 算法从一个起始点出发，每次选择与当前生成树相连的边中权值最小的一条，将新顶点加入生成树。重复直到所有顶点都加入。适合稠密图，优先队列优化后适合稀疏图。

🎯 直觉理解

想象你要用最少的电缆把所有房子连起来。你从某一栋房子开始，每次选择离已经连通的房子群最近的一栋新房，拉一条线过去。不断重复直到所有房子都连上了。

📝 算法流程

1. 任选起点，标记已加入生成树
2. 在所有"一端在树内、一端在树外"的边中选最小的
3. 将新顶点和边加入生成树
4. 重复 n-1 次

$$\text{MST总权值} = \sum_{(u,v) \in T} w(u,v)$$

📊 复杂度分析

💻 参考实现（C++）

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    vector<vector<pair<int,int>>> adj(n+1);
    for (int i = 0; i < m; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    long long total = 0;
    vector<int> minW(n+1, INT_MAX);
    vector<bool> vis(n+1, false);
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    minW[1] = 0; pq.push({0, 1});
    while (!pq.empty()) {
        auto [w, u] = pq.top(); pq.pop();
        if (vis[u]) continue;
        vis[u] = true; total += w;
        for (auto [v, c] : adj[u]) {
            if (!vis[v] && c < minW[v]) {
                minW[v] = c;
                pq.push({c, v});
            }
        }
    }
    cout << total << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目