Tree

Tree

「樹」。樹是一種很特別的圖。樹的定義是:任兩點之間都相通,並且沒有環的圖。

樹的定義對初學者來說或許太過抽象。換個說法吧:一棵樹可想做是由一個點開始,藉由許多條邊不斷地延伸拓展到其他點,而且點和邊都不會重複地被拓展到。

Node

「節點」。進行延伸拓展的點、被延伸拓展到的點,稱作「節點」,也就是說樹上的點都是「節點」。

【註:為了方便,以下仍稱呼「點」。】

Branch

「枝」。延伸拓展所用到的邊稱作「枝」,也就是說樹上的邊都是「枝」。一個點藉由邊往外延伸拓展,稱做「分枝(Branching)」。

【註:為了方便,以下仍稱呼「邊」。】

Root

「根」。方才提到,一棵樹可想做是由一個點開始分枝──這個點便是「根」。一棵樹上的每一個點都可以做為根。

Leaf

「葉」。在一棵樹上選定根後,由根開始不斷分枝,途中所有無法繼續分枝的點皆是「葉」。

另一種說法是:除了根以外,只連著一條邊的點就是葉。但這種說法有個例外:如果樹上總共只有一個點,那麼此點既是根、也是葉。

Level

「層」。在一棵樹上選定根後,按照拓展的順序(也就是按照每個點離根的距離),可以將樹上的點分層次,使得樹上每一個點都擁有一個層數。如果改變根,那麼分層的結果就會不同。

還有另一種比較少見的分層方式,是設定所有葉在同一層,並由葉開始計算層數。

Parent & Child

「父親」與「小孩」。在一棵樹上選定根後,以邊相連的任兩點,靠近樹根者相對地稱作「父親」,靠近樹葉者相對地稱作「小孩」。

一個點的父親,是指與其相鄰的點當中,較此點靠近樹根者,為其父親。父親只會有一個,特例是:樹根沒有父親。

一個點的小孩,是指與其相鄰的點當中,較此點靠近樹葉者,為其小孩。小孩可以是任意多個,特例是:樹葉沒有小孩。

Ancestor & Descendant

「祖先」與「子孫」。在一棵樹上選定根後,一個點的父親、父親的父親、……皆是此點的「祖先」。一個點的小孩、小孩的小孩、……皆是此點的「子孫」。

Directed Tree

在一棵樹上選定樹根後,可以把邊的方向設定成分枝的方向、遠離樹根的方向;也可以把邊的方向設定成朝向樹根的方向,但是這種情況比較少。

Weight

一棵樹可以有權重。當邊擁有權重時,一棵樹的權重等於樹上所有邊的權重總和。

Forest

「森林」。很多棵樹稱作一叢「森林」。

Tree資料結構
( Under Construction! )

UVa 10729

Tree相關性質

樹的特性

1. 樹沒有環。
2. 任意兩點之間只有唯一一條路徑。
3. 樹上所有點之間都相連通。
4. 在樹上任意添加一條邊,就會產生環。
5. 在樹上任意刪除一條邊,一顆樹就裂成兩棵樹。
5. 邊數等於點數減一。

height (rooted tree)

運用Divide and Conquer,移除一棵樹的樹根,形成許多子樹,並分頭處理子樹。

寫成程式碼之後,D&C的運作順序,剛好就是DFS的遍歷順序。因此,有人把這樣的程式碼,直接稱為DFS。這用詞並非精準,然而其過程恰是遍歷一張圖,讀取資訊算出答案,故稱之為DFS倒也無妨。

diameter

樹上相離最遠的兩個點的路徑長度,便是樹的直徑。稍微修改一下計算高度的程式碼,就可以順便計算直徑。

UVa 10308

balanced height

想辦法選定一個樹根,讓樹的高度最小。演算法請自行參考程式碼,時間複雜度為兩次DFS的時間。

UVa 10459 10939

parent-child relationship (rooted tree)

建立DFS tree或者BFS tree,就可以輕鬆判斷一點是不是另一點的父親。

ancestor-descendant relationship (rooted tree)

利用DFS的遍歷順序,就可以輕鬆判斷一點是不是另一點的祖先。

least common ancestor (rooted tree)

樹上兩點共同祖先當中,離根最遠、深度最深的那一個祖先,常簡稱為LCA,亦有人稱lowest common ancestor、nearest common ancestor。

求LCA的演算法相當多元,將以另文介紹。此處僅介紹其中一種:求出樹上所有點對的LCA。

運用了DFS的特性以及Disjoint-set Forest的概念。

