前置知识和定义#

在开始学习最小生成树之前，先了解一些前置知识。

子图#

对于一张图 $G=(V,E)$ ，如果存在一张图 $H=(V',E')$ 满足 $V'\subseteq V$ 且 $E'\subseteq E$ ，则称 $H$ 是 $G$ 的一个子图。记作 $H\subseteq G$ 。

生成子图#

如果存在 $H \subseteq G$ 满足 $V'=V$ ，则称 $H$ 是 $G$ 的一个生成子图。

生成子图又称为支撑子图。

生成树#

生成树：一个无向连通图的生成子图,且同时要求是树。也即在图的边集选择了 $n-1$ 条边，将图中的所有顶点连接起来。

最小生成树#

我们定义，一个无向连通图的 最小生成树，是指这个图中边权和最小的生成树。

Kruskal 算法#

Kruskal 算法是一种常见简单的用于求最小生成树的算法。此算法的基本思想就是贪心的从小到大加入边。

算法流程#

对图中的所有边按边权从小到大排序。
从小到大枚举每一条边 $(u,v)$ ，如果 $u$ 和 $v$ 不在同一连通块中，就加入这条边，并将 $u$ 和 $v$ 所在的连通块合并。
重复步骤 2 直到加入了 $n-1$ 条边。

显然，我们需要使用并查集来维护每个点所在的连通块。那么，此算法的时间复杂度就为 $O(m\log m)$ ，其中 $m$ 是边数。

证明#

归纳法证明#

我们使用数学归纳法证明 Kruskal 算法的正确性。

基础：算法开始前，显然成立。

归纳：假设算法在加入了 $k-1$ 条边后，生成了一个最小生成树 $T$ 。我们需要证明，加入第 $k$ 条边 $(u,v)$ 后，生成的最小生成树 $T'$ 也成立。

我们可以分两种情况讨论：

如果 $(u,v)$ 不在 $T$ 中，那么 $T'$ 就是 $T$ 加上 $(u,v)$ 这条边。显然， $T'$ 是一个最小生成树。
如果 $(u,v)$ 在 $T$ 中，那么 $T'$ 就是 $T$ 去掉 $(u,v)$ 这条边，加上 $(u,v)$ 这条边的最小生成树。根据归纳假设， $T$ 是一个最小生成树，所以 $T'$ 也是一个最小生成树。

反证法#

我们使用反证法证明 Kruskal 算法的正确性。

假设 Kruskal 算法得到的生成树 $T$ 不是最小生成树，那么必然存在某个最小生成树 $T_{opt}$ ，使得 $w(T_{opt}) < w(T)$ ，其中 $w(\cdot)$ 表示生成树的边权和。

设 $e_k = (u,v)$ 是 Kruskal 算法选择的第一个不在 $T_{opt}$ 中的边（按边权从小到大排序后的第 $k$ 条边）。由于 Kruskal 算法会选择这条边，说明在加入 $e_k$ 之前， $u$ 和 $v$ 不在同一个连通块中。

现在考虑 $T_{opt} \cup \{e_k\}$ ，这个图必然包含一个环（因为 $T_{opt}$ 是生成树，加入任何边都会形成环）。这个环中至少包含一条边 $e'$ 满足 $w(e') \geq w(e_k)$ （因为 $e_k$ 是连接这两个连通块的最小权边）。

我们可以构造一个新的生成树 $T' = T_{opt} \cup \{e_k\} \setminus \{e'\}$ 。显然：

