土法炼钢兴趣小组的算法知识备份

最小生成树：Kruskal 与 Prim 的工程权衡

2026-06-05 · algorithms · #mst #kruskal #prim #union-find #boruvka #network-design

目录

一、为什么要谈最小生成树

在图论的工具箱里，最小生成树（Minimum Spanning Tree，MST）是少数几个「定义简洁、应用广泛、算法优美」三项全占的问题。给定一个连通无向加权图 G = (V, E)，MST 要求找到一棵包含所有顶点的树 T，使得 T 中所有边的权重之和最小。

这个问题的实际背景随处可见：城市之间铺设光缆、电路板上的布线、聚类分析中的单链接聚类、甚至游戏地图的程序化生成。它的理论地位同样重要——MST 是贪心策略的经典成功案例，也是理解割、环、拟阵等概念的入口。

本文会完整覆盖三种经典 MST 算法：Kruskal、Prim 和 Boruvka，给出可编译运行的 C 实现，讨论它们各自适合的工程场景，最后延伸到 Steiner 树、可靠性设计等高级话题。

一个核心观点贯穿全文：MST 算法的选择，本质上是边排序和优先队列之间的权衡。 理解了这一点，面对具体工程需求时就不会选错算法。

二、基本定义与性质

2.1 生成树

对于连通图 G = (V, E)，一棵生成树是 G 的一个子图 T = (V, E_T)，满足：

  1. T 包含 G 的所有顶点；
  2. T 是一棵树（连通且无环）；
  3. |E_T| = |V| - 1。

2.2 最小生成树

在边带权的连通图中，权重之和最小的生成树称为最小生成树。注意 MST 不一定唯一——当存在权重相同的边时，可能有多棵不同的 MST，但它们的总权重一定相同。

2.3 MST 的基本性质

环性质（Cycle Property）：对于图中任意一个环，环上权重严格最大的边不属于任何 MST。

割性质（Cut Property）：对于图的任意一个割 (S, V)，跨越该割的权重严格最小的边必属于某棵 MST。

这两条性质是所有 MST 算法正确性的基石。Kruskal 算法利用的是割性质（每次加入的最小边恰好连接两个不同连通分量），Prim 算法也利用割性质（每次选择连接已选集合与未选集合的最小边），而环性质则给出了「哪些边一定不在 MST 中」的判据。

2.4 唯一性条件

如果图中所有边的权重互不相同，则 MST 唯一。证明很简单：假设存在两棵不同的 MST T1 和 T2，取 T1 中不在 T2 里的边 e，把 e 加入 T2 形成环，环上必有另一条跨越同一割的边 e’，由割性质和权重互异性，e 和 e’ 的大小关系确定，从而导出矛盾。

三、割性质的证明

割性质是整篇文章的理论根基，值得完整证明一次。

定理（Cut Property）：设 G = (V, E, w) 是连通加权图，(S, V) 是 G 的任意一个割，e 是跨越该割的唯一最小权边。则 e 属于 G 的每一棵 MST。

证明：

设 T 是 G 的一棵 MST，假设 e = (u, v) 不在 T 中，其中 u 属于 S，v 属于 V。

  1. 因为 T 是生成树，T 中存在一条从 u 到 v 的唯一路径 P。
  2. 路径 P 从 S 出发到达 V，必然至少经过一条跨越割 (S, V) 的边，设这条边为 e’ = (x, y)。
  3. 由题设 e 是跨越该割的唯一最小权边，故 w(e) < w(e’)。
  4. 构造新树 T’ = T - {e’} + {e}。删除 e’ 后 T 断成两个连通分量，加入 e 重新连通，因此 T’ 仍然是生成树。
  5. w(T’) = w(T) - w(e’) + w(e) < w(T)，与 T 是 MST 矛盾。

故 e 必在 T 中。当跨越割的最小权边不唯一时，结论弱化为「至少属于某棵 MST」。

下图展示了割性质的直觉：

割性质示意图

