一个带权图（edge-weighted graph）的每条边上都带有我们赋予的权值。如果图是飞机的航线，那么权值可以表示距离、或者表示票价等。下面，我们主要考虑无向带权图（undirected edge-weighted graph）。
最小生成树（Minimum spanning tree）
————————————————————————
一个带权图的最小生成树(MST)是它的所有生成树中权值之和最小的一个。
————————————————————————
一些假设
- 图是连通的（connected）：只有图是连通的时候，才有最小生成树；如果图不是连通的，那么生成的就是最小生成森林，即给每个连通部分找出一个最小生成树。
- 边的权重不一定代表距离
- 边的权重可以为0或负值
- 边的权重互不相同：这保证了我们找出的生成树是唯一的。事实上，如果有权值相同的边，算法依然可以很好的工作，找出一棵最小生成树
分割性质
回忆一下树的两个性质：
- 添加一条边连接两个节点会产生一个环
- 删除任一条边就会将这棵树分开成两棵子树
————————————————————————
图的一个分割（cut）是指将图的所有节点分成两个不连通的子集的一种划分（partition）。一个分割的跨越边（crossing edge）指的是连接着两个节点（这两个节点分别属于分割产生的两个子集）的边。
————————————————————————
如上图所示，灰色的节点属于一个子集，白色的节点属于另一个子集，红色的边代表跨越边。
————————————————————————
给定一个带权图的任意一个分割，跨越边中权值最小的一条一定在这个图的最小生成树中
————————————————————————
贪心算法
————————————————————————
下面的方法可以将任一含有V个节点的带权图的最小生成树的每条边标记出来：首先将所有边标记为灰色，然后找到一个不含黑色边的分割，将它的最小权值的跨越边标记为黑色，直到有V-1条边被标记为黑色。
————————————————————————
算法的详细过程如下图所示：
带权图的数据结构
我们可以用邻接矩阵来表示带权图，对应位置中的元素表示边的权重；也可以用邻接链表来表示带权图，给每个节点加一个表示权重的属性。不过，下面我们要用另外一种表示方法，使程序可以有更广泛的应用范围。
具体的方法如下：我们将边抽象成一个类，用一个Bag对象来存储一个节点连接的所有边的引用，如下图所示
边的API
public class Edge implement Comparable<Edge>
Edge(int v, int w, double weight)
double weight() // 这条边的权重
int either() // 这条边连接的两个节点中任意一条
int other(int v) // 这条边连接的两个节点中另外一条
int compareTo(Edge that)
String toString()
带权图的API
public class EdgeWeightedGraph
EdgeWeightedGraph(int v)
EdgeWeightedGraph(In in)
int V()
int E()
void addEdge(Edge e)
Iterable<Edge> adj(int v)
Iterable<Edge> edges()
String toString()
上面的表示方法含有冗余的信息（节点v的链表中的Edge对象也含有v），尽管只有一个Edge对象，但我们有两个指向它的引用。如果去掉节点中的v，虽然不含有冗余信息，但我们需要两个节点实体来表示同一条边，也增大了空间开销。
怎么表示最小生成树
主要有以下三种方案：
- 一个包含所有边的列表
- 一个带权图
- 一个以节点序号为索引的数组（数组元素为指向父节点的引用）
我们选用第一种方案，所以有如下的API
public class MST
MST(EdgeWeightedGraph G)
Iterable<Edge> edges()
double weight() // 最小生成树的权重
Prim 算法
Prim算法从一棵只含一个节点的树开始，向它添加V-1条边，每次选取连接着树中与树外节点的边中权重最小的一条。关键问题是：我们如何快速地找出最小权重的跨越边(crossing edge with minimum weight)？
数据结构
借助下面的数据结构，我们可以实现Prim算法
- 树中的节点：我们用以节点序号为索引的布尔数组marked[]来表示树中的节点，如果marked[v]为true则表示v节点在树中
- 树中的边：我们使用下面两种数据结构中的任意一种：一个队列mst来存储最小生成树中的 边；一个以节点序号为索引的数组edgeTo[]，数组元素是Edge对象，edgeTo[v]表示将v连接到树上的那条边
- 跨越边：我们用一个最小优先队列MinPQ
来按权重大小比较各条跨越边
维持跨越边的集合（Maintaining the set of crossing edges）
每当我们向树上添加一条新的边时，同时相当于添加了一个新的节点v。为了维持跨越边的集合，我们需要向优先队列中插入所有从v指向未在树中节点的边。当添加新边后使得原有的跨越边连接的两个节点都处在树中时，这条跨越边就变成不合格的。Prim算法的积极版本(eager version)会立即删除这些边，而懒惰版本(lazy version)只是在我们需要删除的时候才进行不合格判断。
public class LazyPrimMST
{
private boolean[] marked[];
private Queue<Edge> mst;
private MinPQ<Edge> pq;
public LazyPrimMST(EdgeWeightedGraph G)
{
pq = new MinPQ<Edge>();
marked = new boolean[G.V()];
mst = new Queue<Edge>();
visit(G, 0);
while (!pq.isEmpty())
{
Edge e = pq.delMin(); // Get lowest-weight edge from pq
int v = e.either(), w = e.other(v);
if (marked[v] && marked[w]) continue; // Skip if ineligible
mst.enqueue(e); // Add edge to tree
if (!marked[v]) visit(G, v); // Add vertex v to tree
if (!marked[w]) visit(G, w); // Add vertex w to tree
}
}
private void visit(EdgeWeightedGraph G, int v)
{ // Mark v and add to pq all edges from v to unmarked vertices
marked[v] = true;
for (Edge e : G.adj(v))
if (!marked[e.other(v)]) pq.insert(e);
}
public Iterable<Edge> edges()
{ return mst; }
}
下面是详细的图解
————————————————————————
对一个含有E条边和V个节点的连通带权图，在最差情况下，懒惰版本(lazy version)的Prim算法使用$O(E)$的空间和$O(E \log E)$的时间可以计算出一棵最小生成树。
————————————————————————
这个时间上界是十分保守的，因为通常情况下优先队列中的边数远小于E
积极版本的Prim算法
要改进懒惰版本的Prim算法，我们要从优先队列删去那些不合格的边。所以，优先队列中只含有连接着树中节点与树外节点的跨越边。不过，我们可以删去更多的边。我们关心的只是每个树外节点到某个树中节点的若干条边中权重最小的一条。
对树外的一个节点w来说，当我们添加了一个节点v到中时，我们去判断添加v之后w到树中节点的距离会不会变小，如果变小，我们就更新w到树中节点的权重的最小值，并将路径设置为v。综上，优先队列中只有V-1个元素，保存着每个节点到树的权重的最小值。
我们使用一个索引优先队列进行存储，用edgeTo[]数组保存连接v到树的最短的那条边，用distTo[]数组保存v到树的最小权重。
public class PrimMST
{
private Edge[] edgeTo;
private double[] distTo;
private boolean[] marked;
private IndexMinPQ<Double> pq;
public PrimMST(EdgeWeightedGraph G)
{
edgeTo = new Edge[G.V()];
distTo = new double[G.V()];
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
pq = new IndexMinPQ<Double>(G.V());
distTo[0] = 0.0;
pq.insert(0, 0.0);
while (!pq.isEmpty())
visit(G, pq.delMin()); // Add closest vertex to tree
}
private void visit(EdgeWeightedGraph G, int v)
{ // Add v to tree; update data structures
marked[v] = true;
for (Edge e : G.adj(v))
{
int w = e.other(v);
if (marked[w]) continue; // v-w is ineligible
if (e.weight() < distTo[w])
{ // Edge e is new best connection from tree to w
edgeTo[w] = e;
distTo[w] = e.weight();
if (pq.contains(w)) pq.change(w, distTo[w]);
else pq.insert(w, distTo[w]);
}
}
}
}
下面是详细的图解
————————————————————————
对一个含有E条边和V个节点的连通带权图，在最差情况下，积极版本(eager version)的Prim算法使用$O(V)$的空间和$O(E \log V)$的时间可以计算出一棵最小生成树。
————————————————————————
Kruskal算法
Kruskal算法采取方法和Prim算法完全不同。它从按权重从小到大依次选取边，如果添加这条边到最小生成树中不会构成环，就添加这条边到最小生成树中，直到选了$V-1$条边为止。也就是说，我们从一个含有$V$个单节点树的退化森林开始，每一步相当于将两棵树合并成一棵树，直到整个森林合并为一棵树为止。
关于数据结构：我们使用优先队列来按权重排序边；使用Union-Find来判断是否会构成环；使用一个队列来收集最小生成树中的边。
public class KruskalMST
{
private Queue<Edge> mst;
public KruskalMST(EdgeWeightedGraph G)
{
mst = new Queue<Edge>();
MinPQ<Edge> pq = new MinPQ<Edge>(G.edges());
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; // Ignore ineligible edges
uf.union(u, w);
mst.enqueue(e);
}
}
}
大致的过程如下图所示：
————————————————————————
对一个含有E条边和V个节点的连通带权图，在最差情况下，Kruskal算法使用$O(E)$的空间和$O(E \log E)$的时间可以计算出一棵最小生成树。
————————————————————————
上面的时间开销是保守的，事实上应该是$E+E_0\log E$。其中，$E_0$代表比MST边中权重最大边的权重小的所有边的数量，比E小很多。
Perspective
| algorithm | space | time |
|---|---|---|
| lazy Prim | $E$ | $E\log E$ |
| eager Prim | $V$ | $E\log V$ |
| Kruskal | $E$ | $E\log E$ |
| Fredman-Tarjan | $V$ | $E+V\log V$ |
| Chazelle | $V$ | very,very nearly but not quite $E$ |
| impossible? | $V$ | $E$ ? |
Chazelle算法十分复杂，所以实践中常用的仍是Prim和Kruskal算法