[ Alg info ] Topology sort using DFS

Preface: 
考慮你有修課的順序如下, 箭頭說明該課程有相依性. 如 計概->計組 指 "計概" 要先修完後才能修 "計組": 
 

而我們的問題是要找出一種修課的順序可以滿足上面拓撲圖的要求, 而這類的問題稱之為 Topology sort. 底下是 wiki 上面較詳細的說明: 

In computer science, a topological sort (sometimes abbreviated topsort or toposort) or topological ordering of a directed graph is a linear ordering of its verticessuch that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks.

上面說明的 vertex 就可以看成課程, 而 edge 說明課程間的相依性. 而這樣的 Graph 必須滿足 DAG (directed acyclic grapn) 而這類問題的圖形也稱為 AOV (activity on vertex). 

Using DFS as Solution: 
要解決這個問題一個常見的解法是使用 DFS (Deep First Search). 在跑 DFS 的過程中每個 vertex 都會產生所謂的 discover time 與 finish time. 而 finish time 較小的 vertex 相對 finish time 較大的 vertex 在圖形中較 deep 的位置. 底下是 DFS 的 pseudo code: 
 

上面的 u.f 指的即是 finish time. 因此直覺的可以將 vertex 依其 finish time 以 decreasing order 排列後, 取出的的順序便是其中一個可能的解法. (finish time 較大的先取出來, 即由 root 依序往其 leaf 移動). 而其實 finish time 大的先取; 小的後取 的概念類似於 ADT Stack 的想法 (FILO - First in Last out 或是 LIFO - Last in First out), 因此下面的實作中當每個 vertex 狀態由 Gray->Black (finish), 便將之加入 stack, 最後將該 stack 返回並依序取出 vertex 便是 Topology sort 的結果. 

Implementation: 
下面類別 TopologicalSort 實作了使用 DFS 的 Topology sort: (完整代碼) 

view plaincopy to clipboardprint?

1. package map.alg;  
2.   
3. import java.util.Stack;  
4.   
5. public class TopologicalSort {  
6.       
7.     public static void _DFS_Visit(Stack stack, Vertex v)  
8.     {  
9.         v.status = EStatus.Gray;  
10.         // Discover       
11.         for(Edge e:v.edgeSet)  
12.         {  
13.             if(e.to.status.equals(EStatus.White)) _DFS_Visit(stack, e.to);  
14.         }  
15.         // Finish  
16.         v.status = EStatus.Black;  
17.         stack.add(v);  
18.     }  
19.   
20.     /** 
21.      * Alg: 
22.      *  1. Run DFS(G) 
23.      *  2. v.f 越小說明其在 DFS 是處於較 deep 的位置 (相依性重). 因此它應該較後面處理. 
24.      *     這邊我們使用 stack 來存放處理完畢的 vertex (依 finish 先後順序放入 stack) 
25.      *  3. 從 Stack 取出的順序即是 Topological sort 的順序. 
26.      *   
27.      * Ref: 
28.      *  - Wiki Topology sort  
29.      *    http://en.wikipedia.org/wiki/Topological_sorting 
30.      *     
31.      * @param g 
32.      * @return 
33.      */  
34.     public static Stack Go(Graph g)  
35.     {  
36.         // 0) Initialize  
37.         Stack stack = new Stack();        
38.         for(Vertex v:g.vtxMap.values())  
39.         {  
40.             v.pi = null;  
41.             v.status = EStatus.White;  
42.         }  
43.           
44.         // 1) Start DFS       
45.         for (Vertex v : g.vtxMap.values()) {              
46.             if (v.status.equals(EStatus.White)) {  
47.                 _DFS_Visit(stack, v);                 
48.             }  
49.         }  
50.         return stack;   
51.     }  
52. }  

Example: 
底下是使用上面類別來解決一開始的課程問題, 輸出為其中一個可能的修課順序: 

view plaincopy to clipboardprint?

1. public static void main(String args[])  
2. {  
3.     // 0) Prepare Graph  
4.     Graph g = new Graph(true); // Directed graph  
5.               
6.     g.addVertex("微積分上"); g.addVertex("微積分下"); g.addVertex("機率");  
7.     g.addVertex("計概"); g.addVertex("計組"); g.addVertex("作業系統");  
8.     g.addVertex("計程"); g.addVertex("演算法上"); g.addVertex("演算法下");  
9.     g.addVertex("計算機網路");  
10.       
11.     g.addEdge("微積分上", "微積分下");  
12.     g.addEdge("微積分下","機率");  
13.     g.addEdge("機率", "計算機網路");  
14.     g.addEdge("計概", "計組"); g.addEdge("計組", "作業系統"); g.addEdge("作業系統", "計算機網路");  
15.     g.addEdge("計程", "演算法上"); g.addEdge("演算法上", "演算法下"); g.addEdge("演算法下", "作業系統");  
16.       
17.     Stack stack = TopologicalSort.Go(g);  
18.     System.out.printf("\t[Info] Topological Sort: %s", stack.pop());  
19.     while (!stack.isEmpty()) {  
20.         System.out.printf("->%s", stack.pop());  
21.     }  
22.     System.out.println();  
23. }  

輸出如下: 

[Info] Topological Sort: 計程(Black)->計概(Black)->計組(Black)->演算法上(Black)->演算法下(Black)->微積分上(Black)->微積分下(Black)->機率(Black)->作業系統(Black)->計算機網路(Black)

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