Topological Sorting

思路：

三部曲

1. indegree
把所有node的入度算出来，也就是有多少条边进入它。放进hashmap里面。

2. get start nodes
把所有入度为零的点找出来。

3. bfs
每一次进入下一层，把下一层节点的入度减1。 当节点入度为0的时候才加入到queue和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) {  
     // write your code here  
     ArrayList<DirectedGraphNode> result = new ArrayList<>();  
     // 1. indegree  
     Map<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);  
         }  
       }  
     }  
     // 2. get starting nodes  
     Queue<DirectedGraphNode> queue = new LinkedList<>();  
     for(DirectedGraphNode node: graph)  
     {  
       if(!map.containsKey(node))  
       {  
         queue.add(node);      
         result.add(node);  
       }  
     }  
     // 3. bfs  
     while(!queue.isEmpty())  
     {  
       DirectedGraphNode curNode = queue.poll();  
       for(DirectedGraphNode neighbor: curNode.neighbors)  
       {  
         map.put(neighbor, map.get(neighbor)-1);  
         if(map.get(neighbor) == 0)  
         {  
           queue.offer(neighbor);  
           result.add(neighbor);  
         }  
       }  
     }  
     return result;  
   }  
 }