图中紫色虚线表示割 C，将顶点分为蓝色集合 S 和绿色集合 V。跨越割的边中，橙色粗边（权重 1）是轻边，它必然出现在 MST 中。灰色虚线是其余的 crossing edges。

四、Kruskal 算法与 Union-Find

4.1 算法思想

Kruskal 算法是最直觉的贪心策略：

  1. 将所有边按权重从小到大排序；
  2. 依次考察每条边，如果这条边连接的两个顶点不在同一连通分量中，就将这条边加入 MST；
  3. 重复直到 MST 包含 V-1 条边。

正确性直接来自割性质：当我们选择一条连接两个不同分量的边时，这条边是跨越「这两个分量构成的割」的最小边（因为更小的边要么已被选入，要么连接的是同一分量内的顶点）。

4.2 Union-Find 数据结构

判断「两个顶点是否在同一连通分量」以及「合并两个分量」，正是 Union-Find（并查集）的经典用途。

Union-Find 支持两个操作：

朴素实现下，这两个操作的时间复杂度可能退化到 O(n)。加上两个优化后，均摊复杂度降到 O(alpha(n))，其中 alpha 是反阿克曼函数，在实际中可以认为是常数。

4.3 路径压缩（Path Compression）

在 Find 操作中，将查找路径上的所有节点直接挂到根节点下：

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

这使得后续对同一路径上节点的 Find 操作接近 O(1)。

4.4 按秩合并（Union by Rank）

合并时，将较矮的树挂到较高的树下面，避免树的高度过快增长：

void union_sets(int parent[], int rank[], int x, int y) {
    int rx = find(parent, x);
    int ry = find(parent, y);
    if (rx == ry) return;
    if (rank[rx] < rank[ry]) {
        parent[rx] = ry;
    } else if (rank[rx] > rank[ry]) {
        parent[ry] = rx;
    } else {
        parent[ry] = rx;
        rank[rx]++;
    }
}

4.5 Kruskal 的时间复杂度

对于稀疏图（E 接近 V），这几乎是线性的。对于稠密图（E 接近 V^2），排序的开销变大，此时 Prim 可能更优。

五、Prim 算法与优先队列

5.1 算法思想

Prim 算法从任意一个起点开始，维护一个「已选集合」S，每次从 S 到 V的所有边中选择权重最小的一条，将对应的顶点加入 S，直到所有顶点都被选入。

这也是割性质的直接应用：每一步选择的都是跨越割 (S, V) 的最小边。

5.2 基于二叉堆的实现

用最小堆维护每个未选顶点到已选集合的最小边权：

  1. 初始化：将起点的 key 设为 0，其余顶点设为正无穷，全部入堆；
  2. 每次取出堆顶（key 最小的顶点 u），将 u 加入 MST；
  3. 对 u 的每个邻居 v，如果 v 未被选且 w(u,v) < key[v]，则更新 key[v] 并在堆中执行 decrease-key。

时间复杂度：

对于稠密图，E = O(V^2)，此时用邻接矩阵 + 线性扫描更好，复杂度为 O(V^2)。

5.3 Fibonacci 堆优化

Fibonacci 堆的 decrease-key 是均摊 O(1)，extract-min 是均摊 O(log V)：

这是 Prim 算法的理论最优复杂度。当 E = omega(V log V) 时（即图足够稠密），这比 Kruskal 的 O(E log E) 更好。

不过实际工程中 Fibonacci 堆的常数因子很大，缓存不友好，实现也复杂。除非 V 超过百万级别且图确实稠密，否则二叉堆甚至配对堆（pairing heap）通常是更实际的选择。

5.4 Prim vs Dijkstra

Prim 和 Dijkstra 的代码结构几乎一模一样，区别仅在松弛条件：

这种相似性不是巧合。两者都是「从已探索区域向外扩展」的贪心策略，只是优化目标不同：Dijkstra 最小化路径长度，Prim 最小化连接代价。

六、Boruvka 算法

6.1 历史背景

Boruvka 算法（1926 年）是已知最早的 MST 算法，比 Kruskal（1956）和 Prim（1957）都早了三十年。它由捷克数学家 Otakar Boruvka 提出，最初动机是为摩拉维亚地区设计最经济的电力网络。

