图◆最小生成树 | Prim、Kruskal、破圈法

发现了一个梳理的比较系统，该有的都有，而且描述清楚的博主hhhh。以下内容中，有些描述来自他的博客——
Prim原理O(n^2)
Kruskal原理O(eloge)
另外，刷王道大题的时候看到了另一种求MST的方法——破圈法。

最小生成树

问题：如何用最小的“代价”用N-1条边连接N个点

答：最小 总边权重 生成树

• 前提：无向连通图
• Minimum Spanning Tree, MST
• 最小生成树存在当且仅当图是连通的，可能不唯一。
• 树：无环，连通。
• 连通图的生成树：包含图的所有顶点

Prim算法

适合稠密图，O(V^2)，V为顶点数。

思想

贪心，每次只添加从外部连接到该子树的所有边中的最短边即可。

1. 从某个顶点开始（看成只有一个结点的子生成树）
2. 在当前生成树到外部的相邻边中，选一条权重最小的边，将这条边和边的另一个顶点并入子生成树中（生成树就长大了一点）
   继续，直到所有的顶点都被并入了生成树。

类比Dijkstra来看，就是选距离MST最近的外部顶点加入MST。

实现

• 用inMST布尔数组来记录某顶点是否已经在当前的生成树中
• dist数组记录顶点到MST的距离
  int new_d = graph[curr][j]; //注意
dist[j] = min(dist[j], new_d);

#include <cstdio>
#include <algorithm>

#define MAXN 1001
#define INF 0x3fffffff
using namespace std;
int graph[MAXN][MAXN], n_vertex, m_edge, total_weight = 0;

void Prim(int start) {
    int dist[MAXN];
    fill(dist, dist + MAXN, INF);
    bool inMST[MAXN] = {false};
    dist[start] = 0;
    int pre = -1;
    for (int i = 0; i < n_vertex; ++i) { // loop: n
        int min_dist = INF, curr = -1;
        for (int j = 0; j < n_vertex; ++j) {
            if (!inMST[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                curr = j;
            }
        }
        if (curr == -1) {
            printf("NOT CONNECTED\n");
            return;
        }
        inMST[curr] = true;
        total_weight += dist[curr];
        for (int j = 0; j < n_vertex; ++j) {
            if (!inMST[j] && graph[curr][j] != INF) {
                int new_d = graph[curr][j]; //注意
                dist[j] = min(dist[j], new_d);
            }
        }
    }
}

// premise: 连通图
int main() {
    scanf("%d%d", &n_vertex, &m_edge);
    int v1, v2, weight;
    fill(graph[0], graph[0] + MAXN * MAXN, INF);
    for (int i = 0; i < m_edge; ++i) {
        scanf("%d%d%d", &v1, &v2, &weight);
        graph[v1][v2] = graph[v2][v1] = weight;
    }

    // 不妨从第一个结点开始（结点下标从0开始）
    Prim(0);
    printf("MST total weight: %d\n", total_weight);
    return 0;
}

Kruskal算法

适用于稀疏图，复杂度 O（E log E），E为边数。

思想

为使生成树上边的权值之和达到最小，应使生成树中每一条边的权值尽可能地小。

• 每一轮从边集中选一条权值最小的边，将其两个顶点并入到生成树中，直到全部顶点都在生成树中。
  • 对所选边的要求：并入不会形成环，若成环，选下一个权值最小边。
  • 判断并入是否成环：并查集(不相交集合)
    ⚠️用一个visited布尔数组来确保仅加入一次是不够的，例如：已经加入了0---1，2---4，再加入2---1，连接两个分支，就会误判= =，使用并查集是必要的！！！

实现

边集 set<pair<int, pair<int, int >>> edges 自带排序。

#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>

#define MAXN 1001
using namespace std;
set<pair<int, pair<int, int >>> edges; //set自带排序 嘻嘻
vector<pair<int, pair<int, int >>> MST;
int uf[MAXN];

int _find(int me) {
    return uf[me] < 0 ? me : uf[me] = _find(uf[me]);
}

void _union(int a, int b) {
    a = _find(a);
    b = _find(b);
    if (a != b) {
        int mm = min(a, b), MM = max(a, b);
        uf[mm] += uf[MM];
        uf[MM] = mm;
    }
}

// premise: 连通图
int main() {
    int n_vertex, m_edge;
    scanf("%d%d", &n_vertex, &m_edge);
    int v1, v2, weight;
    fill(uf, uf + MAXN, -1);
    for (int i = 0; i < m_edge; ++i) {
        scanf("%d%d%d", &v1, &v2, &weight);
        edges.insert(make_pair(weight, make_pair(v1, v2)));
    }
    // select n_vertex-1 edge to build an MST
    int total_weight = 0;
    pair<int, pair<int, int>> temp_e;
    int va, vb;
    while (!edges.empty()) {
        temp_e = *edges.begin();
        edges.erase(edges.begin());
        va = temp_e.second.first, vb = temp_e.second.second;
        if (_find(va) != _find(vb)) {
            _union(va, vb);
            MST.emplace_back(temp_e);
            total_weight += temp_e.first;
            if (MST.size() == n_vertex - 1) break;
        }
    }
    puts("******** MST ********");
    for (auto item: MST) {
        printf("V%d ---- %d ---- V%d\n", item.second.first, item.first, item.second.second);
    }
    printf("MST total weight: %d\n", total_weight);
    return 0;
}

破圈法（前提：无向连通图）

• 策略
  找到图中的一个环，删去环上权重最大的边。重复这个过程，直到图中不存在环了。
• 正确性证明
  破圈法最终留下的一定是一棵生成树，因为连通且无环。
  关键是 证明它是总边权最小的生成树。
  将破圈法得到的树记作T。假设T不是最小生成树，那一定存在最小生成树T0。
  取T0和T的并集G'，因为两棵树“枝杈”不同，但点集都是V，所以G'中一定有环。
  按破圈法处理G'，删掉环上的最大边，那么得到的树（就是T啦）一定是从G'能得到的最小生成树，与假设矛盾，得证。