最小生成树

概念

一个连通无向有权图 G 的 生成树 Spanning Tree (ST) 是 G 的子图，同时也是一个连接 G 中所有节点的树。一个图 G 可以有很多的生成树，而每一个都有不同的总权重（生成树中所有边的权重之和）。

图 G 的最小生成树 Min(imum) Spanning Tree (MST) 是在所有生成树中，有着最小总权重的生成树。

注意：只有连通图才有生成树，对于非连通图，则存在生成森林。

最小生成树 (及其优化) 的问题如下定义 ：给定一个连通的无向有权图 G = (V, E), 选择 G 中所有边的一个子集，使得图仍然是连通的，但其边的总权重最小。输出要么是 G 的一个最小生成树 (G 可以有很多最小生成树) 或是其最小的权重和。

Prim 算法

该算法的基本思想是从一个结点开始，不断加点（而不是 Kruskal 算法的加边）。具体来说就是，每次要选择距离最小的一个结点，以及用新的边更新其他结点的距离。

从图 $G = V, E$ 中的某一顶点 $u_{0}$ 出发，选择与它关联的具有最小权值的边 $(u_{0}, v)$ ，将其顶点加入到生成树顶点集合 $S$ 中。
以后每一步从一个顶点在 $S$ 中，而另一个顶点不在 $S$ 中的各条边中选择权值最小的边 $(u, v)$ , 把它的顶点加入到集合 $S$ 中。如此继续下去, 直到带权图中的所有顶点都加入到生成树顶点集合 $S$ 中为止。

cpp

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

const int N = 310;
int g[N][N];
int dist[N];
bool st[N];

int n;

int prim() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;

    int res = 0;

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

        res += dist[t];
        st[t] = true;

        for (int j = 0; j < n; j++) dist[j] = min(dist[j], g[t][j]);
    }

    return res;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> g[i][j];
        }
    }

    cout << prim() << endl;

    return 0;
}

Kruskal 算法

初始时图中的每个顶点都是一个单独的 连通分量
将图中的每条边 按权值大小 从小到大排序，从权值最小的边开始，如果该边的两个顶点不在同一个连通分量中，则选入，并把这个两个连通分量合并。
重复步骤2，直到遍历完所有边。

cpp

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

const int N = 110, M = 210;

struct Edge {
    int a, b, c;

    bool operator < (const Edge& t) const {
        return c < t.c;
    }
} e[M];

int p[N];
int n, m;

int find(int x) {
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) p[i] = i;

    for (int i = 0; i < m; i++) {
        int a, b, c; cin >> a >> b >> c;
        e[i] = {a, b, c};
    }

    sort(e, e + m);

    int res = 0;
    for (int i = 0; i < m; i++) {
        int pa = find(e[i].a), pb = find(e[i].b), c = e[i].c;
        if (pa != pb) {
            p[pa] = pb;
            res += c;
        }
    }

    cout << res << endl;

    return 0;
}

最小生成树 ​

概念 ​

Prim 算法 ​

Kruskal 算法 ​

最小生成树

概念

Prim 算法

Kruskal 算法