Spanning Tree

Spanning Tree / Spanning Forest

「生成樹」。從一張圖取出一棵樹,包含圖上所有點。可能有許多種。

當一張圖完全連通,則擁有生成樹。當一張圖不連通,則沒有生成樹,而是擁有許多棵「生成子樹」構成的「生成森林」。

生成樹的權重,是樹上每條邊的權重總和。

Minimum Spanning Tree

「最小生成樹」。權重最小的生成樹。可能有許多種。

Minimum Spanning Tree: Kruskal's Algorithm

用途

求出無向圖的其中一棵最小(大)生成樹。若是圖不連通,則是求出其中一叢最小(大)生成森林。

想法

一、一個單獨的點,視作一棵最小生成子樹MSS。

二、兩棵MSS連結成一棵MSS,以兩棵MSS之間權重最小的邊進行連結,顯然是最好的。

三、三棵MSS連結成一棵MSS,以其中兩棵MSS之間權重最小的邊進行連結,才連結第三棵,總是比較好。

點的視角:不斷連結兩棵MSS、合併兩棵MSS,得到最小生成樹(森林)。

邊的視角:依序以權重最小、次小、……的邊,嘗試連結各棵MSS,得到最小生成樹(森林)。

演算法

一、圖上每一個點,各自是一棵最小生成子樹MSS。
二、圖上所有邊,依照權重大小,由小到大排序。
三、嘗試圖上所有邊,作為最小生成樹(森林)的邊:
 甲、兩端點分別位於兩棵MSS,也就是產生了橋:
   用這條邊連結兩棵MSS,合併成一棵MSS。
   這條邊是最小生成樹(森林)上的邊。
 乙、兩端點皆位於同一棵MSS,也就是產生了環:
   捨棄這條邊。

尋找最小生成樹的過程:

尋找最大生成樹的過程:

時間複雜度

一、排序圖上所有邊。O(ElogE)。

二、連結MSS,採用「Disjoint-sets Forest」。O(Eα(E,V))。

總時間複雜度O(ElogE)。

如果兩點之間有多條邊,預先以Graph Traversal掃描一次所有邊,保留權重最小的邊,仍可求得正確答案。兩點之間只剩下一條邊,邊數至多C(V,2) = V(V-1)/2 = O(V²)條。時間複雜度O(ElogE)可以改寫成O(ElogV²) = O(2ElogV) = O(ElogV)。

迴圈的部份也可以寫成這樣。

UVa 908 10369

Minimum Spanning Tree: Prim's Algorithm

用途

求出無向圖的其中一棵最小(大)生成樹。

演算法

仿效「Shortest Path: Dijkstra's Algorithm」。

差異:Dijkstra's Algorithm屢次找不在樹上、離根最近的點,Prim's Algorithm屢次找不在樹上、離樹最近的點。

另一個差異:選擇特定一點作為起點,得到不同的最短路徑樹;選擇任意一點作為樹根,得到相同的最小生成樹。

時間複雜度

圖的資料結構為Adjacency Matrix,便是O(V²);圖的資料結構為Adjacency Lists,仍是O(V²)。

如同Dijkstra's Algorithm,使用Priority Queue可以得到更低的時間複雜度。

UVa 10034 10147 10307 10397 10842

© 2010 tkcn. All rights reserved.

Minimum Spanning Tree: Borůvka's Algorithm

用途

求出無向圖的其中一棵最小(大)生成樹。若是圖不連通,則是求出其中一叢最小(大)生成森林。

演算法

一、圖上每一個點,各自是一棵最小生成子樹MSS。
二、每棵MSS同時找權重最小、索引值最小的聯外邊,相互連接。
 口、聯外邊是MSS之間的邊,不是MSS之內的邊。
 口、聯外邊可能重複,無妨。
 口、聯外邊顯然不會形成環。
三、重複步驟二,直到形成最小生成樹(森林)。

找權重最小的聯外邊,以得到最小生成樹;當權重一樣小,則找索引值最小的聯外邊,以避免聯外邊形成環。聯外邊的索引值,可以改成聯外邊的兩端點索引值。

證明很簡單:圖上任意一個環,環上權重最大、索引值最大的邊,絕不會被選中。過程中無法形成環,只會形成樹。每一點都聯外,權重又最小,所以是最小生成樹。

時間複雜度

一、每回合尋找權重最小、索引值最小的聯外邊。O(V+E)。

二、連接MSS。採用「Disjoint-sets Forest」,每回合每個點都呼叫了union與find,森林結構維持在最佳狀態,union與find的總時間複雜度,從O(Eα(E,V))降為O(E)。

三、回合數。最差情況:每回合MSS兩兩成對互連,MSS總數量僅下降一半,共logV個回合。平均情況:圖上的邊呈隨機分布,僅1至2個回合。【待補證明】