6.2 算法思想

  1. 初始时每个顶点自成一个连通分量；
  2. 每一轮（phase）中，每个连通分量独立地找出连接自己到其他分量的最小权边；
  3. 将所有找到的边加入 MST，合并对应的分量；
  4. 重复直到只剩一个分量。

6.3 复杂度分析

每一轮至少将分量数减半（最差情况下两个分量合并成一个），因此最多 O(log V) 轮。每一轮需要扫描所有边找最小，耗时 O(E)。

总计：O(E log V)。

6.4 并行友好性

Boruvka 的独特优势在于天然适合并行计算。每一轮中，各连通分量寻找最小外边的操作是完全独立的，可以并行执行。这使得 Boruvka 成为 GPU 上和分布式环境中 MST 计算的首选框架。

实际上，许多现代并行 MST 算法都是以 Boruvka 为基础，在每一轮中用并行原语（如 parallel reduce）来寻找各分量的最小外边。

6.5 与其他算法的混合

一个常见的工程技巧是「Boruvka + Kruskal 混合」：先跑几轮 Boruvka 大幅减少分量数，然后切换到 Kruskal 处理剩余的少量分量。这在某些场景下比单独使用任何一种算法都快。

七、Union-Find 的均摊分析

Union-Find 的均摊复杂度 O(alpha(n)) 是算法分析中的一个经典结果，这里给出证明的核心思路。

7.1 阿克曼函数与反阿克曼函数

阿克曼函数 A(k, j) 的定义：

A(0, j) = j + 1
A(k, 0) = A(k-1, 1)                      当 k >= 1
A(k, j) = A(k-1, A(k, j-1))              当 k >= 1, j >= 1

它的增长速度极快：

反阿克曼函数 alpha(n) = min{k : A(k, 1) >= n}。对于宇宙中原子数量级别的 n（约 10^80），alpha(n) <= 4。因此在任何实际应用中，alpha(n) 都不超过 4，可以视为常数。

7.2 证明梗概（Tarjan-van Leeuwen 分析）

将节点按 rank 分成若干块（block），第 i 块包含 rank 在 [A(i-1,1)+1, A(i,1)] 范围内的节点。关键观察：

  1. 同块收缩：路径压缩使得一个节点的父指针不断上移，如果父节点和自己在同一块内，则该节点的「块内指针跳数」严格递减，最终指向块外节点。

  2. 块的数量：由于反阿克曼函数的定义，rank 最多到 log n，而块的数量恰好是 alpha(n)。

  3. 势能论证：定义势能函数 Phi，对每个节点 x 记录它在块内还能跳几次。每次路径压缩要么跨块（对应势能不变但块号推进），要么块内跳（势能下降 1）。

  4. 均摊：m 次操作的总代价 = 实际代价 + 势能变化。块间跳数不超过 m * alpha(n)，块内跳的总势能下降不超过 n * alpha(n)。

最终得到 m 次操作（混合 Find 和 Union）的总时间为 O(m * alpha(n))，即单次操作均摊 O(alpha(n))。

7.3 工程启示

这个分析告诉我们：路径压缩和按秩合并缺一不可。

实际测试中，Union-Find 操作的平均耗时通常不超过两到三次指针跳转，比理论分析的上界还要好得多。

八、完整 C 实现

8.1 Kruskal 算法实现

以下是一个完整的、可编译运行的 Kruskal 算法 C 实现，包含 Union-Find 数据结构：

/* kruskal.c — Kruskal's MST with Union-Find
 * 编译: gcc -O2 -o kruskal kruskal.c
 * 运行: ./kruskal < input.txt
 *
 * 输入格式:
 *   第一行: V E
 *   接下来 E 行: u v w （顶点从 0 开始编号）
 *
 * 输出: MST 的边和总权重
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_V 100000
#define MAX_E 500000

/* ========== Union-Find ========== */

typedef struct {
    int parent[MAX_V];
    int rank[MAX_V];
    int n;
} UnionFind;

