Topological sort

Topological sort 就是有相依性的一種排序，當"誰要在誰前面" 就是拓樸排序要上場

概念就是先計算出所有點的 in-degree (或是積分)後，再從最少或最大 in-degree 一個一個挑出來

然後把這個點可以到的地方的點的 in-degree扣掉，這樣就可以在往下一步前進，

過程用 queue 把下一回合要輸出的點記下來

這種 list 裝的圖的複雜度是 O(V + E)

如果是用矩陣裝的圖，那就會是 O(V^2) (因為要遍歷每個矩陣點看是不是0)

public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
    // write your code here
    ArrayList<DirectedGraphNode> results = new ArrayList<>();
    if (graph.size() == 0) {
        return results;
    }

    //calculate in and out degrees
    HashMap<DirectedGraphNode, Integer> inDegrees = new HashMap<>();

    for (int i = 0; i < graph.size(); i++) {
        DirectedGraphNode node = graph.get(i);
        if (!inDegrees.containsKey(node)) {
            inDegrees.put(node, 0);
        }
        for (int j = 0; j < node.neighbors.size(); j++) {
            DirectedGraphNode neighbor = node.neighbors.get(j);
            if (inDegrees.containsKey(neighbor)) {
                inDegrees.put(neighbor, inDegrees.get(neighbor)+1);
            } else {
                inDegrees.put(neighbor, 1);
            }
        }
    }

    Queue<DirectedGraphNode> Q = new LinkedList<>();
    for (Map.Entry<DirectedGraphNode, Integer> entry : inDegrees.entrySet()) {
        if (entry.getValue() == 0) {
            Q.offer(entry.getKey());
            // break;   <- all node with zero in-degree should be put in queue initially
        }
    }

    while (!Q.isEmpty()) {
        DirectedGraphNode node = Q.poll();
        results.add(node);
        for (int i = 0; i < node.neighbors.size(); i++) {
            DirectedGraphNode neighbor = node.neighbors.get(i);
            inDegrees.put(neighbor, inDegrees.get(neighbor)-1);
            if (inDegrees.get(neighbor) == 0) {
                Q.offer(neighbor);
            }
        }
    }

    return results;
}