Topological Sorting Show result

Given an directed graph, a topological order of the graph nodes is defined as follow:

• For each directed edge A-->B in graph, A must before B in the order list.
• The first node in the order can be any node in the graph with no nodes direct to it.

Find any topological order for the given graph.

Example

For graph as follow: 

The topological order can be:

[0, 1, 2, 3, 4, 5]

or

[0, 2, 3, 1, 5, 4]

or

....

首先明白两个概念: 入度 表示有向图里有多少箭头指向该点  出度 : 有多少箭头指出该点

解题: 先把入度为0的点加入result中, 然后裁掉该点--->该点所有邻结点的入度都-1; 然后再找出入度为0的点 加入result......

/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 * };
 */
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) {
        ArrayList<DirectedGraphNode> result = new ArrayList<DirectedGraphNode>();
        HashMap<DirectedGraphNode, Integer> map = new HashMap();
        for (DirectedGraphNode node : graph) {//找到所有点的入度值存入hash
            for (DirectedGraphNode neigh : node.neighbors) {
                if (map.containsKey(neigh)) {
                    map.put(neigh, map.get(neigh) + 1);
                } else {
                    map.put(neigh, 1);
                }
            }
        }
        Queue<DirectedGraphNode> queue = new LinkedList<DirectedGraphNode>();// 找到入度为0的点node存入queue
        for (DirectedGraphNode node : graph) {
            if (!map.containsKey(node)) {
                queue.offer(node);
                result.add(node);
            }
        }
        while (!queue.isEmpty()) {//把node的邻接点入度都-1, 找到入度为0的接点加入queue 
            DirectedGraphNode node = queue.poll();
            for (DirectedGraphNode n : node.neighbors) {
                map.put(n, map.get(n) - 1);
                if (map.get(n) == 0) {
                    queue.offer(n);
                    result.add(n);
                } 
            }
        }
        return result;
    }
}