void uf_init(UnionFind *uf, int n) {
    uf->n = n;
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i;
        uf->rank[i] = 0;
    }
}

int uf_find(UnionFind *uf, int x) {
    if (uf->parent[x] != x)
        uf->parent[x] = uf_find(uf, uf->parent[x]);  /* 路径压缩 */
    return uf->parent[x];
}

/* 按秩合并，返回 1 表示成功合并，0 表示已在同一集合 */
int uf_union(UnionFind *uf, int x, int y) {
    int rx = uf_find(uf, x);
    int ry = uf_find(uf, y);
    if (rx == ry) return 0;

    if (uf->rank[rx] < uf->rank[ry]) {
        uf->parent[rx] = ry;
    } else if (uf->rank[rx] > uf->rank[ry]) {
        uf->parent[ry] = rx;
    } else {
        uf->parent[ry] = rx;
        uf->rank[rx]++;
    }
    return 1;
}

/* ========== Edge & Sorting ========== */

typedef struct {
    int u, v;
    long long w;
} Edge;

Edge edges[MAX_E];
Edge mst_edges[MAX_V];

int cmp_edge(const void *a, const void *b) {
    long long diff = ((Edge *)a)->w - ((Edge *)b)->w;
    if (diff < 0) return -1;
    if (diff > 0) return  1;
    return 0;
}

/* ========== Kruskal ========== */

long long kruskal(int V, int E, int *mst_count) {
    qsort(edges, E, sizeof(Edge), cmp_edge);

    UnionFind uf;
    uf_init(&uf, V);

    long long total_weight = 0;
    *mst_count = 0;

    for (int i = 0; i < E && *mst_count < V - 1; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        long long w = edges[i].w;

        if (uf_union(&uf, u, v)) {
            mst_edges[*mst_count] = edges[i];
            (*mst_count)++;
            total_weight += w;
        }
    }
    return total_weight;
}

/* ========== Main ========== */

int main(void) {
    int V, E;
    if (scanf("%d %d", &V, &E) != 2) {
        fprintf(stderr, "错误: 无法读取 V 和 E\n");
        return 1;
    }

    if (V > MAX_V || E > MAX_E) {
        fprintf(stderr, "错误: 超出最大限制 V=%d E=%d\n", MAX_V, MAX_E);
        return 1;
    }

    for (int i = 0; i < E; i++) {
        if (scanf("%d %d %lld", &edges[i].u, &edges[i].v, &edges[i].w) != 3) {
            fprintf(stderr, "错误: 读取第 %d 条边失败\n", i);
            return 1;
        }
    }

    int mst_count = 0;
    long long total = kruskal(V, E, &mst_count);

    if (mst_count < V - 1) {
        printf("图不连通，无法生成 MST\n");
        printf("已找到 %d 条边（需要 %d 条）\n", mst_count, V - 1);
        return 1;
    }

    printf("MST 总权重: %lld\n", total);
    printf("MST 边列表:\n");
    for (int i = 0; i < mst_count; i++) {
        printf("  %d -- %d  (权重 %lld)\n",
               mst_edges[i].u, mst_edges[i].v, mst_edges[i].w);
    }

    return 0;
}

代码要点：

8.2 Prim 算法实现

以下是基于二叉堆的 Prim 算法完整实现，使用邻接表存图：

/* prim.c — Prim's MST with binary heap
 * 编译: gcc -O2 -o prim prim.c
 * 运行: ./prim < input.txt
 *
 * 输入格式与 kruskal.c 相同
 */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#define MAX_V 100000
#define MAX_E 500000
#define INF   LLONG_MAX

/* ========== 邻接表 ========== */

typedef struct AdjNode {
    int to;
    long long w;
    int next;
} AdjNode;

AdjNode adj[MAX_E * 2];  /* 无向图，每条边存两次 */
int head[MAX_V];
int adj_cnt;

void adj_init(int V) {
    adj_cnt = 0;
    memset(head, -1, sizeof(int) * V);
}

