Topological sort

这个听起来是个非常高深的算法，但实际上只是BFS的另一种应用罢了
核心思想就是通过图中最外层的节点往里走，一层一层递进。这里有个indegree的概念（入度？）indegree就是一个描述“层”的数组。也就是说最外层的indegree就是0，因为indegree代表的就是有多少个指向该节点的节点。所以叫indegree. 那么怎么找到indegree呢？通过courseSchedule这道题，你就是遍历所有的prerequisite的数组，然后每次遇到prerequisite的课，就把它对应的indegree加一。

for (int i = 0; i < prerequisite.length; i++) {
  int start = prerequisite[i][1], end = prerequisite[i][0]; 
  //注意这里prerequisite 的结构，[0,1]代表1的先修课是0，所以start 是prerequisite[i][0], end 是prerequisite[i][1];
  graph.putIfAbsent(start, new ArrayList<>());
  graph.get(start).add(end); //把start之后的课程计入到它对应的队列中
  indegree[end]++; //增加indegree
}

做完上面这步之后你就可以安心用BFS来遍历所有的外围节点了。同样用Queue，然后把indegree为0的节点加入queue中，开始遍历（跟正常的level order traversal一样）

Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < indegree.length; i++) {
  if (indegree[i] == 0) q.add(i);
}
int count = 0; //这个count就是为了记录有多少个indegree为0，然后比较总共课程数量，即可知道你是否能够上完全部的课（这张图有没有环，或者说是不是一个DAG，有向无环图）
while (!q.isEmpty()) {
  int cur = q.poll();
  count++;
  for (int nei : graph.getOrDefault(cur, new ArrayList<>()) {
    if (--indegree[nei] == 0)
      q.add(nei);
  }
}
return count == numsCourses;

下面是整段代码：

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        int[] indegree = new int[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            int end = prerequisites[i][0], start = prerequisites[i][1];
            graph.putIfAbsent(start, new ArrayList<>());
            graph.get(start).add(end);
            indegree[end]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) q.add(i);
        }
        int count = 0;
        while(!q.isEmpty()) {
            int cur = q.poll();
            count++;
            for (int next : graph.getOrDefault(cur, new ArrayList<>()))
                if (--indegree[next] == 0)
                    q.add(next);
        }
        return count == numCourses;
    }

时空复杂度

O（N+E） N就是有多少节课，你遍历了至少3遍，E就是有多少prerequisite
空间复杂度也是O（N+E） 因为你要用map或者ArrayList来存起始课和之后的关系。