文章来源：
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) 求得。（請參考本站文件「 」）
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 點的，如此不斷分下去，直到最後一點。
阅读(1255) | 评论(0) | 转发(0) |
