楔子

把一張圖想像成道路地圖，把圖上的點想像成地點，把圖上的邊想像成道路。現在我們在意的是：由某一個地點開始，沿著道路不斷行進，可以到達哪些地點？

從起點開始，使用Graph Traversal，就可以找出所有可以到達的地點。

Connected（Reachable）

「連通」是一個形容詞，是指「有路可通」的意思。

對於一張圖上的兩個點來說，雙向都有路可通，這兩個點就「連通」。

在無向圖當中，兩個點之間邊邊相連，就形成「連通」。在有向圖當中，要注意邊的方向，如果兩個點之間，雙向都有路可通，就是「強連通」；至少單向有路可通（也可以雙向都通），就是「弱連通」。

Graph Traversal或者Transitive Closure都可以判斷連通。

Transitive Closure

一張圖的「遞移閉包」也是一張圖，用來紀錄由一點能不能走到另一點的關係，如果能走到，則兩點之間以邊相連。

只要對圖上每一個點都做一次Graph Traversal，就可以求出「遞移閉包」了。

時間複雜度為V次Graph Traversal的時間。圖的資料結構是adjacency matrix時，時間複雜度為O(V^3)；圖的資料結構是adjacency lists時，時間複雜度為O(VE)。

UVa 459

楔子

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

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

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

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

UVa 10681

走一步是一步，Incrememtal Method

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

然而，一張圖上最多只有V個點，要從一點走到另一點，走V-1條道路之內一定到得了，否則不論走多少條都一定到不了。

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

找出所有中繼站，拉出新路線，Enumerative Method

如果一張圖上，由i點可以走到某一個j點、這個j點又可以走到k點，那麼就可以由i點走到k點。

窮舉所有可能的j點，就可以判斷出由i點是否能走到k點了！

只要計算一下圖上每一個i點和每一個k點，就可以知道圖上各個點可以走到哪裡去了。不過這只能找出走了兩條道路的情況。

p2(i, k) = ( p1(i, 0) AND p1(0, k) ) OR
           ( p1(i, 1) AND p1(1, k) ) OR
           ...                       OR
           ( p1(i, 9) AND p1(9, k) )

pN(i, k)：由i點能不能走到k點，恰走了N條道路的時候。

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

pN+1(i, k) = ( pN(i, 0) AND p1(0, k) ) OR
             ( pN(i, 1) AND p1(1, k) ) OR
             ...                       OR
             ( pN(i, 9) AND p1(9, k) )

pN(i, k)：由i點能不能走到k點，恰走了N條道路的時候。

矩陣相乘，Modeling

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

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

演算法，Iterative Method

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

由於OR的性質，事實上還可以一邊OR矩陣、一邊乘矩陣，結果仍會正確。

p1~N+1(i, k) = p1~N(i, k)                  OR
               ( p1~N(i, 0) AND p1(0, k) ) OR
               ( p1~N(i, 1) AND p1(1, k) ) OR
               ...                         OR
               ( p1~N(i, 9) AND p1(9, k) ) OR

p1~N(i, k)：由i點能不能走到k點，當走了1條、2條、…… 、N條道路的時候。

矩陣的V次方，可參考本站文件「Fast Exponentiation」，藉由Divide and Conquer便能以O(logV)次矩陣乘法求得。矩陣相乘一般需時O(V^3)，當然還可以更快。

另外這個方法也可以用來計算從一點走到另外一點，走了N步之後總共有幾種走法。各位可以想想看。

精簡掉不必要計算的地方，去掉強連通分量

環上的點肯定是相互連通，可以免算Transitive Closure。因此可以直接收縮圖上所有環，再去找Transitive Closure。沒有環的圖有很強的性質。

把圖分作兩部分，Divide and Conquer

精簡過後的圖進行Topological Sort，然後將所有點依照順序先後，分成前半群和後半群。這時便可以輕易的遞迴求得這兩群點的Transitive Closure，也可以輕易的求得前半群往後半群的遞移情況。

