拓扑排序, 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 class Solution {
    /**
     * @param graph: A list of Directed graph node
     * @return: Any topological order for the given graph.
     */    
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        // write your code here
        ArrayList<DirectedGraphNode> list = new ArrayList<DirectedGraphNode>();

        // Key : node
        // Value : current in-degree count
        HashMap<DirectedGraphNode, Integer> map = new HashMap<>();
        for(DirectedGraphNode node : graph){
            for(DirectedGraphNode neighbor : node.neighbors){
                if(!map.containsKey(neighbor)){
                    map.put(neighbor, 1);
                } else {
                    map.put(neighbor, map.get(neighbor) + 1);
                }
            }
        }

        // Now we know each node's in-degree (out is trivial)
        Queue<DirectedGraphNode> queue = new LinkedList<>();

        Iterator<DirectedGraphNode> iter = graph.iterator();
        while(iter.hasNext()){
            DirectedGraphNode node = iter.next();
            // get all nodes without indegree
            if(!map.containsKey(node)){
                queue.offer(node);
                list.add(node);
            }
        }

        while(!queue.isEmpty()){
            DirectedGraphNode node = queue.poll();
            for(DirectedGraphNode next : node.neighbors){
                // node "next"'s parent has been processed
                map.put(next, map.get(next) - 1);
                if(map.get(next) == 0){
                    list.add(next);
                    queue.offer(next);
                } 
            }
        }

        return list;
    }
}