這裡是一個簡單的實作。

時間複雜度切成三部份討論:

一、DFS:很明顯的是O(V^2)或O(V+E),端看樹的資料結構是哪一種。

二、Disjoint-set Forest:直接考慮p[]被設值的次數,總共是O(V^2)次。

三、設定lca[][]的時間共為O(V^2)。

故時間複雜度總共是O(V^2)。

distance between two nodes

樹上任兩點之間只有一條路徑。由其中一點開始進行DFS或BFS,直到遇見另一點,就得到距離了。程式碼就不提供了。

時間複雜度為一次Graph Traversal的時間。

all distances from one node to any nodes

由該點開始進行BFS或DFS即可。時間複雜度為一次Graph Traversal的時間。

all distances between any two nodes

算出所有兩點之間的距離,稍微複雜了些。先隨便選定一個樹根,然後利用Least Common Acestor將路徑分割成兩條,分頭計算兩條路徑的長度。

這裡提供一個實作方式,時間複雜度為O(V^2)。

1. 樹上隨便挑一點作為樹根。
2. 求所有兩點之間的Least Common Ancestor。
3. 求樹根到圖上各點之距離d(‧)。
4. 樹上x點與y點的距離為 (d(x)-d(z)) + (d(y)-d(z)),
   其中z點是x點與y點的Least Common Ancestor。

再提供另一個實作方式,時間複雜度也是O(V^2)。

1. 樹上隨便挑一點作為樹根。
2. 求所有兩點之間的Least Common Ancestor。
3. 以top-down recursive DP計算樹上x點與y點的距離:

