最小生成树的说法是基于加权无向图，比较经典的算法是Prim算法和Kruskal算法。
在认识这两种算法之前要先介绍一个定理：切分定理。即在一幅加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图的最小生成树。切分定理实际上也是一种贪心算法，它让我们找到最小生成树的一条边，不断重复直到找到最小生成树的所有边。
算法实现之前先引入数据类型。
带权重的边：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36public 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){
if(this.weight()<that.weight)
return -1;
if(this.weight()>that.weight)
return 1;
return 0;
}
public String toString() {
return String.format("%d-%d %.2f",v,w,weight);
}
}
加权无向图：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53public 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<Edge>();
}
public EdgeWeightedGraph(In in) {
this(in.readInt());
int E = in.readInt();
if (E < 0) throw new IllegalArgumentException("Number of edges must be nonnegative");
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){
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<Edge>();
for (int v=0;v<V;v++)
for(Edge e:adj[v])
if(e.other(v)>v)
b.add(e);
return b;
}
}
Prim算法
Prim算法主要考虑的是点的关系
以上图片来自http://www.cnblogs.com/skywang12345/
从上图分析中能够看出Prim算法是一个不断增加点的过程，当集合中A加入之后就开始寻找与A相关的各个点，从中选取权重较小的那个，选中B之后就以A、B作为基础进行继续选择，重复以上过程可以得到Prim算法下的最小生成树。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45public class LazyPrimMST {
private double weight;//权重
private Queue<Edge> mst;//最小生成树的边
private boolean[] marked;//最小生成树的顶点
private MinPQ<Edge> pq;//横切边，如果一个边的两个端点，属于切分不同的两边，这个边就称为横切边
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++)
if (!marked[v])
prim(G, v);
}
private void prim(EdgeWeightedGraph G, int s) {
scan(G, s);
while (!pq.isEmpty()) {
Edge e = pq.delMin();//从pq中得到权重最小的边
int v = e.either();
int w = e.other(v);
if (marked[v] && marked[w])//跳过失效的边
continue;
mst.enqueue(e);//将边添加到树中
weight += e.weight();
if (!marked[v]) scan(G, v);//将顶点添加到树中
if (!marked[w]) scan(G, w);
}
}
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;
}
}
这是Prim算法的延时实现，它主要是保存了大量无用的边。因为我们感兴趣的部分只是连接树顶点和非树顶点中权重最小的边，对于非树顶点w，我们只关心w与树结点相连的权重最小的边，因为其余权重更大的边迟早会被淘汰。
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58public 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()];
pq = new IndexMinPQ<Double>(G.V());
for (int v = 0; v < G.V(); v++)
distTo[v] = Double.POSITIVE_INFINITY;
for (int v = 0; v < G.V(); v++)
if (!marked[v]) prim(G, v);
}
private void prim(EdgeWeightedGraph G, int s) {
distTo[s] = 0.0;
pq.insert(s, distTo[s]);
while (!pq.isEmpty()) {
int v = pq.delMin();
scan(G, v);
}
}
private void scan(EdgeWeightedGraph G, int v) {
marked[v] = true;
for (Edge e : G.adj(v)) {
int w = e.other(v);
if (marked[w]) continue; // v-w失效
if (e.weight() < distTo[w]) {
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;
}
}
这是Prim算法的即时版本。即时版本是以点距离树的距离作为条件，在最开始时候把dist都置为负无穷，如果该点位于树中某点的邻接表中，则置为0，并开始将其与优先队列中有的权重比较(如果之前已经有该点到树的权重)，如果新权重比原来的低就进行数据更新。
Kruskal算法
Prim算法是一条边一条边地来构造最小生成树，每一步都为一棵树添加一条边。而Kruskal算法是寻找边会连接一片森林中的两棵树。
以上图片来自 https://www.cnblogs.com/wxdjss/p/5503023.html
代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30public 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();
int w = e.other(v);
if (!uf.connected(v, w)) {
uf.union(v, w);
mst.enqueue(e);
weight += e.weight();
}
}
}
public Iterable<Edge> edges() {
return mst;
}
public double weight() {
return weight;
}
}
分析：
从代码中能够看出，首先是将所有边都加入优先队列，再不断从中取出权值最小的边，通过判断点之间的连通性来对两棵树进行union操作。
这其中的缺少的数据结构，比如UF、Queue、Edge可以到http://algs4.cs.princeton.edu/code 下载。