# 最小生成树问题

在有权的无向连通图 $G=(V,E)$ 中，我们希望寻找一棵树，使得树上全体边的权重和最小，即

$$w(T) = \sum_{e \in T(E)}w(e)$$

最小。我们称这样的树为最小生成树 (minimum spanning tree, MST). 称其为最小的，因为其权重和是最小的。对于给定的图 $G(V,E)$, 求其最小生成树的问题就称为最小生成树问题。

对于最小生成树问题，常见的算法包括 Kruskal 算法和 Prim 算法，其都是通用最小生成树算法的具体实现，其本质都是贪心算法。

# 通用最小生成树算法

# 描述

我们假设 $A$ 是某个最小生成树边集的子集。则通用算法的思想是，对每条边 $e$, 若 $A \cup \{e\}$ 仍然是某个最小生成树边集的子集（此时我们称边 $e$ 是安全的 (safe)），那么就将 $e$ 加入集合 $A$, 直至 $A$ 成为最小生成树的边集。

下面是通用最小生成树算法的代码描述：

List<Edge> A = new ArrayList<Edge>(); //initialize

while (!A.isMST()) {

  for (Edge e : G){ //find a safe edge

    if (!A.has(e) && e.isSafe()) {

      A.add(e); //add the safe edge into set A

    } 

  }

}

return A;

对于特定的最小生成树算法，需要做的就是快速地确定安全边 $e$. 对于 Kruskal 算法和 Prim 算法，其策略不同。

下面，我们将给出识别安全边的规则。但我们需要先给出一些基本的定义。

# 基本概念

对于无向图 $G=(V,E)$, 我们定义其上的一个割 (cut) $(S,V-S)$ 是集合 $V$ 的一个二划分。

如果边 $e$ 的两端点 $u, v$ 满足 $u \in S$ 且 $v \in V-S$, 那么称边 $e$ 通过 (cross) 了割 $(S,V-S)$. 于是，若 $\forall e(u,v) \in A$, 均有 $\{u,v\}$ 同属于 $S$ 或 $V-S$, 那么称 $(S,V-S)$ 不妨碍 (respect) 边集 $A$.

对于图 $G=(V,E)$ 及其上的割 $(S,V-S)$, 若边 $e$ 是通过割 $(S,V-S)$ 的权值最小的边，那么我们称 $e$ 是割 $(S,V-S)$ 的轻边 (light edge). 更一般地，也可以称满足所有性质中边权最小的边为满足该性质的轻边。

# 安全边寻找法则

设 $G=(V,E)$ 是一个有权无向连通图。若 $A$ 是 $E$ 的一个包含于 $G$ 的某个最小生成树的子集。对于不妨碍 $A$ 的割 $(S,V-S)$, 割 $(S,V-S)$ 的轻边 $e$ 关于 $A$ 是安全的。

该定理的证明是简单的：

假设 $T$ 是包含 $A$ 的一棵最小生成树，且对于割 $(S,V-S)$, 不含其对应的轻边 $e$. 设 $T$ 中通过割 $(S,V-S)$ 的边为 $e'$ (根据树的性质，边 $e'$ 是唯一的)。则对 $T' = T - \{e'\} \cup \{e\}$, 其是连通的，边数为 $V-1$ 子图，于是 $T'$ 也是一棵树。则 $\omega(T') = \omega(T) - \omega(e') + \omega(e) \geq \omega(T)$. 于是 $\omega(e') \leq \omega(e)$, 又 $\omega(e)$ 为轻边，于是夹逼得 $\omega(e') = \omega(e)$, 则 $e'$ 也是轻边。

定理的证明虽然简短，但思路值得学习。首先，证明采用了

对于此法则，我们可以作一个显然的推论：

设 $G=(V,E)$ 是一个有权无向连通图。$C=(V_C,E_C)$ 是森林 $G_A = (V,A)$ 的一个连通分支，若边 $(u,v)$ 是连通 $G_A$ 与其余某连通分支的一条轻边，那么 $(u,v)$ 对于 $A$ 是安全的。

# 通用最小生成树算法的正确性

根据上述安全边寻找法则，我们显然可以证明通用最小生成树算法是正确的。

首先，每一次将某条安全边$e$ 加入集合$A$ 的过程都是使图$G_A = (V,A)$ 的连通分支数减少$1$ 的过程。且若图$G_A$ 不是连通的，那么一定存在一个划分$(S,V-S)$，使得$S$ 中的任意顶点与$V-S$ 中的任意顶点不连通。而图$G$ 是连通图，于是存在通过割$(S,V-S)$ 的轻边，根据安全边寻找法则，该轻边是安全边。于是，寻找安全边的操作能成功进行$V-1$ 次，因此通用最小生成树算法最终可以生成一棵树$T$。

若生成的树$T$ 是最小生成树。

# Kruskal 算法

# 算法描述

Kruskal 算法的代码描述如下：

List<Edge> A = new ArrayList<Edge>();

for (Vertex v : V) {

    v.root = v; //every vertex now in the different disjoint-set

}

Arrays.sort(E);

for(int i=0; i<sizeof(E), i++) {

    Edge e = E.get(i);

    if (e.left.root.equals(e.right.root)) {

        A.add(e); //means e is a safe edge

        merge(e.left, e.right); //union two disjoint-set of e's endpoint

    }

}

return A;

算法是这样的，首先将$A$ 初始化为空集，然后将边按升序排列。按权值从小到大依次验证边$e$ 是否是安全的。验证安全的过程需要判断$e$ 的两顶点 ( e.left 与 e.right ) 是否为连通的，一般采用并查集辅助判断。

# 复杂度分析

初始化过程的复杂度为$O(V)$，将边按权值排序的过程复杂度为$O(E\log E)$。对每条边，验证其是否安全的复杂度为$O(\log V)$，于是总复杂度为$O(V + E\log E + E\log V) = O(E\log E)$，而对简单图，有$|E|<|V|^2$，于是复杂度也可以表述为$O(E\log V)$。

# Prim 算法

# 算法描述

在 Prim 算法中，我们首先任选一个顶点$v$ 加入顶点集$S$，于是对于割$(S,V-S)$，我们可以从中选取轻边加入边集$A$，然后将$A$ 的位于$V-S$ 的顶点移入$S$，完成维护。这样，在不断维护和更新$S$ 的过程中，会形成一棵最小生成树。其代码描述如下：

// r is the beginning vertex

for (Vertex u : V) {

    u.key = Double.POSITIVE_INFINITY;

    u.pi = null;

}

r.key = 0;

Heap<Vertex> Q = new Heap<Vertex>(); //use heap to store the vertex queue, key is the weight

for (Vertex u : G) {

    if (!u.equal(r)) Q.add(u);

}

while (!Q.empty()) {

    Vertex u = Q.pop(); //get the vertex in Q, which has the minimum key

    for (Vertex v : G.Adj[u]) {

        if (Q.has(v) && weight(u,v) < v.key) {

            v.pi = u;

            v.key = weight(u,v);

        }

    }

}

在上面的代码中，边集 $A=\{(u,\pi[u])|u \in V-\{r\} - Q\}$. 对于每个顶点，其存在一个 key 域，维护到边集$A$ 的最短距离。队列 $Q$ 采用小根堆存储，堆顶为 key 值最小的顶点。

# 复杂度分析

初始化过程复杂度为$O(V)$，

# 最小生成树的性质

最小生成树存在一些有趣的性质：

1. 图中最短边一定属于某棵最小生成树。
2. 若图中存在多棵最小生成树，则其边的权值由小到大排成的序列是相同的。