《算法》筆記 11 - 最小生成樹

2020-12-05 菜鳥程式設計師成長記

最小生成樹的應用切分定理貪心算法加權無向圖的數據結構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的內容如下：

8164 5 0.354 7 0.375 7 0.280 7 0.161 5 0.320 4 0.382 3 0.171 7 0.190 2 0.261 2 0.361 3 0.292 7 0.346 2 0.403 6 0.526 0 0.586 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的隊列中。

相關焦點

  • 數據結構圖的最小生成樹的算法和應用舉例
    一、最小生成樹介紹圖結構是一種非常重要的非線性數據結構，帶權圖的最小生成樹在工程技術，科學管理的最優解問題中有著廣泛的應用。最小生成樹：權值和最小的生成樹最小生成樹的性質：假設G=(V,E)是個連通圖，U是頂點V的一個非空子集。若(u,v)是一條具有最小權值的邊，其中u∈U，v∈V－U，則必存在一棵包含邊(u,v)的最小生成樹。
  • C++ Prim算法Kruskal算法構造可以使n個城市連接的最小生成樹
    ，用Prim算法或Kruskal算法建立最小生成樹，並得到的最小生成樹的代價。要求在屏幕上顯示得到的最小生成樹中包括了哪些城市間的道路，並顯示得到的最小生成樹的代價。2、表示城市間距離網的鄰接矩陣（要求至少6個城市，10條邊）3、最小生成樹中包括的邊及其權值，並顯示得到的最小生成樹的代價。
  • 機器學習|決策樹的生成過程是怎樣?(一)
    本文筆者將用具體例子講述決策樹的構建過程，分析：決策樹生成過程中有什麼樣的問題？一、基本概念決策樹的定義：首先，決策樹是一種有監督的分類算法——即給定X，Y值，構建X，Y的映射關係。不同於線性回歸等是多項式，決策樹是一種樹形的結構，一般由根節點、父節點、子節點、葉子節點構成如圖所示。
  • 機器學習-決策樹(ID3算法)
    本篇文章採用python實現ID3算法，代碼取自於《Machine Learning in Action》，網上關於本書的代碼很多，但是很多都是直接照搬代碼運行，少數會帶有一些注釋，對於python新手或者小白來說非常不友好。
  • 機器學習中決策樹的原理與算法 | 科普
    因為一個數據集的信息熵是固定的，所以這個問題就轉化為選擇條件信息熵最小的屬性，所以我們只要求出條件信息熵最小的屬性就知道根結點了。 我們只需要將已經得到的結點看做一個新的根結點，利用最小化條件信息熵的方法即可。
  • 從決策樹到隨機森林:樹型算法的原理與實現
    每種方法都包括生成多種樹，這些樹被聯合起來，生成一個單一的一致性預測結果，並且經常帶來預測精度的顯著提升。決策樹決策樹是一種監督學習算法。它適用於類別和連續輸入（特徵）和輸出（預測）變量。基於樹的方法把特徵空間劃分成一系列矩形，然後給每一個矩形安置一個簡單的模型（像一個常數）。從概念上來講，它們是簡單且有效的。首先我們通過一個例子來理解決策樹。
  • 關於「樹」的算法:現實生活中的決策樹
    樹的結構給了我們開發算法的靈感，並再將其反饋到機器，讓它們學習我們希望它們學習的東西，以解決現實生活中的問題。這些基於樹的學習算法被認為是最好和最常用的監督學習方法之一：決策樹、隨機森林、梯度提升等方法在各種數據科學問題中得到了廣泛應用。對於每一個機器學習的初學者來說，學習這些算法並將其用於建模非常重要。
  • 數據結構與算法分析筆記——B樹
    數據結構與算法分析筆記——B樹B樹AVL樹的特徵是，通過在插入或刪除時的微調，使得整個樹中任意節點的左子樹和右子樹之間的高度差不超過1。這樣的結果是，整棵樹的高度不至於太高。那麼，如果我們想要得到一棵更低的樹？該如何呢？
  • 樹模型(一)——樹的構造
    這3種算法是機器學習中的經典算法，本節將針對這3種不同的算法的特徵選擇過程、決策樹的生成細節進行逐步展開。決策樹的構造核心在於如何分支，即如何選取最優的特徵和劃分點依據，需要一個統一的指標（信息量）。熵和基尼指數構建一棵樹的基礎是挑選出最有用的特徵——特徵選擇。特徵選擇的依據是特徵的貢獻度。
  • 算法最熱arXiv論文接收率高一倍,NeurIPS2019最全報告+視頻+筆記
    因為文章較長，我們可以先概覽這些重要結論：算法、深度學習、應用是最熱的投稿關鍵詞，但水論文也多。發表在 arXiv 上的論文接收率更高，是未發表在 arXiv 上的文章的兩倍。今年大會測試了幾項減少被審論文數量的措施，但減少的論文數都非常有限，還有可能錯過好論文。
  • 圖論的各種基本算法
    圖中可以有多顆生成樹，而生成樹的代價就是樹中所有邊的權重的和。最小生成樹就是生成樹中代價最小的。 樸素的想法就是從圖中選擇最小權重的邊，直到生成一顆樹。看通用的算法之前，同樣要討論一下最小生成樹的性質。 對於一個連通、無向、有權圖中，一定有最小生成樹。
  • 用圖形解釋10種圖形算法
    與樹不同，圖可以包含循環(第一個頂點和最後一個頂點相同的路徑)。 因此，我們必須跟蹤訪問的頂點。 在實現BFS時，我們使用隊列數據結構。圖2表示示例圖的BFS遍歷的動畫。 注意如何發現頂點(黃色)並訪問頂點(紅色)。應用領域 用於確定最短路徑和最小生成樹。
  • 並行算法庫清單: 附各算法代碼實例!
    【IT168 資訊】並行算法採用並行程式語言NESL實現，該語言是卡內基梅隆大學Scandal項目中開發的一種程式語言。對於每個算法，團隊給出了一個簡短的描述以及複雜性評估(就工作和深度而言)。　　在很多情況下，NESL代碼已經設置完畢，可以使用FORMs基本接口來運行算法。隨意更改數據或算法，並提交修改後的版本。
  • [ICML 2018]用於分子圖生成的聯結樹變分自動編碼器
    一方面為了激勵自己多看科研文章，另一方面為了把騰睿筆記真的做成筆記。希望能對大家有幫助。圖1. 方法概述具體的圖（樹）編碼器和圖（樹）解碼器參見原文。提出的JT-VAE在重建的準確率超出基準方法，同時所有生成的分子都是有效的。相比於單個原子生成的方法，以有效的子結構作為生成單位解決了分子的有效性不足的問題。
  • 《盜墓筆記》的小筆記之「先天八卦」
    看了這麼久的《盜墓筆記》，不能光過個眼癮。也要從中學到知識。這本書中經常提到風水寶地、奇門遁甲、生門死門一類的詞語。修建陵墓講究風水，但這風水就比較廣泛了。北派的尋龍點穴都與八卦有密切的聯繫。小編因為看了《盜墓筆記》，對風水八卦感了興趣，但這也不是一朝一夕就能學會的（我覺得南派三叔懂這些，他經常用奇門遁甲找東西）。
  • 數據結構基礎:樹結構的學習筆記
    樹的高度：一棵樹的最大層次數稱為樹的高度或者樹的深度。有序（無序）樹：樹中的節點的各個子樹看成是從左到右有次序的，即不能交換，則稱為有序樹，否則為無序樹。二叉樹是n(n>=0)個節點的有限集合，它或者是空樹（n=0），或者是由一個根節點及兩棵不相交的、分別稱為左子樹、右子樹的二叉樹所組成。
  • 達爾文記錄進化論的兩本筆記失竊,內含著名的生命之樹素描
    據英國劍橋大學圖書館稱，一名小偷可能偷了查爾斯·達爾文的兩本親筆筆記本，其中一本裡有他在1837年所繪製的標誌性「生命之樹」素描。然而，在2001年1月的一次例行檢查中，館長發現裝書的藍色小盒子不見了。雖然盒子有可能是放錯了地方，但是多年來徹底的搜索都沒有結果，所以圖書館正在考慮盒子被偷的可能性。
  • 太驚豔了,原來算法可視化後可以這麼藝術
    我們稱之為泊松圓盤分布，因為任意細胞間的最小距離總是一定的。它與前面兩個算法最大不同在於，它是 充分利用現有採樣點逐步生成新的採樣點 ，而不是在整個採樣區域隨機生成新的採樣點。同時也注意到，任意兩個採樣點的最小距離都是一定，沒有特別靠近的兩個點（正如泊松圓盤分布所定義的那樣），這些都是由算法的執行過程嚴格保證的。
  • 一個真正安全的去中心化加密筆記應用程式TrustNote介紹
    TrustNote採用AES-256加密算法加密票據。AES-256是軍用級的，目前是最安全的加密算法。下圖顯示了TrustNote如何生成AES-256密匙的過程。 安全的唯一鍵 TrustNote為每個用戶生成一個全局唯一的私鑰，其算法與比特幣為用戶生成私鑰的算法相同，並通過助記符幫助用戶備份私鑰
  • 兩本查爾斯·達爾文的筆記遭偷竊,包括「生命之樹」草圖
    編譯 | 賀璐據《衛報》報導，兩本查爾斯·達爾文的筆記遭偷竊，其中包括達爾文1837年影響深遠的「生命之樹」（tree of life）草圖。基於筆記的獨特屬性，其價值難以估量，但預計可能達到數百萬英鎊，圖書館方面稱。「生命之樹」草圖。這兩本筆記曾從儲藏室被取出，在圖像部門拍攝照片。拍攝工作於2000年11月完成。當時圖書館正在進行「大規模的建築工作」。