如何找 articulation point
以前在離散看過相關的解說，但那時候看了老半天不知道在寫什麼鬼。
最近看了資結版本的，總算大概知道怎麼看了。
Articulation Point，中文叫做關節點。(後面簡稱 AP)
定義 : 如果拿掉了這個點，整張圖會被分成兩個 Component。
OK，直接來看題目。
這邊借一下演算法筆記的圖，好像不少教材都用這個圖當例子 (?)
如圖所示，第一張左邊的圖是原圖，右邊則是標出了哪些是 AP。
其他格子內的則是顯示，如果拿掉了 AP 會得到什麼樣的結果。
這邊就直接開門見山的說了，我們可以透過 DFS 來做分析。
因此，我們對這張圖做 DFS Traversal，並且根據 Traversal 順序畫一張圖 (如右圖，DFS Tree)
Back edge 也要標上去
複習 : back edge 就是子孫(ancestor)指回去祖先的邊。
有 back egde 就會有環。
通過上面的 DFS Traversal，我們可以得到一個順序 :
這邊的例子剛好是 0 1 2 3 4 5 6 7 8 9。(0 為 root)
因此我們得到一個叫 DFN 的 array :
(DFN 就是拜訪順序。如果今天是 1 0 2 3 ... 9 ，那 1 的 DFN 就是 0 )
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|---|
| DFN | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Low |
這時候我們還需要一個資訊，叫 Low。
Low 的意義是：不斷往下走 tree edge ，最後走一次 back edge ，所能觸及的最高祖先。
公式 : Low( x ) = min( DFN(x), DFN(y) )
DFN(y) ? y 從哪來 ?
y 指的是 x 的所有子點，一直往下走，看能不能試著觸及祖先
(也就是走 Back Edge，因為只有走 BE 才可能接觸到祖先。)
其中，如果 x 沒有後代 (沒有子點)，也沒有 BE 可以走，那 y = x 也是可能的。
如果 x 跟他的子點都能往祖先，那看誰找到的祖先最上層。
其實如果用圖來看，真的是直接看 **"子點能碰到的祖先是哪位，另該祖先為 y" **
這樣就夠了，不然上面講得有些繞口。
圖片再放一次，來看一下 DFS Tree :
Low(0) = min( DFN(0), DFN(0) ) -> 0 自己就最老
Low(1) = min( DFN(1), DFN(0) ) -> 4 可以回去 0 所以找 DFN(0)
Low(2) = min( DFN(2), DFN(2) )
Low(3) = min( DFN(3), DFN(0) )
Low(4) = min( DFN(4), DFN(0) )
Low(5) = min( DFN(5), DFN(5) )
Low(6) = min( DFN(6), DFN(5) )
Low(7) = min( DFN(7), DFN(5) )
Low(8) = min( DFN(8), DFN(8) )
Low(9) = min( DFN(9), DFN(9) )
所以我們表格可以填好了
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|---|
| DFN | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Low | 0 | 0 | 2 | 0 | 0 | 5 | 5 | 5 | 8 | 9 |
最後階段 : 判斷 Articulation Point。
Root : 如果他有兩個以上子點，那 Root 是 Articulation Point。
非 Root : x 的每個子點，假設叫 w，若 Low( w ) >= DFN( x )，那 x 就是 Articulation Point。請搭配 DFS 產生的圖來判斷
以這題來說，Root 是 0，並且 ...
假設我們想判斷 1 是不是 AP，此時 x = 1 且 w 有 2 3 4，我們可以找 :
Low( 2, 3, 4 ) 是否 >= DFN( 1 ) ---> Low( 2 ) = 2 >= DFN( 1 ) = 1 ---> 砍掉 1 時，2 會被分離。
假設我們想判斷 2, 4, 8, 9 是不是 AP --- 但是這些點都沒有子點，直接判不是。
假設我們想判斷 3 是不是 AP，此時 x = 3，我們可以找 :
Low( 4 )=0 是否 >= DFN( 3 )=3 ? ---> 沒有，所以 3 不是。
假設我們想判斷 5 是不是 AP，我們可以找 :
Low( 6, 7, 8, 9) 是否 >= DFN( 5 ) ? ---> Low( 8 )=8 >= DFN(5)=5 ---> 砍掉 5 時，8 會被分離。
經過每個這樣判斷，我們得出 0, 1, 5, 7 是 Articulation Point。
時間複雜度為遍歷的時間複雜度。
圖的資料結構為 adjacency matrix ，便是 O(V²) ；圖的資料結構為 adjacency lists ，便是 O(V+E) 。
Ref : 演算法筆記
