資料結構與演算法04 by 隨機客

非正題：嗯，今天是騎車去上課有史以來最塞的一次，也是我有史以來上課最認真聽的一次(拿著筆電狂打)事實上還有很多不懂的地方，寫到這裡就要很感謝，哈密瓜的討論，Josh Ko的支持與校正，隨機客上課的精采，這些都是我邊碎碎念騎車邊快樂上課的動力:)

---

2007/03/19 資料結構與演算法(下) 呂學一 投影片

今天上課的主題是Minimum Spanning Tree MST 和 Epilogue(時間來不及所以省略)

• Minimum Spanning Tree - Boruvka' s algorithm
  此問題主在描述，在一圖形G中，每個edge都有不同的權重，找出連結所有node的最輕解(edge 的權重和相加為最小)用比較正式的描述則變成
  

  • Input: A connected n-node m-edge graph G with edge weight w.
  • Output: A spanning tree T of G with minimum w(T).

  這個問題的主要起源是Boruvka被波蘭政府委託在Bohemia這塊土地上牽電線，而讓每個城市都有線，而要怎麼樣牽電線會讓所耗費的成本為最小，就成為Minimum Spanning Tree的原始問題(yen3註：也蠻經典的XD)
  
  但是先假設一個狀況，才能使用Boruvka' s algorithm

  We may assume that all edge weights are distinct(yen3註：假設每一個邊的權重(重量)是不一樣的，而這樣子的假設不失一般性(JK註：不失一般性的原因，如果遇到這樣的狀況，也可以加以修改而符合假設。)，原因是，在真實世界上，也很難找到一樣權重的路)
  (JK註：假設並不會得問題的範圍變狹隘。)(相同權重的邊，稍微加一個數字造成些微的不同，雖然相同權重的邊有些許的不同，但是所算出的結果仍然一樣。)

  
  那麼解法呢，Boruvka' s algorithm 方法如下(s.9)
  
  1. 尋找每個node對外連接node的lightest incident edge加以連接
  2. 將已連接的connected component視為一點，尋找connected component 的 lightest incident edge再加以連接
  3. 集合每一個maximal subtree of F 成為一個single node(yen3註：我解釋的不好，所以照簡報)連接每個maximal subtree為單一集合，即為答案
  
  那麼簡單而言，讓每一個city伸出一隻手出去，往鄰邊伸出一隻手，從重量最輕的邊伸出去，如果每個ctiy都伸出最輕的手，則是Minimum spanning tree, 若無如此，，each city 都伸出lightest edge尋找spanning tree，則將connecting component縮成一個點再將已形成的spannign tree視同為一個node，再尋找每個node's lightest edge，直到連結全部node為止。
  
  那麼演算法的效率呢，是一個expected linear time從O(m log n)一直至O(m, a(m, n))甚至optimal time(比任何已知的演算法都來的快)，但是不是真正的linear time，無人知道，在s.7中有提到基於兩種基礎所發展出來的演算法。
  • Unit-cost RAM Model
    每一個數字用log n的數字來表示，允許任何連續O(log n) bit做加減乘除，皆可在linear time 上做到。
  • Deterministic comparison based algorithms
    需要把資料兩兩做比較的演算法，所以最多為O(n logn)
  
  當然，眼尖的人會發現此slight的論文發表時間有所問題，但是不是那麼的重要，所以我們略過:)
  
  那麼演算法的正確性呢？
  

  對於任何一點，連接此node的lightest edge此點為週圍鄰邊最輕的，此edge必得在MST上

  在s.12上，紅色代表為最輕的邊，n-1個點皆在右邊，假設Red edge 不在MST上，那麼右邊為一個connected ，變成第二個點在MST上，但是權重卻比red edge重，矛盾(JK註：證明)


• Minimum Spanning Tree - Kruskal' s algorithm

事實上為換湯不換藥的方法，採用的是disjoint-set方法的資料結構，方法比較簡單(JK註：Disjoint set的實作比較簡單)(s.14)

1. 每個node自為成一個集合
2. For each edge (u,v), taken in non-decreasing order by weights

   if Find-set(u) ≠Find-set(v) then
   Output edge (u,v)
   Union(u,v)

   (從權重最輕的邊依序處理，若兩集合不相等，則此兩邊必為相連的MST，所以印出edge(u, v)，把u, v兩個集合做一個結合成新集合)

至於正確性的證明是和Boruvka' s algorithm 一模一樣的。但是效率會好一點，會等於O(m log m) = O(m log n)


• Minimum Spanning Tree - Prim's algorithm
  前面的方法稍微散亂，這個演算法的方法的方法蠻簡單的(JK註：要先實作priority queue，本質上和Dijkstra最短路徑演算法相同)

  從任一點開始，尋找權重最輕的邊，每連一個點，就視為一個connected component，縮為一個點，再尋找權重最輕的點，相連，直至連接G 上所有node為止

至於正確性呢，證法也同Boruvka' s algorithm


• Advanced Topic - Expected O(m)-time comparison-base algorithm for MST [Karger-Klein-Tarjan, JACM 1995](yen3註：此處目前無人校稿，)
  呃，事實上要了解並不難，但是要先了解三個特性
  
  • Cut Property - 給一個MST，任意選一edge把所有node分成兩半，任意的crossing edges，一定比剛剛切掉的edge權重來的重
  
  
  • Cycle Property - 任一cycle in graph G，此cycle一定有一權重最重的edge，而此edge一定不在MST上
  
  
  • Uniqueness Property - 若任一edge權重都不一樣，那麼MST只有唯一解
  
  證明呢，我打算在下一篇blog說明，因為我認為我的思考還不夠完備，那時候寫也是不夠的XD
  此外還要再說明T-heavy edges(s.40)定義為在任一spanning tree of G，必然有一邊權重為最重的edge(u, v)，那麼根據cycle property ，此edge必不在MST上
  

  所有不在MST的edge必為T heavy edge(if and only if)。
  給一個spanning tree，把所有的T heave edge 丟掉，則此spanning tree必為Minimum Spanning Tree.

  
  也因為有了這個性質，要證明一個spanning tree是不是MST是非常簡單的，在linear time即可做到(s. 44. 45)
  
  那麼方法為
  

  The strategy: Using random sampling to further delete at least a constant factor of edges on average after each phase of edge contraction.(yen3註：這這裡不是那麼了解，課堂上的大意為random 取node，然後把T heave node刪掉，約取三次，最後會最多只剩n/3 nodes需要再做處理)

---

臨時趕完有品質很差的感覺(雖然品質從來沒好過)，不過換來的是，有一個禮拜的時間可以修正和擴充


Josh Ko 於 2007/03/20 校稿
---
寫到後面有一種很累的感覺