Transitive Closure

楔子

把一張圖想像成道路地圖,把圖上的點想像成地點,把圖上的邊想像成道路。現在我們在意的是:由某一點開始,走過N條道路後,可以到達哪些點?

最簡單的莫過於走過零條道路的情況了,哪裡都去不了。至於走過一條道路的情況,可以到達起點附近的點。

【註:讀過Shortest Path章節的讀者,應該很快就會聯想到:由一點到另一點最少需要走過幾條道路。但是這和此處所言不同。】

當N很大時,各位可能會想到用Graph Traversal來試試看──可是路線是環的話就沒轍了。環經過同一個點很多次,而Graph Traversal只能拜訪一個點一次。

Transitive Closure

中文譯作「遞移閉包」。一張圖的Transitive Closure是一張圖,用來紀錄由一點能不能走到另一點的關係,如果能走到,則兩點之間以邊相連。

要找出一張圖的Transitive Closure,也就是要找出圖上每一個點,走過一條、兩條、…… 、無限多條道路之後,會到達圖上哪些點。

然而,一張圖上最多只有V個點,要從一點走到另一點,走V-1條道路之內一定到得了,否則不論走多少條都一定到不了。另外還要考慮從一點走過V個邊回到原點的情況(經過圖上所有點的環)。

因此,要找出一張圖的Transitive Closure,只要找出圖上每一個點,走過一條、兩條、…… 、V條道路之後,會到達圖上哪些點就可以了。

Transitive Closure: 一個普通的演算法

經過其他點

有個簡單的想法:如果一張圖上,由i點可以走到某一個k點、這個k點又可以走到j點,那麼就可以由i點走到j點。

窮舉所有可能的k點,就可以判斷出由i點到j點是否相通了!

只要再計算一下圖上每一個i點和每一個j點,就可以判斷出圖上各點是否相通了。不過這樣只能找出走過兩條道路的情況。

p2(i, j) = p1(i, 0) && p1(0, j) || ... || p1(i, 9) && p1(9, j)

pN(i, j):由i點能不能走到j點。N是走過的道路數目。

兩條加一條就是三條,三條加一條就是四條。走過三條道路、走過四條道路等等的情況,可以以逐次加一條道路的方式,慢慢累積而得。

pN+1(i, j) = pN(i, 0) && p1(0, j) || ... || pN(i, 9) && p1(9, j)

pN(i, j):由i點能不能走到j點。N是走過的道路數目。

經過其他點v.s.矩陣相乘

i點到k點,k點到j點,窮舉所有k點──其實就和矩陣乘法的規則一樣。如果把一張圖儲存成adjacency matrix,那麼直接拿這張圖的adjacency matrix自己乘上自己,並且把加法改成OR運算,乘法改成AND運算,相乘的結果就是走過兩條道路的情況了!

同理,走過兩條道路的矩陣,再乘上一次原圖的adjacency matrix,就會成為走過三條道路的情況。如此一來,若要求走過N條道路的情況,就是原圖的adjacency matrix的N次方。

一個普通的演算法

現在回頭談Transitive Closure要怎麼求。既然一張圖的Transitive Closure只需要檢查一條、兩條、…… 、V條道路,所以一張圖的Transitive Closure就是此圖的adjacency matrix的1次方、2次方、…… 、V次方,然後統統OR起來就對了。

時間複雜度

矩陣相乘需要O(V^3)(還可以更快)。矩陣的V次方可藉由Divide and Conquer以O(logV) * O(V^3) = O(logV * V^3)求得。(請參考本站文件「Divide and Conquer─Fast Exponentiation」)

Transitive Closure: Warshall's Algorithm

Warshall's Algorithm

Warshall不用「走過幾條道路」的觀點來思考,反而是用「中繼點」的觀點來思考:如果一張圖上可以由i點開始,走過一些中繼點,最後走到j點,那麼就可以由i點走到j點。這和上一個章節的「經過其他點」的概念類似。

中繼點有可能是第0點、第1點、…… 、等等。中繼點也不見得只有一點。儘管聽起來很複雜,不過Warshall卻利用Divide and Conquer,分割原問題成容易解決的小問題了!

Warshall把由i點到j點的路線分成兩種:經過第0點的、未經過第0點的。接著分別遞迴下去,再分為經過第1點的、未經過第1點的,如此不斷分下去,直到最後一點。

tc(i, j, k) = tc(i, k, k+1) && tc(k, j, k+1) || tc(i, j, k+1)
              ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^    ^^^^^^^^^^^^^
              經過第k點                    沒有經過第k點

tc(i, j ,k):紀錄由i點走不走的到j點,當中繼點遞迴到第k點的時候。

找出一張圖的Transitive Closure

使用Dynamic Programming紀錄每個小問題的答案。另外,由於計算順序以及OR運算的關係,造成記憶體可以重複使用,只需要開二維陣列。請見程式碼:

徵求練習題。