一、定義
最小生成樹（Minimum Spanning Tree，MST）僅針對加權(quán)連通無向圖。對于一副加權(quán)連通無向圖，其生成樹是它的一棵含有其所有頂點(diǎn)的無環(huán)連通子圖。
最小生成樹（MST）是指它的一棵權(quán)值最小的生成樹。
1-1 最小生成樹示例
API定義：
1-1 最小生成樹的API定義
二、性質(zhì)
最小生成樹的兩種主要算法（Prim算法和Kruskal算法）都基于切分定理。
最小生成樹具有以下性質(zhì)：
- 具體V個頂點(diǎn)的加權(quán)連通無向圖，其最小生成樹包含V個頂點(diǎn)，V-1條邊。
- 切分定理
在一副加權(quán)連通無向圖G中，將所有頂點(diǎn)分成兩個非空不相交子集U和V，假設(shè)頂點(diǎn)u∈U、v∈V，則對于權(quán)值最小的邊e=(u,v)，該圖的最小生成樹一定包含e。
證明（反證法）：
假設(shè)T是圖G的最小生成樹，且T不包含e=(u,v)。
①根據(jù)樹的定義，T中必然存在一條路徑f（假設(shè)f≠e），連接U和V（因?yàn)闃渲兴许旤c(diǎn)必然是連通的）；
②將e加入樹T，p和e必然構(gòu)成一個回路（樹中加入任意一條邊都會構(gòu)成回路）
③去掉回路中比e大的邊，將生成比原T權(quán)重更小的生成樹T'（與原假設(shè)中T是最小生成樹矛盾）
2-1 切分定理
三、Prim算法實(shí)現(xiàn)
3.1 基本思想
Prim算法是為一棵生長中的樹添加邊，每次添加一條。
初始時，這棵樹只有一個頂點(diǎn)，然后添加V-1條邊，每次總是選擇到樹中任意頂點(diǎn)最短的邊添加。
具體步驟：
- 將圖中所有頂點(diǎn)分屬兩個集合U和V：
U：樹頂點(diǎn)（已被選入生成樹的頂點(diǎn)）
V：非樹頂點(diǎn)（還未被選入生成樹的頂點(diǎn)） - 選擇任意一個頂點(diǎn)加入U
- 枚舉U，找到U到V之間的一條最短路徑，將這條最短路徑對應(yīng)的非樹頂點(diǎn)加入樹頂點(diǎn)。
- 重復(fù)步驟3（共V-1次），直到所有頂點(diǎn)加入樹頂點(diǎn)。
3-1 Prim算法示例
3.2 源碼實(shí)現(xiàn)
public class LazyPrimMST {
private double weight; // total weight of MST
private Queue<Edge> mst; // edges in the MST
private boolean[] marked; // marked[v] = true if v on tree
private MinPQ<Edge> pq; // edges with one endpoint in tree
public LazyPrimMST(EdgeWeightedGraph G) {
mst = new Queue<Edge>();
pq = new MinPQ<Edge>();
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++) // run Prim from all vertices to
if (!marked[v]) prim(G, v); // get a minimum spanning forest
}
private void prim(EdgeWeightedGraph G, int s) {
scan(G, s);
while (!pq.isEmpty()) { // better to stop when mst has V-1 edges
Edge e = pq.delMin(); // smallest edge on pq
int v = e.either(), w = e.other(v); // two endpoints
if (marked[v] && marked[w]) continue; // lazy, both v and w already scanned
mst.enqueue(e); // add e to MST
weight += e.weight();
if (!marked[v]) scan(G, v); // v becomes part of tree
if (!marked[w]) scan(G, w); // w becomes part of tree
}
}
// add all edges e incident to v onto pq if the other endpoint has not yet been scanned
private void scan(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;
}
public double weight() {
return weight;
}
public static void main(String[] args) {
In in = new In(args[0]);
EdgeWeightedGraph G = new EdgeWeightedGraph(in);
LazyPrimMST mst = new LazyPrimMST(G);
for (Edge e : mst.edges()) {
StdOut.println(e);
}
StdOut.printf("%.5f\n", mst.weight());
}
}
3.3 算法優(yōu)化
3.2 中對的Prim算法可以采用索引優(yōu)先隊列優(yōu)化：
用索引優(yōu)先隊列保存各個非樹頂點(diǎn)到樹頂點(diǎn)集合的最短距離；一個distTo數(shù)組保存非樹頂點(diǎn)v到樹頂點(diǎn)集合的最短距離，初始時為正無窮大。
優(yōu)化版本源碼：
public class PrimMST {
// edgeTo保存最小生成樹的邊
private Edge[] edgeTo;
// distTo[v]表示非樹頂點(diǎn)v到樹頂點(diǎn)集合的最短距離，初始時為正無窮大
private double[] distTo;
private boolean[] marked;
// 索引優(yōu)先隊列，保存各個非樹頂點(diǎn)到樹頂點(diǎn)集合的最短距離
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<Double>(G.V());
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
// run from each vertex to find minimum spanning forest
for (int v = 0; v < G.V(); v++)
if (!marked[v])
prim(G, v);
}
// run Prim's algorithm in graph G, starting from vertex s
private void prim(EdgeWeightedGraph G, int s) {
distTo[s] = 0.0;
pq.insert(s, distTo[s]);
while (!pq.isEmpty()) {
int v = pq.delMin(); // 找到一條最短切邊對應(yīng)的頂點(diǎn)v
marked[v] = true; // 加入樹頂點(diǎn)集合
//對頂點(diǎn)v的鄰邊進(jìn)行處理
for (Edge e : G.adj(v)) {
int w = e.other(v);
if (marked[w])
continue;
if (e.weight() < distTo[w]) { // 更新w到樹頂點(diǎn)集合的最短距離
distTo[w] = e.weight();
edgeTo[w] = e;
if (pq.contains(w))
pq.decreaseKey(w, distTo[w]);
else
pq.insert(w, distTo[w]);
}
}
}
}
public Iterable<Edge> edges() {
Queue<Edge> mst = new Queue<Edge>();
for (int v = 0; v < edgeTo.length; v++) {
Edge e = edgeTo[v];
if (e != null) {
mst.enqueue(e);
}
}
return mst;
}
public double weight() {
double weight = 0.0;
for (Edge e : edges())
weight += e.weight();
return weight;
}
public static void main(String[] args) {
In in = new In(args[0]);
EdgeWeightedGraph G = new EdgeWeightedGraph(in);
PrimMST mst = new PrimMST(G);
for (Edge e : mst.edges()) {
StdOut.println(e);
}
StdOut.printf("%.5f\n", mst.weight());
}
}
3.4 性能分析
Prim算法的時間復(fù)雜度一般為O(ElgV)，采用索引優(yōu)先隊列優(yōu)化后可以達(dá)到O(ElgE)。
四、Kruskal算法實(shí)現(xiàn)
4.1 基本思想
Kruskal算法的基本步驟如下：
- 首先按邊的權(quán)值從小到達(dá)排序；
- 每次從剩余邊中選出權(quán)值最小的，且頂點(diǎn)未連通的兩個頂點(diǎn)，加入到生成樹中；
- 直到加入V-1條邊為止。
4-1 Kruskal算法示意圖
4.2 源碼實(shí)現(xiàn)
public class KruskalMST {
private static final double FLOATING_POINT_EPSILON = 1E-12;
private double weight; // weight of MST
private Queue<Edge> mst = new Queue<Edge>(); // edges in MST
public KruskalMST(EdgeWeightedGraph G) {
// more efficient to build heap by passing array of edges
MinPQ<Edge> pq = new MinPQ<Edge>();
for (Edge e : G.edges()) {
pq.insert(e);
}
// run greedy algorithm
UF uf = new UF(G.V());
while (!pq.isEmpty() && mst.size() < G.V() - 1) {
Edge e = pq.delMin();
int v = e.either();
int w = e.other(v);
if (!uf.connected(v, w)) { // v-w does not create a cycle
uf.union(v, w); // merge v and w components
mst.enqueue(e); // add edge e to mst
weight += e.weight();
}
}
// check optimality conditions
assert check(G);
}
/**
* Returns the edges in a minimum spanning tree (or forest).
* @return the edges in a minimum spanning tree (or forest) as
* an iterable of edges
*/
public Iterable<Edge> edges() {
return mst;
}
/**
* Returns the sum of the edge weights in a minimum spanning tree (or forest).
* @return the sum of the edge weights in a minimum spanning tree (or forest)
*/
public double weight() {
return weight;
}
// check optimality conditions (takes time proportional to E V lg* V)
private boolean check(EdgeWeightedGraph G) {
// check total weight
double total = 0.0;
for (Edge e : edges()) {
total += e.weight();
}
if (Math.abs(total - weight()) > FLOATING_POINT_EPSILON) {
System.err.printf("Weight of edges does not equal weight(): %f vs. %f\n", total, weight());
return false;
}
// check that it is acyclic
UF uf = new UF(G.V());
for (Edge e : edges()) {
int v = e.either(), w = e.other(v);
if (uf.connected(v, w)) {
System.err.println("Not a forest");
return false;
}
uf.union(v, w);
}
// check that it is a spanning forest
for (Edge e : G.edges()) {
int v = e.either(), w = e.other(v);
if (!uf.connected(v, w)) {
System.err.println("Not a spanning forest");
return false;
}
}
// check that it is a minimal spanning forest (cut optimality conditions)
for (Edge e : edges()) {
// all edges in MST except e
uf = new UF(G.V());
for (Edge f : mst) {
int x = f.either(), y = f.other(x);
if (f != e) uf.union(x, y);
}
// check that e is min weight edge in crossing cut
for (Edge f : G.edges()) {
int x = f.either(), y = f.other(x);
if (!uf.connected(x, y)) {
if (f.weight() < e.weight()) {
System.err.println("Edge " + f + " violates cut optimality conditions");
return false;
}
}
}
}
return true;
}
/**
* Unit tests the {@code KruskalMST} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
In in = new In(args[0]);
EdgeWeightedGraph G = new EdgeWeightedGraph(in);
KruskalMST mst = new KruskalMST(G);
for (Edge e : mst.edges()) {
StdOut.println(e);
}
StdOut.printf("%.5f\n", mst.weight());
}
}
4.3 性能分析
Kruskal算法一般還是比Prim算法慢，因?yàn)樵谔幚砻織l邊時，除了兩種算法都要完成的優(yōu)先隊列操作外，Kruskal算法還需要進(jìn)行一次并查集的connect()操作。
五、各類最小生成樹算法的比較
5-1 各類MST算法比較
