[ Alg info ] Using DFS to find Articulation point

Preface: 
考慮有下面網路拓譜圖, 當你是一個網管, 可能會希望找出當那些點 break 後則可能會造成部分的子網路無法連線而加以改善: (下面例子即是實驗室與 215 機房 的 switch) 
 

而你可以把網路拓譜圖視為一個 Connected graph, 而我們的目標便是找出 Argiculation point: 

如果在connected graph G 中的的一個 vertex v 被移除以後(包含 v 和所有incident在它上面的edge), 新的graph G’ 會變成有兩塊以上的connected components

以下面左邊的圖形為範例, Vertex 1, 3, 5 與 7 即為 Argiculation point: 
 

Use DFS to find Articulation point: 
底下說明使用 DFS (Deep First Search) 來找出 Articulation point. 首先第一步便是決定 Graph 的某一點開始跑 DFS 並標示出每點的 discover time. 假設我們取 Vertex 3 為 root 跑 DFS, 則一種可能的走法如下: (3-4-2-1-0-5-6-7-9-8) 
 

接著我們將 Vertex 3 視為 root 並調整長相如下 (虛線為 back edge): 
 

然後我們使用下面公式計算每一點的 low 值: 

low(u)=min{u.d, min{low(w)|w is a child of u}, min{w.d| (u,w) is a back edge}}

計算結果如下: 
 

接著只要滿足下面任一個條件即為 Articulation point: 

* Root 有超過一個 child 即為articulation point
* 當某 vertex v 有任何一個 child u 的 low(u)≥v.d 時, 則 v 為articulation point

以上面的例子來說, 因為 Root vertex 3 有兩個 child (Vertex 4,5), 故 Vertex 3 為 Articulation point; Vertex 1 的 d=3, 而其 child Vertex 0 的 low 值為 4, 故 Vertex 1 為 Articulation point... 眼尖的你應該可以發現只要 Vertex u 的 child(s) 都有 back edge 回到 Vertex u 的祖先, 則 Vertex u 就不會是 Articulation point! 

Implementation: 
底下類別實作了上面利用 DFS 找 Articulation point 的過程: (完整代碼) 

view plaincopy to clipboardprint?

1. package map.alg;  
2.   
3. import java.util.ArrayList;  
4. import java.util.List;  
5. import java.util.Set;  
6. import java.util.TreeSet;  
7.   
8. import map.Edge;  
9. import map.Graph;  
10. import map.Vertex;  
11. import map.enums.EEdgeType;  
12.   
13. public class FindArtiCulationPt {  
14.   
15.     /** 
16.      * BD: low(v)=min{v.d, min{low(w)|w is a child of v}, min{w.d| (v,w) is a back edge}} 
17.      * @param v 
18.      */  
19.     protected static void _CalcLow(Vertex v)  
20.     {  
21.         int low = Integer.MAX_VALUE;  
22.         for(Edge e:v.edgeSet)  
23.         {  
24.             if(e.to.d > v.d) // children  
25.             {  
26.                 _CalcLow(e.to);               
27.                 low = Math.min(low, e.to.low);  
28.             }  
29.             else if(e.type.equals(EEdgeType.Back)) low = Math.min(low, e.to.d); // back edge  
30.         }  
31.         v.low = Math.min(low, v.d);  
32.     }  
33.       
34.     public static Set Go(Graph g, Vertex s)  
35.     {  
36.         Set vset = new TreeSet();  
37.           
38.         // 1) Run DFS  
39.         DFS.Run(g, s);  
40.           
41.         // 2.1) 如果是root的話(開始做dfs的地方), 且有超過一個的 children 是articulation point  
42.         s.low = 1;  
43.         List childList = new ArrayList();  
44.         for(Edge e:s.edgeSet)  
45.         {  
46.             if(e.type.equals(EEdgeType.Tree)) {  
47.                 System.out.printf("\t[Test] Child=%s\n", e.to);  
48.                 childList.add(e.to);  
49.             }  
50.         }  
51.         if(childList.size()>1) vset.add(s);  
52.           
53.         // 2.2) 當有一個以上的小孩,   
54.         //      無法沿著它自己的後代及一條nontree edge (back edge)到達它的祖先的時候, 則為articulation point  
55.         for(Vertex v:childList) _CalcLow(v);          
56.         for(Vertex v:g.vtxMap.values())  
57.         {  
58.             for(Edge e:v.edgeSet)  
59.             {  
60.                 if(e.to.d>v.d && e.to.low>=v.d)  
61.                 {  
62.                     vset.add(v);  
63.                     break;  
64.                 }  
65.             }  
66.         }  
67.                   
68.         return vset;  
69.     }  
70. }  

Example: 
底下為該類別使用的一個範例: 

view plaincopy to clipboardprint?

1. public static void main(String[] args) {  
2.     Graph g = new Graph(false);  
3.     g.addVertice(0, 9);  
4.     g.addEdge(0, 1);  
5.     g.addEdge(1, 2); g.addEdge(1, 3);  
6.     g.addEdge(2, 4);  
7.     g.addEdge(4, 3);  
8.     g.addEdge(3, 5);  
9.     g.addEdge(5, 6); g.addEdge(5, 7);  
10.     g.addEdge(6, 7);  
11.     g.addEdge(7, 8); g.addEdge(7, 9);  
12.       
13.     Set vset = FindArtiCulationPt.Go(g, g.getVertex(3));  
14.     System.out.printf("\t[Info] Articulation Point:\n");  
15.     for(Vertex v:vset) System.out.printf("\t\t%s\n", v);  
16. }  

執行結果: 

[Info] Articulation Point:
1(Black)
3(Black)
5(Black)
7(Black)

Supplement: 
* [CSIE 1212] Data Structure and Algorithm - 4/9 Graph2 
* Articulation Vertex / Bridge 
* [ Intro Alg ] Elementary Graph Algorithms - Depth-first search