MST-学习笔记

最小生成树（Minimum Spanning Tree, MST）是在一个加权无向图中寻找一个边的子集，使得这个子集构成的树包含图中的所有顶点，并且边的权重之和最小。

1.切分定理

切分定理是最小生成树算法的理论基础。它指出：

• 如果将图中的节点分为两部分，那么连接这两部分的最小权重的边必定属于图的最小生成树。

这个定理是Prim算法和Kruskal算法正确性的保证。

2. Kruskal算法

时间复杂度

Kruskal算法的时间复杂度主要由排序边的操作决定，为 \(O(E \log E)\)，其中 \(E\) 是图中边的数量。在边排序之后，算法需要进行并查集操作，时间复杂度为 \(O(E \alpha(V))\)，其中 \(\alpha\) 是阿克曼函数的反函数，对于所有实际的输入值几乎可以认为是常数。

核心伪代码

KRUSKAL(G):
1. A = ∅
2. 对每个顶点 v ∈ G.V:
3.     MAKE-SET(v)
4. 将 G.E 中的边按权重从小到大排序
5. for each edge (u, v) ∈ G.E ordered by increasing weight:
6.     if FIND-SET(u) ≠ FIND-SET(v):
7.         A = A ∪ {(u, v)}
8.         UNION(u, v)
9. return A

示例代码

#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;

const int maxn = 2005;
struct Edge {
    int x, y, z;
} e[maxn * maxn];
int fa[maxn];

int findset(int x) {
    if (x == fa[x]) return x;
    return fa[x] = findset(fa[x]);
}

bool cmp(const Edge& a, const Edge& b) {
    return a.z < b.z;
}

int main() {
    int n; scanf("%d", &n);
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            scanf("%d", &e[++cnt].z);
            e[cnt].x = i - 1;
            e[cnt].y = j;
        }
    }

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

    ll ans = 0;
    sort(e + 1, e + cnt + 1, cmp);
    int num = 0;
    for (int i = 1; i <= cnt; i++) {
        int x = e[i].x, y = e[i].y, w = e[i].z;
        int rx = findset(x), ry = findset(y);
        if (rx != ry) {
            fa[rx] = ry;
            num++;
            ans += w;
            if (num == n - 1) break;
        }
    }
    printf("%lld\n", ans);
    return 0;
}

3. Prim算法

时间复杂度

Prim算法的时间复杂度依赖于使用的数据结构。使用优先队列实现时，时间复杂度为 \(O(E \log V)\)，其中 \(V\) 是顶点数，\(E\) 是边数。

核心伪代码

PRIM(G, r):
1. for each u ∈ G.V:
2.     u.key = ∞
3.     u.parent = NIL
4. r.key = 0
5. Q = G.V
6. while Q ≠ ∅:
7.     u = EXTRACT-MIN(Q)
8.     for each v adjacent to u:
9.         if v ∈ Q and w(u, v) < v.key:
10.            v.parent = u
11.            v.key = w(u, v)

示例代码

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

typedef pair<int, int> pii; // first: weight, second: vertex

vector<vector<pii>> adj; // adjacency list

int prim(int start, int n) {
    vector<int> key(n, INT_MAX);
    vector<bool> inMST(n, false);
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    key[start] = 0;
    pq.push({0, start});

    int mst_cost = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        if (inMST[u]) continue;
        inMST[u] = true;
        mst_cost += key[u];

        for (auto &[cost, v] : adj[u]) {
            if (!inMST[v] && cost < key[v]) {
                key[v] = cost;
                pq.push({cost, v});
            }
        }
    }

    return mst_cost;
}

int main() {
    int n, m;
    cin >> n >> m;
    adj.resize(n);

    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});
    }

    int start_vertex = 0; // assuming the vertices are 0-indexed
    cout << "Cost of MST: " << prim(start_vertex, n) << endl;

    return 0;
}

这段代码使用了C++的STL容器，如 vector 和 priority_queue，来实现Prim算法。这里的 priority_queue 用于维护一个按边权重排序的顶点集合，以便每次都能从中取出当前最小边权的顶点。