void adj_add(int u, int v, long long w) {
    adj[adj_cnt].to = v;
    adj[adj_cnt].w  = w;
    adj[adj_cnt].next = head[u];
    head[u] = adj_cnt++;
}

/* ========== 最小堆 ========== */

typedef struct {
    int    vertex;
    long long key;
} HeapNode;

typedef struct {
    HeapNode data[MAX_V + 1];
    int pos[MAX_V];    /* pos[v] = v 在堆数组中的下标 */
    int size;
} MinHeap;

void heap_init(MinHeap *h) {
    h->size = 0;
    memset(h->pos, -1, sizeof(h->pos));
}

void heap_swap(MinHeap *h, int i, int j) {
    HeapNode tmp = h->data[i];
    h->data[i] = h->data[j];
    h->data[j] = tmp;
    h->pos[h->data[i].vertex] = i;
    h->pos[h->data[j].vertex] = j;
}

void heap_sift_up(MinHeap *h, int i) {
    while (i > 0) {
        int parent = (i - 1) / 2;
        if (h->data[parent].key <= h->data[i].key) break;
        heap_swap(h, i, parent);
        i = parent;
    }
}

void heap_sift_down(MinHeap *h, int i) {
    int n = h->size;
    while (2 * i + 1 < n) {
        int child = 2 * i + 1;
        if (child + 1 < n && h->data[child + 1].key < h->data[child].key)
            child++;
        if (h->data[i].key <= h->data[child].key) break;
        heap_swap(h, i, child);
        i = child;
    }
}

void heap_insert(MinHeap *h, int v, long long key) {
    int i = h->size++;
    h->data[i].vertex = v;
    h->data[i].key    = key;
    h->pos[v] = i;
    heap_sift_up(h, i);
}

HeapNode heap_extract_min(MinHeap *h) {
    HeapNode min_node = h->data[0];
    h->pos[min_node.vertex] = -1;
    h->size--;
    if (h->size > 0) {
        h->data[0] = h->data[h->size];
        h->pos[h->data[0].vertex] = 0;
        heap_sift_down(h, 0);
    }
    return min_node;
}

void heap_decrease_key(MinHeap *h, int v, long long new_key) {
    int i = h->pos[v];
    if (i < 0 || h->data[i].key <= new_key) return;
    h->data[i].key = new_key;
    heap_sift_up(h, i);
}

/* ========== Prim ========== */

long long key[MAX_V];       /* 到已选集合的最小边权 */
int       parent[MAX_V];    /* MST 中的父节点 */
int       in_mst[MAX_V];    /* 是否已加入 MST */

long long prim(int V, int src) {
    MinHeap heap;
    heap_init(&heap);

    for (int i = 0; i < V; i++) {
        key[i]    = INF;
        parent[i] = -1;
        in_mst[i] = 0;
    }
    key[src] = 0;

    for (int i = 0; i < V; i++)
        heap_insert(&heap, i, key[i]);

    long long total_weight = 0;
    int mst_count = 0;

    while (heap.size > 0) {
        HeapNode min_node = heap_extract_min(&heap);
        int u = min_node.vertex;

        if (min_node.key == INF) break;  /* 不连通 */

        in_mst[u] = 1;
        total_weight += min_node.key;
        mst_count++;

        /* 松弛邻居 */
        for (int e = head[u]; e != -1; e = adj[e].next) {
            int v = adj[e].to;
            long long w = adj[e].w;
            if (!in_mst[v] && w < key[v]) {
                key[v] = w;
                parent[v] = u;
                heap_decrease_key(&heap, v, w);
            }
        }
    }

    if (mst_count < V) return -1;  /* 图不连通 */
    return total_weight;
}

/* ========== Main ========== */

