拓扑排序， BFS 做法

无论是 directed 还是 undirected Graph，其 BFS 的核心都在于 "indegree"，处理顺序也多是从 indegree 最小的开始，从外向内。

我们先用一个 HashMap 统计下所有节点的 indegree; 值越高的，在拓扑排序中位置也就越靠后，因为还有 N = current indegree 的 parent node 们没有处理完。

因此在循环最开始，我们可以把所有 indegree = 0 (也即不在 hashmap 中) 的节点加到 list 中，也作为 BFS 的起点。

在 BFS 过程中，我们依次取出队列里取出节点 node 的 neighbors， next，并且对 next 对应的 indegree -1，代表其 parent node 已经被处理完，有效 indegree 减少。

当-1之后如果 next 的 indegree 已经是 0 ， 则可以加入 list，并且作为之后 BFS 中新的起始节点。

从 Course Schedule 的 BFS 做法学到的经验是，如果图中有环，会有环上的 node 永远无法减到 indegree = 0 的情况，导致一些 node 没有被访问。

这也是当初面试被问到的为什么 JVM 不只靠 reference counting 来做 GC，就是因为有环的时候，indegree 不会减到 0.

Topological Sort

 public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        // write your code here
        Queue<DirectedGraphNode> queue = new LinkedList<DirectedGraphNode>();
        HashMap<DirectedGraphNode, Integer> degree = new HashMap<DirectedGraphNode, Integer>();
        for(DirectedGraphNode node : graph){
            for(DirectedGraphNode n : node.neighbors){
                if(degree.containsKey(n)) degree.put(n, degree.get(n)+1);
                else degree.put(n, 1);
            }
        }

        ArrayList<DirectedGraphNode> ans = new ArrayList<DirectedGraphNode>();
        for(DirectedGraphNode n : graph)
            if(!degree.containsKey(n)) {queue.offer(n);}

        while(!queue.isEmpty()){
            DirectedGraphNode cur = queue.poll();
            ans.add(cur);
            for(DirectedGraphNode neighbor : cur.neighbors){
                if(degree.containsKey(neighbor)){
                    degree.put(neighbor, degree.get(neighbor)-1);
                    if(degree.get(neighbor)==0){
                        queue.offer(neighbor);
                        degree.remove(neighbor);
                    }
                }
            }
        }
        return ans;
    }