- 最小生成樹的應用
- 切分定理
- 貪心演算法
- 加權無向圖的資料結構
- Prim演算法
- Kruskal演算法
最小生成樹的應用
加權圖是一種為每條邊關聯一個權值的圖模型，這種圖可以表示許多應用，比如在一副航空圖中，邊表示航線，權值就可以表示距離或費用；在一副電路圖中，邊表示導線，權值就可以表示導線的長度或成本，在這些情形中，最令人感興趣的便是如何將成本最小化，最小生成樹就是用于在加權無向圖中解決這類問題的，最小生成樹相關的演算法在通信、電子、水利、網路、交通燈行業具有廣泛的應用，
圖的生成樹是它的一顆含有其所有頂點的無環連通子圖，一副加權無向圖的最小生成樹(Minimum spanning tree)是它的一顆權值（樹中所有邊的權值之和）最小的生成樹，
切分定理
圖的一種切分是將圖的所有頂點分為兩個非空且不重復的集合，橫切邊是一條連接兩個屬于不同集合頂點的邊，
通常通過指定一個頂點集并隱式地認為它的補集為另一個頂點集來指定一個切分，這樣，一條橫切邊就是連接該集合的一個頂點和不在該集合中的另一個頂點的一條邊，
切分定理
切分定理的內容為：在一副加權圖中，給定任意的切分，它的橫切邊中的權重最小者必然屬于圖的最小生成樹，
切分定理是最小生成樹演算法的理論依據，
要證明切分定理，需要知道樹的兩個重要性質：
- 用一條邊連接樹中的任意兩個頂點都會產生一個新的環；
- 從樹中刪去任意條邊都將會得到兩顆獨立的樹，
接下來用反證法證明切分定理：令e為權值最小的橫切邊，T為圖的最小生成樹，假設T不包含e，那么將e加入T得到的圖必然含有一條經過e的環，且這個環至少還有另一條橫切邊——設為f，f的的權重必然大于e（因為e的權重是最小的且圖中所有邊的權值都不相同），那么刪去f保留e就可以得到一顆權值更小的樹，這與假設矛盾，
貪心演算法
切分定理是所有解決最小生成樹問題演算法的基礎，這些演算法都是一種貪心演算法的特殊情況，貪心演算法是一類在每一步選擇中都采取在當前狀態下最好或最優的選擇，從而希望導致結果是最好或最優的演算法，解決最小生成樹問題時，會使用切分定理找到最小生成樹的一條邊，不斷重復直到找到最小生成樹的所有邊，這些演算法之間的區別之處在于保存切分和判定權重最小的橫切邊的方式，
最小生成樹的貪心演算法：一副加權無向圖中，在初始狀態下所有邊均為灰色，找到一種切分，它產生的橫切邊均不為黑色，將它權重最小的橫切邊標記為黑色，如此反復，直到標記了V-1條黑色邊為止，
其中V為圖中頂點的數量，那么要將這些頂點全部連接，至少需要V-1條邊，根據切分定理，所有被標記為黑色的邊都屬于最小生成樹，如果黑色邊的數量小于V-1，那么必然還存在不會產生黑色邊的切分，只要找夠V-1條黑色邊，最小生成樹就完成了，
加權無向圖的資料結構
加權無向圖的資料結構沒有沿用之前無向圖的資料結構，而是重新定義了Edge和EdgeWeightedGraph類，分別用于表示帶權重的邊和加權無向圖，
帶權重的邊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 this.weight;
}
public int either() {
return this.v;
}
public int other(int vertex) {
if (v == vertex)
return w;
if (w == vertex)
return v;
else
throw new RuntimeException("Inconsistent edge");
}
public int compareTo(Edge 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);
}
}
either和other方法可以回傳邊連接的兩個端點，weight表示邊的權重，
加權無向圖EdgeWeightedGraph的實作
public class EdgeWeightedGraph {
private static final String NEWLINE = System.getProperty("line.separator");
private final int V; // vertex
private int E; // edge
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();
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 String toString() {
StringBuilder s = new StringBuilder();
s.append(V + " vertices, " + E + " edges " + NEWLINE);
for (int v = 0; v < V; v++) {
s.append(v + ": ");
for (Edge w : adj[v]) {
s.append(w + " | ");
}
s.append(NEWLINE);
}
return s.toString();
}
public Bag<Edge> edges() {
Bag<Edge> b = new Bag<Edge>();
for (int v = 0; v < V; v++) {
for (Edge w : adj[v]) {
b.add(w);
}
}
return b;
}
EdgeWeightedGraph與無向圖中的Graph非常類似，只是用Edge物件替代了Graph中的整數來作為鏈表的結點，adj(int v)方法可以根據頂點而索引到對應的鄰接表，每條邊都會出現兩次，如果一條邊連接了頂點v和w，那么這條邊會同時被添加到v和w對應的領接表中，
Prim演算法
將要學習的第一種計算最小生成樹的方法叫做Prim演算法，它的每一部都會為一顆生長中的樹添加一條邊，一開始這棵樹只有一個頂點，然后會向它添加V-1條邊，每次總是將下一條連接樹的頂點與不在樹中的頂點且權重最小的邊加入樹中，
但如何才能高效地找到權重最小的邊呢，使用優先佇列便可以達到這個目的，并且保證足夠高的效率，因為要尋找的是權重最小的邊，所以這里將使用查找最小元素的優先佇列MinPQ，
此外，Prim演算法還會使用一個由頂點索引的boolean陣列marked[]，和一條名為mst的佇列，前者用來指示已經加入到最小生成樹中的頂點，佇列則用來保存包含在最小生成樹中的邊，
每當在向樹中添加了一條邊時，也向樹中添加了一個頂點，要維護一個包含所有橫切邊的集合，就要將連接這個頂點和其他所有不在樹中的頂點的邊加入優先佇列，通過marked[]陣列可以識別這樣的邊，需要注意的是，隨著橫切邊的不斷加入，之前加入的邊中，那些連接新加入樹中的頂點與其他已經在樹中頂點的所有邊都失效了，因為這樣的邊都已經不是橫切邊了，它的兩個頂點都在樹中，這樣的邊是不會被加入到mst佇列中的，
接下來用tinyEWG.txt的資料來直觀地觀察演算法的軌跡，tinyEWG.txt的內容如下：
8
16
4 5 0.35
4 7 0.37
5 7 0.28
0 7 0.16
1 5 0.32
0 4 0.38
2 3 0.17
1 7 0.19
0 2 0.26
1 2 0.36
1 3 0.29
2 7 0.34
6 2 0.40
3 6 0.52
6 0 0.58
6 4 0.93
它表示的圖包含8個頂點，16條邊，末尾的double數值表示邊的權重，
下圖是演算法在處理tinyEWG.txt時的軌跡，每一張圖都是演算法訪問過一個頂點之后(被添加到樹中，鄰接鏈表中的邊也已經被處理完成)，圖和優先佇列的狀態，優先佇列的內容被按照順序顯示在一側，樹中的新頂點旁邊有個星號，
演算法構造最小生成樹的程序為：
- 將頂點0添加到最小生成樹之中，將它的鄰接鏈表中的所有邊添加到優先佇列之中，
- 將頂點7和邊0-7添加到最小生成樹之中，將頂點的鄰接鏈表中的所有邊添加到優先佇列之中，
- 將頂點1和邊1-7添加到最小生成樹之中，將頂點的鄰接鏈表中的所有邊添加到優先佇列之中，
- 將頂點2和邊0-2添加到最小生成樹之中，將邊2-3和6-2添加到優先佇列之中，邊2-7和1-2失效，
- 將頂點3和邊2-3添加到最小生成樹之中，將邊3-6添加到優先佇列之中，邊1-3失效，
- 將頂點5和邊5-7添加到最小生成樹之中，將邊4-5添加到優先佇列之中，邊1-5失效，
- 從優先佇列中洗掉失效的邊1-3、1-5和2-7，
- 將頂點4和邊4-5添加到最小生成樹之中，將邊6-4添加到優先佇列之中，邊4-7和0-4失效，
- 從優先佇列中洗掉失效的邊1-2、4-7和0-4，
- 將頂點6和邊6-2添加到最小生成樹之中，和頂點6相關聯的其他邊均失效，
演算法的具體實作：
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();
int v = e.either(), w = e.other(v);
if (marked[v] && marked[w])
continue;
mst.enqueue(e);
if (!marked[v])
visit(G, v);
if (!marked[w])
visit(G, w);
}
}
public void visit(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;
}
// cmd /c --% java algs4.four.LazyPrimMST ..\..\..\algs4-data\tinyEWG.txt
public static void main(String[] args) {
In in = new In(args[0]);
EdgeWeightedGraph ewg = new EdgeWeightedGraph(in);
LazyPrimMST lazyPrim = new LazyPrimMST(ewg);
double weight=0;
for (Edge e : lazyPrim.edges()) {
weight += e.weight();
StdOut.println(e);
}
StdOut.println(weight);
}
}
visit()方法的作用是為樹添加一個頂點，將它標記為“已訪問”，并將與它關聯的所有未失效的邊加入優先佇列中，在while回圈中，會從優先佇列取出一條邊，如果它沒有失效，就把它添加到樹中，否則只是將其從優先佇列洗掉，然后再根據添加到樹中的邊的頂點，更新優先佇列中橫切邊的集合，
Kruskal演算法
Prim演算法是一條邊一條邊地來構造最小生成樹，每一步都為一棵樹添加一條邊，接下來要學習的Kruskal演算法處理問題的方式則是按照邊的權重順序，從小到大將邊添加到最小生成樹中，加入的邊不會與已經加入的邊構成環，直到樹中含有V-1條邊為止，從一片由V顆單結點的樹構成的森林開始，不斷將兩棵樹合并，直到只剩下一顆樹，它就是最小生成樹，
同樣是處理tinyEWG.txt，Kruskal演算法的軌跡如下圖：
【】
該演算法首先會將所有的邊加入到優先佇列并按權重順序排列，然后依次從優先佇列拿到最小的邊加入到最小生成樹中，然后輪到處理1-3、1-5、2-7這三條邊時，發現它們會使最小生成樹形成環，說明這些頂點已經被包含到了最小生成樹中，屬于失效的邊；接著繼續處理4-5，隨后1-2、4-7、0-4又被丟棄，把6-2加入樹中后，最小生成樹已經有了V-1條邊，最小生成樹已經形成，查找結束，
演算法的具體實作為：
public class KruskalMST {
private Queue<Edge> mst;
private double _weight = 0;
public KruskalMST(EdgeWeightedGraph G) {
mst = new Queue<Edge>();
MinPQ<Edge> pq = new MinPQ<Edge>();
UF uf = new UF(G.V());
for (Edge e : G.edges()) {
pq.insert(e);
}
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;
}
// cmd /c --% java algs4.four.KruskalMST ..\..\..\algs4-data\tinyEWG.txt
public static void main(String[] args) {
In in = new In(args[0]);
EdgeWeightedGraph ewg = new EdgeWeightedGraph(in);
KruskalMST kruskalMST = new KruskalMST(ewg);
for (Edge e : kruskalMST.edges()) {
StdOut.println(e);
}
StdOut.println(kruskalMST.weight());
}
}
這里同樣使用了MinPQ來為邊排序，并使用了之前Union-Find演算法中實作的的Quick Union資料結構，用它可以方便地識別會形成環的邊，最終生成的最小生成樹同樣保存在名為mst的佇列中，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/113007.html
標籤：其他
上一篇：利用DFS算出有多少個連通圖