最差時間複雜度O((V+E)logV),通常簡單寫成O(ElogV)。平均時間複雜度O(V+E)。

Minimum Spanning Tree: Edmonds' Algorithm

用途

求出有向圖的其中一棵最小(大)生成樹。

有向圖上,以權重最小的邊,連結兩棵有向MSS,不見得形成有向MSS。直接套用無向圖的演算法,邊的方向亂七八糟,無法形成有向生成樹。必須設計其他演算法。

想法

生成樹的基本概念是:連接圖上各點的樹。從這個概念下手,並且考慮邊的方向性,得到兩個粗糙的演算法:

有向圖上,每一個點,如果要被連結到,都要至少有一條出邊,除了樹葉以外。
每一個點,找權重最小的出邊,會比較好。
有向圖上,每一個點,如果要被連結到,都要剛好有一條入邊,除了樹根以外。
每一個點,找權重最小的入邊,會比較好。

出邊有許多條,入邊只有一條,從入邊下手比較容易。

樹根是個例外,樹根沒有入邊。但是我們可以假定我們已經知道最小生成樹的樹根是哪個點,如此就不必顧慮例外了。設計好演算法之後,用試誤法嘗試各種樹根即可。

Minimum Arborescence

預先指定樹根的有向最小生成樹。個人感覺這個詞彙不太討喜。

水母【尚無正式名稱,因為像水母就把它叫做水母】

運氣好的時候,各點的最小入邊,剛好形成一棵生成樹,而且是最小生成樹。

運氣普通的時候,各點的最小入邊,通常形成許多隻水母。

各點各取一條入邊,一旦入邊們形成環,此環一定只有出邊、沒有入邊。環與出邊,形成一個特別的圖:很多棵樹,一個環串起了樹根。又像是太陽、又像是水母。

把水母改裝成最小生成子樹

最小生成樹不得有環。水母有環,是不合格的。

水母是權重最小的連結方式,最小生成樹的權重則略高、等高於水母。使用窮舉法,嘗試拆除水母的每一條邊,並且更改為另一條邊,從中找到權重增加最少的邊。

一、更改水母環的邊:
 甲、新邊是由其他水母連入:水母環消失。變成其他水母腳。很好!
 乙、新邊是由自身水母環連入:水母環變小。連結權重無故變大,不可取。
 丙、新邊是由自身水母腳連入:水母環變大。多了一些點可供聯外。
二、更改水母腳的邊:
  水母環不變,連結權重無故變大,不可取。

有好處的只有一甲、一丙。歸納出:只需要更改水母環的邊,讓水母環消失或者變大,從中選擇權重增加最少的拆除方式。

演算法

水母環的入邊,全部看過一遍,找到權重增加最少的入邊。

已經看過的入邊,修改成權重增加量,然後收縮水母環,就不用看第二遍了。

壹、刪去所有自環:自己連向自己的邊。
貳、圖上每一點嘗試作為樹根。
 一、刪去樹根的全部入邊。也可以將權重設定為無限大。
 二、判斷樹根能不能連到圖上各點。否則生成樹不存在。
 三、重複以下步驟,直到形成生成樹為止:
  甲、每一個點,找出權重最小的入邊。O(V+E)
    形成一群水母。
  乙、調整水母環的入邊的權重,修改成權重增加量。O(V+E)
    w(a, x) -= w(å, x),
    x是水母環上一點。
    åx是x點的最小入邊,也是水母環上的邊。
    ax是x點的其他入邊。
  丁、收縮水母環,成為一點。O(V+E)

Kruskal's Algorithm連結多個MSS。一旦發現造成環的邊,就直接捨棄;一旦發現造成橋的邊,就一定保留。

Edmonds' Algorithm連結多隻水母。總是留下造成環的邊(形成水母環),並且嘗試各種打開環的方式:有時候擴大水母環,有時候兩隻水母連結成一隻水母。

時間複雜度

一、每回合找出各點的最小入邊。O(V+E)。

二、回合數。最差情況是每回合產生一個水母,水母環只有兩點。水母環收縮之後,整張圖只減少一個點。圖上有V個點,最多收縮V-1次水母環,總共V-1個回合。

三、窮舉V個點,嘗試作為樹根。

時間複雜度O(VVE)。

演算法

窮舉樹根,再仿效Dijkstra's Algorithm,時間複雜度O(V³)。有差異的地方,不影響時間複雜度:

一、縮環最多V-1次(兩點縮成一點)。縮環得到的新點,最多V-1個。總點數最多2V,仍是O(V)。

二、縮環,採用Disjoint-sets Forest。O(Eα(E,V))。

如同Dijkstra's Algorithm,使用Priority Queue可以得到更低的時間複雜度。

UVa 11183