210题的 DFS 解法 好难理解

大家觉得这个解法理解吗？

1. class Solution {
   
2. 
   
3.     public int[] findOrder(int numCourses, int[][] prerequisites) {
   
4. 
   
5.         ArrayList < Integer > [] graph = new ArrayList[numCourses];
   
6.         
   
7.         for (int i = 0; i < numCourses; i++) {
   
8.             graph[i] = new ArrayList < Integer > ();
   
9.         }
   
10.         
    
11.         for (int i = 0; i < prerequisites.length; i++) {
    
12.         
    
13.             graph[prerequisites[i][1]].add(prerequisites[i][0]);
    
14.             
    
15.         } // build graph & root[];
    
16.         
    
17.         Boolean[] visited = new Boolean[numCourses];
    
18.         
    
19.         List < Integer > ans = new ArrayList < Integer > ();
    
20.    
    
21.           for (int i = 0; i < visited.length; i++) {
    
22.       
    
23.               if( visited[i] == null){
    
24.                 if ( !dfs(i, graph, ans, visited) ) return new int[0];
    
25.             }
    
26.             
    
27.         }
    
28.         
    
29.         if (ans.size() != numCourses) return new int[0];
    
30.         
    
31.         int[] res = new int[ans.size()];
    
32.         
    
33.         int index = 0;
    
34.         
    
35.         for (int i: ans) {
    
36.             res[index++] = i;
    
37.         }
    
38.         
    
39.         return res;
    
40.     }
    
41.    
    
42.     public boolean dfs(int cur, ArrayList < Integer > [] graph, List < Integer > ans, Boolean[] visited) {
    
43.         
    
44.         if ( visited[cur] != null ) return visited[cur];   //  来判断是否有环!!!!!!!!!!!!!!!
    
45.         
    
46.         visited[cur] = false; // 这个课还没上过，但被检查过
    
47.         
    
48.         for (int c: graph[cur]) {   // 指望着 cur 的 课程
    
49.             if ( !dfs(c, graph, ans, visited) ) return false;
    
50.         }
    
51.         
    
52.         ans.add(0, cur);  // 最后再加上最开始的。
    
53.         
    
54.         visited[cur] = true;  // 这个课已经上了
    
55.         
    
56.         return true;
    
57.     }
    
58. }
    
59. 
    
60. 
    
61. 
    
62. 
    
63. 
    
64. 
    
65. 
    
66. 
    
67. 
    
68. 
    
69. 
    

复制代码

刚刷完这题，我也觉得讨论里的答案都很难理解，就算是硬理解了 自己也写不出来。看了花花酱的答案 感觉还挺容易理解的。btw看不到你贴出来的答案

挺好理解的呀，就是topological sort dfs的写法呀

其实和BFS是两个方向，BFS+queue的解法是从indegree为0的点开始出发，所通到的点in degree 减一，把所有入度为0的点当做新的起点。图的问题，既然可以通过入度解决，对称来看，也可以通过出度。DFS最先加入最终结果的，一定是出度为0的点，当当前节点的孩子都被遍历完，当前节点加入结果，也就是说当前节点的出度变为0。

dfs=树里面的后序遍历

额。。。就典型的topological sort呗，楼主可以复习一下这里。。

DFS解法：dependency要全部完成才能执行自己的node