Topological order 拓扑排序

给定一个有向图，图节点的拓扑排序被定义为：

1. 对于每条有向边A--> B，则A必须排在B之前
2. 拓扑排序的第一个节点可以是任何在图中没有其他节点指向它的节点　　

找到给定图的任一拓扑排序

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

    //add nodes without parents to the queue
    Queue<DirectedGraphNode> q = new LinkedList<DirectedGraphNode>();
        for (DirectedGraphNode node : graph) {
            if (!map.containsKey(node)) {
                q.offer(node);
                result.add(node);
            }
    }

    while (!q.isEmpty()) {
        DirectedGraphNode node = q.poll();
        for (DirectedGraphNode n : node.neighbors) {
            map.put(n, map.get(n) - 1);
            if (map.get(n) == 0) {
                result.add(n);
                q.offer(n);
            }
        }
    }
    return result;
}