最小生成树——Kruskal 算法

按学院培养方案，大一下学期你们要学离散数学，图论是其中一部分。李梦巧老师很严格，小心挂科！

问题回顾

给定一个 $n$ 个节点 $m$ 条边的无向带权连通图，求最小生成树的边权和。

生成树：选出 $n-1$ 条边，使 $n$ 个节点全部连通且无环。

最小生成树 (MST)：在所有生成树中，边权和最小的那棵。

Kruskal 算法

贪心策略：每次选当前权值最小的边，若加入后不会形成环，就加入 MST。

为什么贪心是对的？—— MST 的割性质：对于图中任意一个割（将图分成两部分），连接这两部分的最小权边一定属于某个 MST。Kruskal 本质上就是在不断寻找切割的最小权边。

算法流程

1. 将所有边按权值从小到大排序
2. 初始化并查集，每个节点自成一派
3. 遍历排序后的边：
   • 若边的两端已连通（find 相同）→ 加入会成环，跳过
   • 否则 → 合并两端（unite），累加权值
4. 选够 $n-1$ 条边即结束

与上一题的呼应

上一题"demon的荒岛求生"学了并查集，本题恰好用上：排序 + 并查集判环 = Kruskal。数据结构就是这样一环扣一环。

复杂度

• 排序：$O(m \log m)$
• 每条边做一次并查集操作：$O(m \cdot \alpha(n)) \approx O(m)$

总体 $O(m \log m)$。

完整代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1005;
int parent[MAXN];

struct Edge {
    int a, b, w;
    bool operator<(const Edge& o) const { return w < o.w; }
};

int find(int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

bool unite(int a, int b) {
    a = find(a); b = find(b);
    if (a != b) { parent[a] = b; return true; }
    return false;
}

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

    int n, m;
    cin >> n >> m;
    vector<Edge> edges(m);
    for (int i = 0; i < m; i++)
        cin >> edges[i].a >> edges[i].b >> edges[i].w;
    sort(edges.begin(), edges.end());

    for (int i = 1; i <= n; i++) parent[i] = i;

    int ans = 0, cnt = 0;
    for (int i = 0; i < m && cnt < n - 1; i++) {
        if (unite(edges[i].a, edges[i].b)) {
            ans += edges[i].w;
            cnt++;
        }
    }
    cout << ans << '\n';
    return 0;
}

最小生成树--prim算法

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const ll N=1010;
ll n,m;
ll ret;
ll dist[N];
bool st[N];
vector<pair<ll,ll>>edges[N];

void prim()
{
    memset(dist,0x3f3f,sizeof dist);
    dist[1]=0;

    for(int i=1;i<=n;i++)
    {
        ll t=0;
        for(int j=1;j<=n;j++)
        {
            if(dist[j]<dist[t] && !st[j])
            {
                t=j;
            }
        }

        st[t]=true;
        ret+=dist[t];
        for(auto u:edges[t])
        {
            ll v=u.first;
            ll w=u.second;
            dist[v]=min(dist[v],dist[t]+w);
        }
    }
}

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

    cin>>n>>m;

    for(ll i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        edges[u].push_back({v,w});
        edges[v].push_back({u,w});
    }

    prim();
    cout<<ret<<"\n";

    return 0;
}

//ysh牛逼 //ysh牛逼 //ysh牛逼 //ysh牛逼 //ysh牛逼 //ysh牛逼 //ysh牛逼