int main(void) {
    int V, E;
    if (scanf("%d %d", &V, &E) != 2) {
        fprintf(stderr, "错误: 无法读取 V 和 E\n");
        return 1;
    }

    adj_init(V);

    for (int i = 0; i < E; i++) {
        int u, v;
        long long w;
        if (scanf("%d %d %lld", &u, &v, &w) != 3) {
            fprintf(stderr, "错误: 读取第 %d 条边失败\n", i);
            return 1;
        }
        adj_add(u, v, w);
        adj_add(v, u, w);
    }

    long long total = prim(V, 0);

    if (total < 0) {
        printf("图不连通，无法生成 MST\n");
        return 1;
    }

    printf("MST 总权重: %lld\n", total);
    printf("MST 边列表:\n");
    for (int i = 0; i < V; i++) {
        if (parent[i] != -1) {
            printf("  %d -- %d  (权重 %lld)\n", parent[i], i, key[i]);
        }
    }

    return 0;
}

代码要点：

九、算法对比：何时用哪个

9.1 理论复杂度对比

算法 时间复杂度 空间复杂度 数据结构
Kruskal O(E log E) O(V + E) Union-Find
Prim（二叉堆） O((V + E) log V) O(V + E) 二叉堆 + 邻接表
Prim（Fibonacci 堆） O(E + V log V) O(V + E) Fibonacci 堆 + 邻接表
Prim（邻接矩阵） O(V^2) O(V^2) 数组
Boruvka O(E log V) O(V + E) Union-Find

9.2 工程选择指南

稀疏图（E 接近 V）：Kruskal 最优。排序 O(E log E) 接近 O(V log V)，Union-Find 操作几乎线性。代码也最简单。

稠密图（E 接近 V^2）：Prim + 邻接矩阵（O(V^2)）最优。此时 Kruskal 的 O(E log E) = O(V^2 log V)，明显更慢。

中等密度图：Prim + 二叉堆通常表现最好。O((V + E) log V) 在大多数实际图上优于 Kruskal。

并行场景：Boruvka 首选。可以利用多核或 GPU 并行计算各分量的最小外边。

边已排序：如果输入的边已经排好序，Kruskal 的瓶颈消失，直接降为 O(E * alpha(V))，几乎线性。

动态图（增量）：如果边是逐个到达的，可以用在线版 Kruskal（维护当前 MST 森林）。

9.3 实测经验

在我的实际项目中，对于 V < 10^5、E < 10^6 的图，Kruskal 和 Prim（二叉堆）的性能差距通常在 20% 以内，远不如理论分析暗示的那么大。瓶颈往往在 I/O 和内存访问模式上，而不是算法本身。

我的个人选择策略：默认用 Kruskal（代码短、不易出错），除非图确实稠密或者需要在线处理。竞赛场景下 Kruskal 几乎是首选，因为 Union-Find 的板子大家都背得滚瓜烂熟。

十、工程陷阱与注意事项

在实际工程中使用 MST 算法时，有一些经典的坑值得专门列出来。

10.1 常见陷阱一览

陷阱 症状 解决方案
边权溢出 排序或求和时结果错误 用 long long 存边权和总权重
浮点边权比较 MST 结果不稳定 用整数化（乘以精度因子）或容差比较
自环 Kruskal 多加了无用边 预处理时过滤 u == v 的边
平行边 正确性不受影响但浪费时间 可选择性地保留最小权平行边
图不连通 算法输出不完整的树 检查 MST 边数是否等于 V-1
Union-Find 未初始化 合并结果错误 确保 parent[i] = i 的初始化
堆中的过期条目 Prim 用懒删除堆时重复处理 extract 后检查 in_mst 标记
负权边 MST 算法正确处理负权 不需要特殊处理（与最短路不同）
边权相同时的非确定性 不同运行得到不同 MST 如果需要确定性，对权重相同的边再按端点排序
大规模图的栈溢出 递归路径压缩 改用迭代版 Find（两遍遍历）

10.2 迭代版路径压缩

当 V 很大（超过 10^5 级别）时，递归版 uf_find 可能导致栈溢出。以下是迭代版本：

int uf_find_iter(UnionFind *uf, int x) {
    /* 第一遍：找到根 */
    int root = x;
    while (uf->parent[root] != root)
        root = uf->parent[root];

    /* 第二遍：路径压缩 */
    while (uf->parent[x] != root) {
        int next = uf->parent[x];
        uf->parent[x] = root;
        x = next;
    }
    return root;
}