$T'$ 仍然是一个生成树（因为去除了环中的一条边）
$w(T') = w(T_{opt}) + w(e_k) - w(e') \leq w(T_{opt})$ （因为 $w(e_k) \leq w(e')$ ）

但是这与 $T_{opt}$ 是最小生成树的假设矛盾，因为我们找到了一个权值不大于 $T_{opt}$ 的生成树 $T'$ ，且 $T'$ 包含了 $e_k$ 。

通过重复这个过程，我们可以证明 Kruskal 算法得到的生成树 $T$ 必须是最小生成树，从而证明了算法的正确性。

代码实现#

1
#include <bits/stdc++.h>
2
using namespace std;
3
// #define MULTI_CASES
4
#define ll long long
5
#define int ll
6
#define endl '\n'
7
#define vi vector<int>
8
#define PII pair<int, int>
9
const int MaxN = 2e5 + 100;
10
const int INF = 1e9;
11
const int mod = 1e9 + 7;
12
int T = 1, N, M;
13
int a[MaxN];
14
// vector<PII> G1[MaxN];
15
struct edge
16
{
17
    int x, y, z;
18
} e[MaxN];
19
bool cmp(edge a, edge b)
20
{
21
    return a.z < b.z;
22
}
23
int fa[MaxN];
24
struct MST
25
{
26
    vector<int> fn;
27
    MST(int n)
28
    {
29
        for (int i = 0; i <= n; i++)
30
        {
31
            fn.push_back(i);
32
        }
33
    }
34
    int find(int x)
35
    {
36
        if (fn[x] == x)
37
        {
38
            return x;
39
        }
40
        return fn[x] = find(fn[x]);
41
    }
42
    void join(int x, int y)
43
    {
44
        int fx = find(x), fy = find(y);
45
        if (fx != fy)
46
        {
47
            fn[fx] = fy;
48
        }
49
    }
50
    void kruskal(){
51
        int cnt=0,ans=0;
52
        sort(e+1,e+M+1,cmp);
53
        for(int i=1;i<=M;i++){
54
            int u=find(e[i].x);
55
            int v=find(e[i].y);
56
            if(u==v)continue;
57
            fn[u]=v;
58
            ans+=e[i].z;
59
            cnt++;
60
            if(cnt>N-1)break;
61
        }
62
        if(cnt==N-1){
63
            cout<<ans<<endl;
64
        }
65
        else{
66
            cout<<"orz"<<endl;
67
        }
68
    }
69
};
70
inline void Solve()
71
{
72
    cin >> N >> M;
73
    MST mst(N);
74

75
    for (int i = 1; i <= M; i++)
76
    {
77
        cin >> e[i].x >> e[i].y >> e[i].z;
78
    }
79
    mst.kruskal();
80
}
81
signed main()
82
{
83
#ifdef NOI_IO
84
    freopen(".in", "r", stdin);
85
    freopen(".out", "w", stdout);
86
#endif
87
    ios::sync_with_stdio(0);
88
    cin.tie(nullptr), cout.tie(nullptr);
89
#ifdef MULTI_CASES
90
    cin >> T;
91
    while (T--)
92
#endif
93
        Solve();
94
    return 0;
95
}

Prim 算法#

Prim 算法是另一种常见的求最小生成树的算法，它的基本思想是从一个点开始，不断加点。

算法流程#

选择图中的任意一个点作为起点，将其加入生成树。
从生成树中选择一个点 $u$ ，将 $u$ 到其他所有点的边加入候选边集合。
从候选边集合中选择一条边 $(u,v)$ ，权值最小，将 $v$ 加入生成树。
重复步骤 2 和 3，直到生成树包含所有点。

优化#

如果直接暴力枚举所有边，时间复杂度是 $O(n^2)$ ，但是我们可以使用类似堆优化Dijkstra的方法，将时间复杂度优化到 $O(m\log n)$ 。

代码实现#

1
#include <bits/stdc++.h>
2
using namespace std;
3
// #define MULTI_CASES
4
#define ll long long
5
#define int ll
6
#define endl '\n'
7
#define vi vector<int>
8
#define PII pair<int, int>
9
const int MaxN = 2e5 + 100;
10
const int INF = 0x3f3f3f3f;
11
const int mod = 1e9 + 7;
12
int T = 1, N, M;
13
vector<PII> G1[MaxN];
14
int dist[MaxN];
15
bool vis[MaxN];
16
inline void Solve()
17
{
18
    cin >> N >> M;
19
    for (int i = 1; i <= M; i++)
20
    {
21
        int u, v, w;
22
        cin >> u >> v >> w;
23
        G1[u].push_back({v, w});
24
        G1[v].push_back({u, w});
25
    }
26
    priority_queue<PII, vector<PII>, greater<PII>> pq;
27
    memset(dist, 0x3f, sizeof(dist));
28
    dist[1] = 0;
29
    pq.push({0, 1});
30
    int ans = 0;
31
    while (!pq.empty())
32
    {
33
        auto [d, u] = pq.top();
34
        pq.pop();
35
        if (vis[u])
36
            continue;
37
        vis[u] = 1;
38
        ans += d;
39
        for (auto [v, w] : G1[u])
40
        {
41
            if (!vis[v] && dist[v] > w)
42
            {
43
                dist[v] = w;
44
                pq.push({w, v});
45
            }
46
        }
47
    }
48
    for (int i = 1; i <= N; ++i)
49
    {
50
        if (!vis[i])
51
        {
52
            cout << "orz" << endl;
53
            return;
54
        }
55
    }
56
    cout << ans << endl;
57
}
58
signed main()
59
{
60
#ifdef NOI_IO
61
    freopen(".in", "r", stdin);
62
    freopen(".out", "w", stdout);
63
#endif
64
    ios::sync_with_stdio(0);
65
    cin.tie(nullptr), cout.tie(nullptr);
66
#ifdef MULTI_CASES
67
    cin >> T;
68
    while (T--)
69
#endif
70
        Solve();
71
    return 0;
72
}

最小生成树学习记录

前置知识和定义#

子图#

生成子图#

生成树#

最小生成树#

Kruskal 算法#

算法流程#

证明#

归纳法证明#

反证法#

代码实现#

Prim 算法#

算法流程#

优化#

代码实现#