算法基础：最小生成树的“两大神功” (Prim & Kruskal) - 图论 - 算法 | 欢迎来到百解BaiJay的博客 = 白百流云 = 循此苦旅,终抵群星

什么是最小生成树 (MST)？
想象你要给好几个村庄通电，村庄之间连电线的费用不同。你的目标是：用最少的总费用把所有村庄连通，且不形成回路。这个 “最省钱的连接方案” 就是最小生成树。

# 1. Kruskal 算法：加边法 (贪心 + 并查集)

Kruskal 的思想非常直观：总是找最短的那条边。

# 核心步骤：

把图中所有的边按权值（长度）从小到大排序。
依次取出边，如果这条边的两个端点还没连通，就选它；如果已经连通了，就丢弃（防止形成环）。
直到选够了 $n-1$ 条边。

# C++ 代码实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 定义边的结构体
struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w < other.w; // 按权值升序排序
    }
};

int parent[1005];

// 并查集查找根节点
int find(int i) {
    if (parent[i] == i) return i;
    return parent[i] = find(parent[i]);
}

int main() {
    int n, m; // n个点，m条边
    cin >> n >> m;
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++) cin >> edges[i].u >> edges[i].v >> edges[i].w;

    // 1. 排序
    sort(edges.begin(), edges.end());

    // 2. 初始化并查集
    for (int i = 1; i <= n; i++) parent[i] = i;

    int mst_weight = 0, count = 0;
    for (auto& edge : edges) {
        int rootU = find(edge.u);
        int rootV = find(edge.v);

        // 3. 如果不在一个集合，合并它们
        if (rootU != rootV) {
            parent[rootU] = rootV;
            mst_weight += edge.w;
            count++;
        }
    }

    if (count == n - 1) cout << "最小生成树权重: " << mst_weight << endl;
    else cout << "图不连通" << endl;

    return 0;
}

# 2. Prim 算法：加点法 (切分定理)

Prim 的思想是：从一个点出发，慢慢向外扩张。

# 核心步骤：

随意选一个起点加入 “已连接集合”。
寻找一条最短的边，这条边的一头在 “已连接集合” 里，另一头在 “未连接集合” 里。
把这个新点拉进来，重复步骤 2，直到所有点都在集合里。

# C++ 代码实现：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

const int INF = 1e9;
typedef pair<int, int> PII; // {权值, 节点编号}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<PII>> adj(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({w, v});
        adj[v].push_back({w, u});
    }

    priority_queue<PII, vector<PII>, greater<PII>> pq;
    vector<int> dist(n + 1, INF); // 到达集合的最短距离
    vector<bool> visited(n + 1, false);

    int mst_weight = 0;
    dist[1] = 0;
    pq.push({0, 1}); // 从1号点开始

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (visited[u]) continue;
        visited[u] = true;
        mst_weight += d;

        for (auto& edge : adj[u]) {
            int w = edge.first;
            int v = edge.second;
            if (!visited[v] && w < dist[v]) {
                dist[v] = w;
                pq.push({dist[v], v});
            }
        }
    }

    cout << "最小生成树权重: " << mst_weight << endl;
    return 0;
}

# 💡 总结：我该选哪一个？

算法	核心思想	适合场景	时间复杂度
Kruskal	找最短的边	稀疏图（边比较少的情况）
Prim	找最近的点	稠密图（边非常多的情况）

面试小贴士： > 记住，Kruskal 依赖于排序和并查集，而 Prim 依赖于优先队列（堆）。如果你是初学者，建议先熟练掌握 Kruskal，它的逻辑更符合直觉！

C++ 最小生成树数据结构