10.3 Prim 的懒删除堆变体

如果不想实现 decrease_key（确实比较麻烦），可以用「懒删除」策略：不更新堆中已有的条目，而是直接插入一个新的更小的条目。取出时检查是否已在 MST 中：

/* 懒删除版 Prim 的核心循环（伪代码风格的 C） */
while (heap.size > 0) {
    HeapNode node = heap_extract_min(&heap);
    if (in_mst[node.vertex]) continue;  /* 跳过过期条目 */
    in_mst[node.vertex] = 1;
    total_weight += node.key;
    /* 松弛邻居，直接 insert 新条目 */
    for (each neighbor v of node.vertex) {
        if (!in_mst[v] && w < key[v]) {
            key[v] = w;
            heap_insert(&heap, v, w);  /* 不删旧的，直接插新的 */
        }
    }
}

这种方法实现简单，但堆的大小可能膨胀到 O(E)，空间和时间常数都会变大。竞赛中常用，工程中看情况。

10.4 浮点权重的处理

很多实际问题（如欧几里得 MST）中边权是浮点数。此时有两个选择：

  1. 整数化：如果精度允许，将所有权重乘以 10^k 转为整数；
  2. 容差比较：排序时用 fabs(a - b) < eps 判断相等，但这会破坏排序的传递性，需要小心处理。

我的建议是尽量整数化。浮点比较是无底洞，除非你确切知道自己在做什么。

十一、应用场景与扩展问题

11.1 网络线缆布局

MST 最经典的应用就是网络布线：给定 n 个节点（数据中心、交换机、办公室），节点之间的布线成本已知，求最小成本的连通布线方案。

这正是 Boruvka 当年解决的问题——只不过那时连接的是变电站而非服务器。

实际布线中还要考虑可靠性（单点故障问题），这引出了下面的 Suurballe 算法。

11.2 聚类分析（单链接聚类）

单链接聚类（Single-Linkage Clustering）与 MST 有着精确的对应关系：

  1. 对数据点构建完全图，边权为点对之间的距离；
  2. 计算 MST；
  3. 删除 MST 中权重最大的 k-1 条边，得到 k 个聚类。

这等价于：MST 的构建过程就是单链接层次聚类的过程。Kruskal 算法按边权从小到大合并，每次合并对应层次聚类树中的一次合并操作。

这种方法的优势是能发现任意形状的聚类（不像 k-means 倾向于球形聚类），劣势是对噪声敏感。

11.3 Suurballe 算法与网络可靠性

在实际网络设计中，仅有 MST 是不够的——任何一条边的故障都会导致网络分裂。Suurballe 算法寻找两条边不相交的最短路径，可以用来增强网络的可靠性。

具体做法：在 MST 的基础上，为关键节点对找到备份路径，确保任意单边故障不会导致断连。这本质上是求最小权的 2-边连通子图，是一个比 MST 更难但实际中非常重要的问题。

11.4 Steiner 树问题

Steiner 树问题是 MST 的一个自然推广：给定图 G 和一个顶点子集 S（称为「终端」），找到连接 S 中所有顶点的最小权子树。与 MST 不同的是，Steiner 树允许使用不在 S 中的顶点（称为 Steiner 点）作为中继。

关键区别：

Steiner 树问题是 NP-hard 的。证明的核心思路是从集合覆盖（Set Cover）或精确覆盖（Exact Cover）归约。这意味着除非 P = NP，不存在多项式时间的精确算法。

实际中常用的近似方法：

  1. MST 近似：对终端集合 S 构建完全图（边权为原图中两点间最短路），求这个完全图的 MST，再映射回原图。近似比为 2 - 2/|S|。
  2. Dreyfus-Wagner 动态规划：O(3^|S| * V + 2^|S| * V^2)，当 |S| 较小时可用。
  3. 迭代优化：基于局部搜索的启发式方法，实际效果往往很好。

11.5 欧几里得 MST

