引言
有關概念可參考博文資料結構之圖的概述
我們要學習的第一種計算最小生成樹的算法，它每一步都會為一顆生長中的樹添加一條邊。
下面分析下算法思路
思路
一開始這棵樹隻有一個頂點，然後會向它添加V-1條邊，每次總是将下一條連接配接樹中的頂點與不在樹中的頂點且權重最小的邊加入樹中。
Prim算法
每次當我們向(生成)樹中添加了一條邊之後，也向樹中添加了一個頂點。要維護一個包含所有橫切邊的集合，就要将連接配接這個頂點和其他所有不在樹中的頂點的邊加入優先隊列。要注意的是，新加入樹的頂點與其他已經在樹中的頂點的所有邊都失效了。
Prim算法的即時實作可以将這樣的失效邊從優先隊列中删掉，我們先來學習延時實作的版本，暫且将這些邊留在優先隊列中，等要删除它們的時候再檢查邊的有效性。
圖的一種切分是将圖的所有頂點分為兩個非空且不重複的集合。這裡一個是生成樹頂點集合，另一個是待加入生成樹的頂點集合。橫切邊是一條連接配接屬于兩個不同集合的頂點的邊。
圖論算法——Prim算法和Kruskal算法
假設我們要計算下圖的最小生成樹
延時版本的Prim算法過程如下：
每一張圖檔都是算法通路過一個頂點之後(被加到生成樹中)圖和優先隊列的狀态。
優先隊列在圖的一側，新頂點旁邊有個
*
。算法構造最小生成樹的過程如下：
- 将頂點
0
0-7
- 将頂點
7
0-7
1-7,5-7,2-7,4-7
1-7
- 将頂點
1
1-7
0-2
- 将頂點
2
0-2
2-3,6-2
2-3
- 将頂點
3
2-3
3-6
5-7
- 将頂點
5
5-7
4-5
4-5
- 将頂點
4
4-5
6-2
- 将頂點
6
6-2
在添加了8個頂點和7條邊之後，最小生成樹就生成了。優先隊列中剩下的邊都是失效的，可以不去管它們。
延時版本的Prim算法實作
EdgeWeightedGraph
package com.algorithms.graph;
import com.algorithms.heap.BinaryHeap;
import com.algorithms.heap.Heap;
import com.algorithms.queue.Queue;
/**
* @author yjw
* @date 2019/5/24/024
*/
public class LazyPrimMST {
/**
* 最小生成樹的總權值
*/
private double weight;
/**
* 最小生成樹的頂點
*/
private boolean[] marked;
/**
* 最小生成樹的邊
*/
private Queue<Edge> mst;
/**
* 按照最小權值構造的優先隊列
*/
private Heap<Edge> pq;
public LazyPrimMST(EdgeWeightedGraph g) {
pq = new BinaryHeap<>();
marked = new boolean[g.vertexNum()];
mst = new Queue<>();
weight = 0;
//先通路第一個頂點0
visit(g,0);
while (!pq.isEmpty()) {
//循環跳出條件為pq為空
//從優先隊列中删除并傳回權值最小的邊
Edge e = pq.deleteMin();
//邊的兩個頂點v和w
int v = e.either(),w = e.other(v);
if (marked[v] && marked[w]) {
//如果該邊已經在生成樹中，則不執行後面的代碼，跳到!pq.isEmpty()判斷
continue;
}
//說明該邊不在生成樹中，加入最小生成樹mst
mst.enqueue(e);
weight += e.weight();
if (!marked[v]) {
visit(g,v);
}
if (!marked[w]) {
visit(g,w);
}
}
}
private void visit(EdgeWeightedGraph g,int v) {
marked[v] = true;
for (Edge e : g.adj(v)) {
//将頂點v的所有鄰接邊加入隊列中(除了已經在生成樹中的頂點的邊)
if (!marked[e.other(v)]) {
pq.insert(e);
}
}
}
/**
* 傳回最小生成樹的所有邊
* @return
*/
public Iterable<Edge> edges() {
return mst;
}
/**
* 傳回總的權重
* @return
*/
public double weight() {
return weight;
}
public static void main(String[] args) {
EdgeWeightedGraph g = new EdgeWeightedGraph(8);
g.addEdges(0,6,.58,2,.26,4,.38,7,.16);
g.addEdges(1,3,.29,2,.36,7,.19,5,.32);
g.addEdges(2,6,.40,7,.34,3,.17);
g.addEdge(3,6,.52);
g.addEdges(4,6,.93,7,.37,5,.35);
g.addEdge(5,7,.28);
LazyPrimMST lp = new LazyPrimMST(g);
System.out.println(lp.weight);
for (Edge e : lp.edges()) {
System.out.println(e);
}
}
} 其中優先隊列的實作請通路博文:Java中的優先隊列——二叉堆
輸出如下：
1.81
0-7(0.16)
1-7(0.19)
0-2(0.26)
2-3(0.17)
5-7(0.28)
4-5(0.35)
2-6(0.40) 運作時間
Prim算法的延時實作計算一幅含有V個頂點和E條邊的連通權重無向圖的最小生成樹所需的空間與E成正比，
所需的時間與成正比(最壞情況)。
Kruskal算法
這種算法實作起來更加簡單，主要思想是按照邊的權重順序（從小到大）處理它們，将最小的邊加入到最小生成樹中（通過小頂堆來實作），當然，新加入的邊不能與已加入的邊構成環(這一點通過并查集來檢查)。直到樹中含有V-1條邊為止。
Kruskal算法實作
package com.algorithms.graph;
import com.algorithms.UnionFind.QuickFindUF;
import com.algorithms.UnionFind.UF;
import com.algorithms.heap.BinaryHeap;
import com.algorithms.heap.Heap;
import com.algorithms.queue.Queue;
/**
* @author yjw
* @date 2019/5/28/028
*/
public class KruskalMST {
private Queue<Edge> mst;
private double weight;
public KruskalMST(EdgeWeightedGraph g) {
mst = new Queue<>();
//注意傳入的是Iterable
Heap<Edge> heap = new BinaryHeap<>(g.edges());
UF uf = new QuickFindUF(g.vertexNum());
weight = 0.0;
/**
* 為什麼要小于 vertexNum - 1 ? 因為生成樹中最多有vertexNum - 1個邊，是以當生成樹的邊為vertexNum - 1時說明已經生成完畢了
* 當然還有heap不能為空
*/
while (!heap.isEmpty() && mst.size() < g.vertexNum() - 1) {
//取到目前權重最小邊
Edge edge = heap.deleteMin();
//得到邊的兩個頂點
int v = edge.either(),w = edge.other(v);
//判斷是否會形成環，即該邊兩個頂點是否已經連通
if (uf.connected(v,w)) {
continue;
}
//不會則加入并查集和最小生成樹
weight += edge.weight();
uf.union(v,w);
mst.enqueue(edge);
}
}
public Iterable<Edge> edges() {
return mst;
}
public double weight() {
return weight;
}
public static void main(String[] args) {
EdgeWeightedGraph g = new EdgeWeightedGraph(8);
g.addEdges(0,6,.58,2,.26,4,.38,7,.16);
g.addEdges(1,3,.29,2,.36,7,.19,5,.32);
g.addEdges(2,6,.40,7,.34,3,.17);
g.addEdge(3,6,.52);
g.addEdges(4,6,.93,7,.37,5,.35);
g.addEdge(5,7,.28);
KruskalMST km = new KruskalMST(g);
System.out.println(km.weight());
for (Edge e : km.edges()) {
System.out.println(e);
}
}
} 輸出如下：
1.81
0-7(0.16)
2-3(0.17)
1-7(0.19)
0-2(0.26)
5-7(0.28)
4-5(0.35)
2-6(0.40)