概述
一棵树
树是一种特殊的图，树必须满足：无回路；V 个顶点一定有 V - 1 条边。
生成树
生成树就是：包含全部顶点；V - 1 条边都在图里。下图所示，左边是原图（加权无向图），右边是图中的生成树，可以看出一幅图中可长出不同的生成树。
性质：用一条边连接树中的任意两个顶点都会产生一个新的环；从树中删去一条边将会得到两棵独立的树；生成树存在 '互推' 图连通
最小生成树
最小生成树：边的权重和最小的生成树。如图 1 所示，图右边中最小生成树是中间这棵，它的权重和为 5。
切分定理
上述介绍了最小生成树，那么问题来了，如何才能在图中找出最小生成树呢。答案就是：切分定理。
切分定理将会把加权图中的所有顶点分为两个集合、检查横跨两个集合的所有边并识别哪条边权值最小，权值最小的边应属于图的最小生成树，其中横跨两个集合的边叫做横切边。换句话说，使用切分定理便能找到最小生成树的一条边，不断重复直到找到最小生成树的所有边。
如下图所示，蓝红两个集合，绿色边是指横切边，标红的边是权值最小的横切边，它就是最小生成树中的一条边了。
加权无向图的数据类型
如上图所示，加权无向图 EdgeWeightedGraph 与 Graph 的 API 基本相同。区别在于加权无向图由于多了权重、边等概念，所以增加 Edge 类统一处理这些内容；EdgeWeightedGraph 中的邻接表 Bag 不再简单存储 integer，而存的是 Edge 对象。
Edge 类
public class Edge implements Comparable<Edge>{
private final int v; // 顶点之一
private final int 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){ // 另一个顶点
if (vertex == v) return w;
else if(vertex == w) return v;
else throw new RuntimeException("Inconsistent edge");
}
public int compareTo(Edge that){ // 将这条边 e与that比较
if(this.weight() < that.weight()) return -1;
else if(this.weight() > that.weight()) return +1;
else return 0;
}
public String toString(){
return String.format("%d-%d %.2f", v, w, weight);
}
}
EdgeWeightedGraph 类
public class EdgeWeightedGraph {
private static final String NEWLINE = System.getProperty("line.separator"); // 换行展示
private final int V; // 顶点总数
private int E; // 边的总数
private Bag<Edge>[] adj; // 邻接表
public EdgeWeightedGraph(int V){ // 创建一幅含V个顶点空图
this.V = V;
this.E = 0;
adj = (Bag<Edge>[]) new Bag[V];
for(int v = 0; v < V; v++)
adj[v] = new Bag<Edge>();
}
public EdgeWeightedGraph(In in){ // 从输入流中读取图
this(in.readInt());
int E = in.readInt();
for (int i = 0; i < E; i++) {
int v = in.readInt();
int w = in.readInt();
double weight = in.readDouble();
Edge e = new Edge(v, w, weight);
addEdge(e);
}
}
public int V(){ return V; }
public int E(){ return E; }
public void addEdge(Edge e){ // 向图中添加一条边 e
int v = e.either(), w = e.other(v);
adj[v].add(e);
adj[w].add(e);
E++;
}
public Iterable<Edge> adj(int v){ // 和v相关联的所有边
return adj[v];
}
public Iterable<Edge> edges(){ // 图的所有边
Bag<Edge> list = new Bag<Edge>();
for (int v = 0; v < V; v++) {
int selfLoops = 0;
for (Edge e : adj(v)) {
if (e.other(v) > v) {
list.add(e);
}
else if (e.other(v) == v) {
if (selfLoops % 2 == 0) list.add(e);
selfLoops++;
}
}
}
return list;
}
public String toString() { // 对象的字符串表示
StringBuilder s = new StringBuilder();
s.append("顶点：" + V + " 边：" + E + NEWLINE);
for (int v = 0; v < V; v++) {
s.append(v + ": ");
for (Edge e : adj[v]) {
s.append(e + " ");
}
s.append(NEWLINE);
}
return s.toString();
}
public static void main(String[] args) {
EdgeWeightedGraph G = new EdgeWeightedGraph(new In());
StdOut.println("-------------------------");
StdOut.println(G);
}
}
运行结果：
Prim 算法
Prim 算法是一种计算最小生成树的方法，它的每一步都会为一棵生长中的树添加一条边。一开始这棵树只有一个顶点，然后会向它添加 V-1 条边，每次总是将下一条连接树集合中的顶点与非树集合中的顶点且权重最小的横切边（黑色表示）加入树中。
算法详解
该算法用 edgeTo[] 数组记录最小生成树的所有的边；用 distTo[] 数组记录最小生成树所有边的权重；用 pq 队列来保存有效的横切边，红色线段表示存入 pq 队列中的横切边；最小生成树集合（白色背景顶点）；非树集合（灰色背景顶点）。
算法以下图为原图，最终找到图中的最小生成树：
1、选择一出发点 0，添加到最小生成树中，将它的邻接链表中的所有横切边添加到优先队列 pq 之中。
2、将顶点 7 和队列中权值最小的边 0-7 添加到最小生成树中。树集合扩展了顶点 7 ，所以顶点 7 的邻接链表中的所有横切边添加到 pq 队列中，故将边 1-7 和 5-7 添加到队列中。边 4-7 和 2-7 不会加入优先队列，因为对于非树集合中某顶点到树集合存在多条横切边，仅权重最小的边会入队，例如对于非树集合中点 2，与树存在两条横切边 2-0 和 2-7，由于 2-0 权重更小，所以 2-7 不会入队。
3、将顶点 1 和队列中权值最小的边 1-7 添加到最小生成树中，将边 1-3 入队。
4、将顶点 2 和队列中权值最小的边 0-2 添加到最小生成树之中，将连接顶点 6 与树的最小边由 0-6 替换为 2-6，将连接顶点 3 与树的最小边由 1-3 替换为 2-3。这是由于非树集合中顶点 6 到树只能存在一条权值最小横切边，2-6 权值小于 0-6，故将边 2-6 替代 0-6，顶点 3 同理。
5、将顶点 3 和队列中权值最小的边 2-3 添加到最小生成树之中。
6、将顶点 5 和队列中权值最小的边 5-7 添加到最小生成树之中，将连接顶点 4 与树的最小边由 0-4 替换为 4-5。
7、将顶点 4 和队列中权值最小的边 4-5 添加到最小生成树之中。
8、将顶点 6 和队列中仅剩的边 6-2 添加到最小生成树之中。
添加了 V-1 条边之后，最小生成树完成且优先队列为空。
代码展示
public class PrimMST {
private Edge[] edgeTo; // 距离树最近的边
private double[] distTo; // distTo[w] = edgeTo[w].weight()
private boolean[] marked; // 如果v在树中则为true
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); // 从起始点 0 开始
while(!pq.isEmpty())
visit(G, pq.delMin());
}
private void visit(EdgeWeightedGraph G, int v){ // 将顶点 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.change(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) {
EdgeWeightedGraph G = new EdgeWeightedGraph(new In());
PrimMST mst = new PrimMST(G);
StdOut.println("-------------------------");
StdOut.println("最小生成树：");
for (Edge e : mst.edges()) {
StdOut.println(e);
}
StdOut.print("最小生成树权重总值：" + mst.weight());
}
}
运行结果：
Kruskal 算法
Kruskal 算法的主要思想是每次选择权重最小的边，将其加入最小生成树中（图中的黑色边），加入的边不会与已经加入的边构成环，直到树中含有 V-1 条边为止。这些黑色的边逐渐合并为一棵树，也就是图的最小生成树。
算法详解
算法中用 mst 队列保存最小生成树所有边；用 pq 队列来保存未被检查的边；用 UF 的数据结构会识别形成环的边且判断无效的边。
算法以下图为原图，最终找到图中的最小生成树：
1、先将所有边权重从小到大排序，存入队列 pq 中。这样可以很方便的选择权重最小的有效边，加入最小生成树中。
0-7 0.16
2-3 0.17
1-7 0.19
0-2 0.26
5-7 0.28
1-3 0.29
1-5 0.32
2-7 0.34
4-5 0.35
1-2 0.36
4-7 0.37
0-4 0.38
6-2 0.40
3-6 0.52
6-0 0.58
6-4 0.93
2、选择队列 pq 中权重最小的有效边 0-7 加入到最小生成树中（加入mst 队列）。0-7 已检查，便会从 pq 中出队。
3、选择队列 pq 中权重最小的有效边 2-3 加入到最小生成树中。
4、选择队列 pq 中权重最小的有效边 1-7 加入到最小生成树中。
5、选择队列 pq 中权重最小的有效边 0-2 加入到最小生成树中。注意，由于 0-2 加入最小生成树中，且树不能有环的特性，所以边 1-2、1-3、2-7 会失效。
6、选择队列 pq 中权重最小的有效边 5-7 加入到最小生成树中。注意，由于 5-7 加入最小生成树中，所以边 1-5 会失效。
7、由于队列 pq 中很多边失效了，接下来权重最小的有效边 4-5 将加入到最小生成树中。由于 4-5 的加入，所以边 4-7、4-0 失效。
8、最后一条权重最小的有效边 2-6 加入到最小生成树中。Kruskal 算法结束。
代码展示
public class KruskalMST {
private double weight; // 最小生成树权重总值
private Queue<Edge> mst = new Queue<Edge>();
public KruskalMST(EdgeWeightedGraph G){
MinPQ<Edge> pq = new MinPQ<Edge>();
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); // 将边添加到最小生成树中
weight += e.weight();
}
}
public Iterable<Edge> edges(){
return mst;
}
public double weight(){
return weight;
}
public static void main(String[] args) {
EdgeWeightedGraph G = new EdgeWeightedGraph(new In());
KruskalMST mst = new KruskalMST(G);
StdOut.println("-------------------------");
StdOut.println("最小生成树：");
for (Edge e : mst.edges()) {
StdOut.println(e);
}
StdOut.println("最小生成树权重总值：" + mst.weight());
}
}
运行结果：