当顶点是平面上的点、边权是欧几里得距离时，可以利用几何性质加速。关键事实：欧几里得 MST 是 Delaunay 三角剖分的子图。因此可以：

  1. 先算 Delaunay 三角剖分：O(V log V)；
  2. 在三角剖分的边上跑 Kruskal：边数 O(V)，排序 O(V log V)。

总复杂度 O(V log V)，比朴素的 O(V^2 log V)（对完全图跑 Kruskal）好得多。

11.6 最小瓶颈路径

MST 还有一个很好的性质：图中任意两点间的最小瓶颈路径（minimax path）恰好就是 MST 上这两点间的路径。

所谓最小瓶颈路径，是使得路径上最大边权最小的路径。这在网络带宽分析中很有用——如果边权表示带宽限制（取倒数变成最小化），MST 上的路径就是带宽最大的路径。

十二、个人思考与工程哲学

12.1 算法选择的本质

回到文章开头的论点：MST 算法的选择，本质上是边排序和优先队列之间的权衡。

Kruskal 说：「让我把所有边排好序，然后贪心地选。」这是一种全局视角。

Prim 说：「让我从一个点开始，逐步扩展，用优先队列维护边界。」这是一种局部视角。

两者殊途同归，但适合的场景不同。这种「全局排序 vs 局部优先队列」的对偶性在算法设计中反复出现——比较 Dijkstra（优先队列）和 Bellman-Ford（全局松弛）也能看到类似的味道。

12.2 理论与实践的鸿沟

Fibonacci 堆让 Prim 达到了 O(E + V log V) 的理论最优，但在实际中几乎没人用。原因很简单：

  1. 常数因子太大，在常见规模下反而比二叉堆慢；
  2. 实现复杂度高，容易出 bug；
  3. 缓存不友好，在现代 CPU 上表现不佳。

这教会我们一个道理：O 记号隐藏的常数在工程中可能比渐近量级更重要。 一个 O(n log n) 但缓存友好、SIMD 优化的算法，在 n < 10^7 的范围内轻松击败 O(n) 但缓存不友好的算法。

类似的例子还有：跳表（理论优雅，实际不如红黑树）、van Emde Boas 树（理论 O(log log n)，实际不如 std::set）。

12.3 Union-Find 的普适性

Union-Find 是我最喜欢的数据结构之一。它的设计哲学很简洁：用两个简单的启发式（路径压缩 + 按秩合并）就把一个 O(log n) 的数据结构推到了 O(alpha(n))，接近理论下界。

而且它的应用范围远超 MST：

如果让我推荐一个「投入产出比最高的数据结构」，Union-Find 一定在前三名。

12.4 关于 Boruvka 的复兴

Boruvka 算法在很长时间里被教科书冷落，但随着并行计算的普及，它正在经历复兴。在 GPU 编程中，Boruvka 的每一轮都可以高效并行化——每个线程块负责一个连通分量，用 atomicMin 找最小外边。

我在一个网络拓扑分析项目中测试过 GPU 版 Boruvka，对于 10^7 级别的边数，比 CPU 上的 Kruskal 快了约 15 倍。当然，这包含了数据传输的开销——如果数据已经在 GPU 上（比如图计算流水线的中间结果），加速比会更大。

12.5 写给初学者

如果你刚开始学 MST，我的建议是：

  1. 先理解割性质，它是一切 MST 算法的理论根基；
  2. 先写 Kruskal，代码短、好调试，Union-Find 是必须掌握的基本功；
  3. 再写 Prim，感受「和 Dijkstra 只差一行」的优雅；
  4. 最后了解 Boruvka，体会「古老算法在新时代焕发生机」的趣味。

MST 问题本身不难，但它串联起来的知识图谱——贪心、拟阵、并查集、优先队列、均摊分析、NP-hard 归约——构成了算法学习中最有价值的一条线索。顺着这条线深挖下去，你会遇到越来越多有趣的东西。

12.6 延伸阅读建议

关于 MST 的理论深度，推荐以下材料：

上一篇: Bellman-Ford 与路由协议 下一篇: Tarjan 算法族 相关阅读: - Dijkstra 与 A* - 网络流与二分匹配

By .