d(x,y) =
{ 0                    , when x = y
{ w(x, px), d(px, y)   , when y is the ancestor of x
{ w(y, py), d(x, py)   , when x is the ancestor of y
{ d(x,z) + d(y,z)      , otherwise (z is the lca of x and y)

d(x,y)為x點與y點之間的距離
w(x,y)為邊xy的權重。如果邊xy不存在,w(x,y)為無限大。
px為x的父親,py為y的父親。

Spanning Tree

Spanning Tree

中譯「生成樹」,從一張圖上分離出一棵包含圖上所有點的樹,便是這張圖的生成樹。一張圖的生成樹可能會有很多種,而最短路徑樹、DFS樹、BFS樹也都是生成樹(當一張圖是完全連通的時候);一張圖也可能不存在生成樹,而有「生成森林」(當一張圖部份不連通的時候)。

生成樹也可以有權重。當圖上每條邊都有權重時,生成樹的權重為樹上每條邊的權重總和。

Minimum Spanning Tree(MST)

中譯「最小生成樹」。亦有人稱Minimum Cost Spanning Tree,中譯「最小成本生成樹」。權重最小的生成樹就是最小生成樹。一張圖的最小生成樹可能會有很多種。

Directed Minimum Spanning Tree
(Directed MST)
(Minimum Arborescence)
(Optimum Branchings)

有向圖所分離出的有向生成樹。網路上有人稱之為「最小樹形圖」。

Spanning Forest

中譯「生成森林」。當一張圖部分不連通的時候,各個連接組件的生成樹,所形成的一叢森林。

Spanning Subgraph

中譯「生成子圖」,從一張圖上分離出一棵包含圖上所有點的子圖。可以想做是生成樹(森林)額外加上幾條邊。

Spanning Subtree

中譯「生成子樹」,從一張圖的子圖上分離出一棵包含子圖上所有點的樹。

Minimum Spanning Tree:
Prim's Algorithm
(Prim-Jarník Algorithm)

用途

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

演算法

和Dijkstra's Algorithm的概念相同,請參考「Shortest Path: Dijkstra's Algorithm」。

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

另外一個差異是:最小生成樹可以選定任何一點做為樹根,而最短路徑樹會有特定起點。

令map[a][b]是a點到b點的距離(即是邊的權重)。
令dist[a]是目前的MST到a點的距離,樹根設為零,其他點都設為無限大。

1. 重複下面這件事V次,以將所有點加入到最小生成樹之中。
 甲、尋找一個目前不在MST上而且離起點最近的點:
   直接搜尋dist[]陣列裡頭的數值,來判斷離目前的MST最近的點。(Greedy)
 乙、將此點加入到MST之中。
 丙、將此點連出去的邊的權重,更新至dist[]陣列之中。(DP)

時間複雜度

圖的資料結構為adjacency matrix的話,便是O(V^2);圖的資料結構為adjacency lists的話,還是O(V^2)。

UVa 10034 10147 10307 10397 10600 10842

Minimum Spanning Tree:
Kruskal's Algorithm

用途

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

演算法

一、兩棵MST,要合併成一棵MST時,找兩棵MST之間權重最小的邊做連結,當然會是最好的。二、三棵MST,要合併成一棵MST時,先連結其中兩棵連結權重最小的MST,然後才連第三棵,總是比較好。三、一個獨立的節點,可視為一棵MST。由以上三點,可以歸納出一個greedy方法:以權重最小的邊連結各棵MST,一定比較好。

1. 一開始圖上每一個點,各自是一棵最小生成子樹MSS。
2. 將圖上所有邊依照權重大小,由小到大排序。
3. 依序嘗試這些邊作為MST上的邊,直到完成MST。
 甲、每次選中的邊都必須是目前權重最小的邊:
   排序過就沒問題了。
 乙、每次選中的邊都必須是連接兩棵MSS的邊:
   如果目前選到的這條邊,會讓目前的MSS產生環,則捨棄。

不連通的圖

這個演算法有一個特色。如果原圖並非連通,找出來的邊仍然具有「權重最小」且能「連結圖上各點」的性質。Prim's Algorithm則無法處理不連通的圖。

沒選中的邊

方才的三個性質非常強健,除了可歸納出「每次選中的邊,都是MST上的邊」,還可歸納出「沒有選中的邊,絕不會成為MST上的邊,不論這張圖以後又增加了多少邊,依舊如此。」各位看倌可以自行驗證此說。

時間複雜度

排序圖上所有邊需時O(ElogE)。逐條邊建立MST,並且判斷環,可以利用Disjoint Sets,需時O(E*α(E))。故整體的時間複雜度為O(ElogE)。

關於Disjoint Sets可參考「Disjoint Sets: Union-Find Algorithm」。

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

了解這些題目後,就能懂得大意了。

UVa 908 10369 10462

Minimum Spanning Tree:
Borůvka's Algorithm

用途

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

演算法

換湯不換藥,與Kruskal's Algorithm理念相同,只是Borůvka一次就選許多條邊。

1. 一開始圖上每一個點,各自是一棵最小生成子樹MSS。
2. 重複以下步驟,直到形成最小生成樹(森林):
 甲、每棵MSS同時各自找權重最小的聯外邊
   (即是MSS與MSS之間的邊,而不是MSS之內的邊),
   與其他MSS相互連接,成為更大棵的MSS。
   這個動作在無向圖中絕對不會形成環。

時間複雜度

每個步驟中,每棵MSS同時各自找權重最小的聯外邊,用各棵MSS的樹根進行Graph Traversal即可解決,MSS之內的邊會拜訪一次,MSS之間的邊會拜訪兩次,圖上各點拜訪一次至兩次。整體算起來,每個步驟所需時間,介於一到二次Graph Traversal之間。

每棵MSS相互連接,最差的情況是兩兩互接,MSS總數量僅下降一半,所以運氣不好時需要logV個步驟。

故總時間複雜度為O(logV)次Graph Traversal的時間。

以下是使用Disjoint Forest實作的程式碼,時間複雜度不太正確,有點胡亂搞,僅供參考。希望大家可以寫出更好的程式碼。

2nd-best Minimum Spanning Tree:
Gabow's Algorithm

用途

在無向圖上,求出一棵最大(小)生成樹,再求出權重最接近最小(大)生成樹的另一棵生成樹。

當圖上每條邊的權重都不一樣時,才保證能求出權重次小(大)的生成樹。一般情況下,有可能求出另一棵最小(大)生成樹。

演算法

最小生成樹改了一條邊,就能變成次小生成樹,因此可以試著窮舉此條邊。

1. 先求出一棵最小生成樹。
2. 求出樹上任兩點ij之間,權重最大的邊,記為E(i,j)。
3. 窮舉每一條不在最小生成樹上的邊pq:
 甲、把邊pq添加到最小生成樹上,勢必形成環。
 乙、然後移除邊E(p,q),勢必又形成樹,此樹權重已然盡量少。
 丙、記下此樹。
4. 剛剛得到的E-(V-1)棵樹之中,權重最小者便是次小生成樹。

時間複雜度

為下述三項總和。一、建立一棵最小生成樹,看是用哪種演算法;二、建立E(i,j)的時間,等同於求樹上所有兩點之間的距離,為O(V^2);三、窮舉邊pq與增減一條邊的時間,共O(E)。

Directed Minimum Spanning Tree: Chu-Liu/Edmonds Algorithm

Chu-Liu/Edmonds Algorithm

Chu-Liu/Edmonds Algorithm用來求出有向圖的其中一棵最小生成樹(或者最大生成樹)。

想法

一棵生成樹上每一個點,都僅有一條入邊(除了根以外)。要找生成樹,圖上每一個點,都必須找到一條入邊(但不會是自己連向自己的入邊)。

既然要找最小生成樹,當然就是找權重越小的邊越好囉。每一個點(除了根以外)各自找到權重最小的入邊之後,有可能就剛好是一棵最小生成樹了,但是也有可能形成幾隻水母。

水母(沒有正式名稱,因為像水母就把它叫做水母)

由於每個點都僅有一條入邊,如果形成環,環上一定只有出邊,不會有入邊。每個點都僅有一條入邊,除了剛好形成一棵樹以外,要不就是形成水母──一只環再加上環上的點各是一棵樹的樹根,或者說是很多棵樹的樹根用環串起。

水母與最小生成樹

最小生成樹不得有環,所以水母是不合格的。然而水母是權重最小的連接方式,若有一棵恰當的最小生成樹,其權重會稍高於水母。

一、改變水母環上的邊,讓水母變成一棵樹。儘管整體權重稍微變大,但仍可接受。

二、改變水母觸手上的邊,並沒有比較好。不但讓整體權重變大,而且水母環仍舊存在,並沒有解決掉不合格的問題。

得到結論:只需要嘗試打開水母環上的邊就行了。打開邊的時候,要同時考慮新連入的邊的權重,以及被取消的邊的權重。選擇差值最小者,可讓總權重增加最小。進入水母環的邊全部都看過一遍後,就能選出差值最小者。

連入水母環的邊

根據Kruskal's Algorithm提到的最小生成樹相連性質,可以知道連接多隻水母,就和連接多棵最小生成樹的道理是一樣的,以權重小的邊來連接是最好的。唯一不同的是,Kruskal's Algorithm一旦發現造成環的邊,就直接捨棄;Chu-Liu/Edmonds Algorithm則是留下造成環的邊(形成水母),並且嘗試各種打開環的方式。

演算法

1. 刪去所有自己連向自己的入邊。
2. 重複以下步驟,直到形成生成樹為止:
 甲、找出圖上每個點的最小入邊。O(E)
   如果有兩個點以上找不到入邊,則表示生成樹不存在。
   (找不到入邊的點可作為生成樹樹根)
 乙、找出所有水母。如果沒有水母就表示目前已是最小生成樹。O(V)
 丙、調整所有進入水母環的邊的權重。O(E)
   w(a, x) -= w(å, x),åx是x點的最小入邊,ax為其他連入x點的邊。
 丁、收縮水母環成為一點。O(E)

如果要固定樹根的話:

1. 刪去所有自己連向自己的入邊。
2. 移除樹根的全部入邊。
3. 判斷樹根能不能連到圖上各個點,否則生成樹不存在。
4. 重複以下步驟,直到形成生成樹為止:
 甲、找出圖上每個點的最小入邊。O(E)
 乙、找出所有水母。如果沒有水母就表示目前已是最小生成樹。O(V)
 丙、調整所有進入水母環的邊的權重。O(E)
   w(a, x) -= w(å, x),åx是x點的最小入邊,ax為其他連入x點的邊。
 丁、收縮水母環成為一點。O(E)

最糟的情況是每個步驟中剛好產生一直水母環有兩個點的水母,水母環進行收縮後,整張圖只減少一個點。所以最多要進行V-1次步驟,總共的時間複雜度會是O(V*E)。

據說此演算法還可以加速成O(V^2)以及O(ElogV),不過我不知道怎麼做就是了。

UVa 11183

類似生成樹的樹

Minimum k-Spanning Tree

k-Spanning Tree是一棵剛好有k個點的生成子樹。求出權重最小的、剛好有k個點的生成子樹,是NP-Complete問題。

Steiner Tree

在一張無向圖上選定k個點,然後用圖上的邊連接這k個點,選到的邊的總權重越小越好。

為了減少權重,當然要儘可能的去掉多餘的邊,所以這張子圖一定不會出現環,這張子圖會是一棵樹。

要求出Steiner Tree是NP-Complete問題。

Steiner Tree特殊情況:
當k = 1時,Steiner Tree就是一個點。
當k = 2時,Steiner Tree就是此兩點間最短路徑。
當k = V時,Steiner Tree就是最小生成樹。

http://www.prefield.com/algorithm/dp/steiner_tree.html