Skip to content

最小生成树

一、定义与背景

  • 加权图：每条边关联一个权值（如距离、成本）的图。
  • 生成树：图的无环连通子图，包含所有顶点。
  • 最小生成树（MST）：权值和最小的生成树。
  • 应用：
  • 电路（顶点：元器件，边：导线，权值：长度/时间）。
  • 航空（顶点：机场，边：航线，权值：距离/费用）。
  • 电力分配、图像分析等。

二、假设与约定

  • 连通图：仅考虑连通图，非连通图生成“最小生成森林”。
  • 权值特性：
  • 不一定与距离成正比。
  • 可为 0 或负数。
  • 假设所有边权值不同（简化唯一性证明，实际算法适用等值情况）。
  • 目标：在一幅加权连通无向图中找到 MST。

三、核心原理

1. 树的基本性质
  • 添加边产生环。
  • 删除边分裂为两棵树。
2. 切分定理（Cut Property）
  • 定义：
  • 切分：将图顶点分为两个非空、不重叠的集合。
  • 横切边：连接两个集合的边。
  • 命题 J：任意切分的横切边中，权值最小的边必属于 MST。
  • 证明（反证法）：
  • 假设 MST 不含最小横切边 ( e )，加入 ( e ) 形成环。
  • 环中必有另一横切边 ( f )（权值 > ( e )）。
  • 删除 ( f )，保留 ( e )，得到更小权值的生成树，与 MST 定义矛盾。
3. 贪心算法
  • 命题 K：从灰色边开始，反复选择不产生黑色横切边的切分，将最小横切边标记为黑色，直到标记 ( V-1 ) 条边。
  • 证明：切分定理保证每次选择的边属于 MST，( V-1 ) 条边形成连通无环图，即 MST。

四、数据结构

1. 加权边（Edge）
public class Edge implements Comparable<Edge> {
    private final int v, w;     // 顶点
    private final double weight; // 权值
    public Edge(int v, int w, double weight) { this.v = v; this.w = w; this.weight = weight; }
    public double weight() { return weight; }
    public int either() { return v; }
    public int other(int vertex) { return vertex == v ? w : vertex == w ? v : throw new Exception(); }
    public int compareTo(Edge that) { return Double.compare(this.weight, that.weight); }
}
2. 加权无向图（EdgeWeightedGraph）
public class EdgeWeightedGraph {
    private final int V;           // 顶点数
    private int E;                 // 边数
    private Bag<Edge>[] adj;       // 邻接表
    public EdgeWeightedGraph(int V) {
        this.V = V; this.E = 0;
        adj = (Bag<Edge>[]) new Bag[V];
        for (int v = 0; v < V; v++) adj[v] = new Bag<>();
    }
    public void addEdge(Edge e) { int v = e.either(), w = e.other(v); adj[v].add(e); adj[w].add(e); E++; }
    public Iterable<Edge> adj(int v) { return adj[v]; }
    public Iterable<Edge> edges() {
        Bag<Edge> b = new Bag<>();
        for (int v = 0; v < V; v++) for (Edge e : adj[v]) if (e.other(v) > v) b.add(e);
        return b;
    }
}

五、算法实现

1. Prim 算法
  • 思想：从单一顶点开始，逐步扩展树，每次添加权值最小的横切边。
  • 两种实现：
  • 延时（Lazy）版本：
    • 使用优先队列保存所有横切边（含失效边）。
    • 时间：( O(E \log E) )，空间：( O(E) )。 java public class LazyPrimMST { private boolean[] marked; // MST 顶点 private Queue<Edge> mst; // MST 边 private MinPQ<Edge> pq; // 横切边 public LazyPrimMST(EdgeWeightedGraph G) { pq = new MinPQ<>(); marked = new boolean[G.V()]; mst = new Queue<>(); visit(G, 0); while (!pq.isEmpty()) { Edge e = pq.delMin(); int v = e.either(), w = e.other(v); if (marked[v] && marked[w]) continue; // 失效边 mst.enqueue(e); if (!marked[v]) visit(G, v); if (!marked[w]) visit(G, w); } } private void visit(EdgeWeightedGraph G, int v) { marked[v] = true; for (Edge e : G.adj(v)) if (!marked[e.other(v)]) pq.insert(e); } public Iterable<Edge> edges() { return mst; } }
  • 即时（Eager）版本：
    • 使用索引优先队列，仅保存每个非树顶点到树的最小边。
    • 时间：( O(E \log V) )，空间：( O(V) )。 java public class PrimMST { private Edge[] edgeTo; // 到树最近的边 private double[] distTo; // 边的权值 private boolean[] marked; // MST 顶点 private IndexMinPQ<Double> pq; // 有效横切边 public PrimMST(EdgeWeightedGraph G) { edgeTo = new Edge[G.V()]; distTo = new double[G.V()]; marked = new boolean[G.V()]; pq = new IndexMinPQ<>(G.V()); for (int v = 0; v < G.V(); v++) distTo[v] = Double.POSITIVE_INFINITY; distTo[0] = 0.0; pq.insert(0, 0.0); while (!pq.isEmpty()) visit(G, pq.delMin()); } private void visit(EdgeWeightedGraph G, int v) { marked[v] = true; for (Edge e : G.adj(v)) { int w = e.other(v); if (marked[w]) continue; if (e.weight() < distTo[w]) { edgeTo[w] = e; distTo[w] = e.weight(); if (pq.contains(w)) pq.changeKey(w, distTo[w]); else pq.insert(w, distTo[w]); } } } }
2. Kruskal 算法
  • 思想：按边权值从小到大处理，加入不形成环的边，直到 ( V-1 ) 条边。
  • 实现：
  • 使用优先队列排序边，Union-Find 判断环。
  • 时间：( O(E \log E) )，空间：( O(E) )。 java public class KruskalMST { private Queue<Edge> mst; public KruskalMST(EdgeWeightedGraph G) { mst = new Queue<>(); MinPQ<Edge> pq = new MinPQ<>(); for (Edge e : G.edges()) pq.insert(e); UF uf = new UF(G.V()); while (!pq.isEmpty() && mst.size() < G.V() - 1) { Edge e = pq.delMin(); int v = e.either(), w = e.other(v); if (uf.connected(v, w)) continue; uf.union(v, w); mst.enqueue(e); } } public Iterable<Edge> edges() { return mst; } }

六、性能分析

算法 空间 时间
Lazy Prim ( E ) ( E \log E )
Eager Prim ( V ) ( E \log V )
Kruskal ( E ) ( E \log E )
  • Prim：适合稠密图（即时版本更高效）。
  • Kruskal：适合稀疏图，边排序为主瓶颈。

七、展望

  • 历史：Prim（1939/1961）、Kruskal（1956）、Boruvka（1926）。
  • 优化：斐波纳契堆（( E + V \log V )）、Chazelle（接近线性但复杂）。
  • 线性时间：理论上未证明不存在，实际接近线性。

八、总结

  • 核心：切分定理和贪心策略。
  • 算法：Prim（逐步扩展树）、Kruskal（合并森林）。
  • 适用性：已解决大多数实际问题，现代数据结构提升效率。