精簡過後的圖進行Topological Sort，其adjacency matrix會呈現一個可愛的上三角矩陣。將此矩陣切成四份，前半群點的Transitive Closure是左上角矩陣，後半群點的Transitive Closure是右下角矩陣，前半群往後半群的遞移情況是右上角矩陣。

演算法

一、收縮圖上所有環。
　　例如使用收縮圖上所有Strongly Connected Component的演算法。
二、進行拓樸排序（圖上無環），以利Divide and Conquer將圖分成兩部分。
三、把排序結果分成前半和後半兩群點，分別遞迴計算這兩群點的遞移閉包。
四、於Divide and Conquer的合併階段，計算前半群走到後半群的遞移情況。
　　至於由後半群往前半群是沒有道路的，因為拓樸排序。

1. 令G為精簡過後的圖的adjacency matrix。
   G均分成四份，左上為A，右上為T，左下為0矩陣，右下為B。
2. 遞迴求出A*。遞迴求出B*。
3. G*均分成四份，左上會是A*，右上會是A*TB*，左下會是0矩陣，右下會是B*。

時間複雜度正比於矩陣相乘的時間複雜度。

http://www.student.cs.uwaterloo.ca/~cs466/Old_courses/F08/transitiveClosure.pdf

延伸閱讀：分成前中後三群

當圖的構造特殊時，剛好可以分成三群，而且只有前群到中群、中群到後群的邊，便可以使用此式子。

1. 令G為圖的adjacency matrix。
   G均分成九份，上為A，右為B，其餘皆為0矩陣。
2. G*均分成九份，上仍為A，右仍為B，右上為AB，
   左上、中、右下為單位矩陣，其餘皆為0矩陣。

延伸閱讀：直接Divide and Conquer

這裡再提供一個完全不用求Strongly Connected Component，就可以直接做Divide and Conquer，其原理是以集合為單位來求Transitive Closure。時間複雜度正比於矩陣相乘的時間複雜度。

1. 令G為圖的adjacency matrix。
   G均分成四份，左上為A，右上為B，左下為C，右下為D。
2. 遞迴求出D*。
3. 令E = A + BD*C，並且遞迴求出F*。
4. G*均分成四份，左上會是E*，右上會是E*BD*，左下會是D*CE*，右下會是D* + D*CE*BD*。

把兩點之間的所有路線，依照中繼點來分類

首先列出一條路徑所有的中繼點，有可能是第0點、第1點、…… 第V-1點。現在把i點到j點的路線分成兩種：經過第0點、未經過第0點。接著兩種各自再細分為：經過第1點、未經過第1點。如此不斷細分下去直到：經過第V-1點、未經過第V-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點的時候。

然後利用Dynamic Programming計算各個子問題。時間複雜度是O(V^3)，空間複雜度則可以精簡至O(V^2)。

bool adj[9][9]; // 一張圖，資料結構為adjacency matrix。 bool tc[9][9]; // Transitive Closure void warshall() { // 先把原圖複製到要進行DP計算的陣列 for (int i=0; i<9; i++) for (int j=0; j<9; j++) tc[i][j] = adj[i][j]; // 依序計算各個子問題tc(i, j, k) for (int k=9-1; k>=0; k--) // for (int k=0; k<9; k++) for (int i=0; i<9; i++) for (int j=0; j<9; j++) if (tc[i][k] && tc[k][j]) tc[i][j] = true; }

UVa 280

延伸閱讀：中繼點順序

以中繼點來分類的時候，事實上可以採用任意的中繼點順序來分類。例如，把i點到j點的路線分成兩種：經過第V-3點、未經過第V-3點。接著兩種各自再細分為：經過第5點、未經過第5點。如此不斷細分下去，直到圖上每一點都被用於分類為止。

這樣子可以調整計算子問題的順序。也就是說，在k的迴圈當中，k值並非一定要從0跑到V-1才行，k值其實可以隨意變動，只要讓0到V-1的數字都剛好出現過一次就行了。