Topological Sorting is very important, almost every company has a question related to it.

Goal: To find an proper order making the front nodes are independent from the rest.

Degree: In-degree: how many edges points to this node. Out-Degree: how may edges points out from this node. In Topological Sorting, we only care about in-degree.

Step:

1) Summarize in-degree: keep a hashmap to add the node which indegree is larger than 1.

2) Put all the zero in-degree to a queue. (We can loop the list find the nodes that is not in the hashmap.)

3) Poll those node out, all this nodes neighbors' in-degree minus 1. If then the in-degree equals to 0, put it into the queue. 

If all the nodes come out, this graph could do a Topological Sorting. Because if there is cycle dependency, it cannot do Topological Sorting. 

BSF doesn't need to hashMap to keep which node has been visit, because we use in-dgree to track. Only the in-degree is 0, it will be put in the queue. This make sure there are no duplicates. 

/** * Definition for Directed graph. * class DirectedGraphNode { *     int label; *     ArrayList
     
       neighbors; *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList
      
       (); } * }; */public class Solution {    /**     * @param graph: A list of Directed graph node     * @return: Any topological order for the given graph.     */        public ArrayList
       
         topSort(ArrayList
        
          graph) {        // write your code here        ArrayList
         
           rst = new ArrayList
          
           (); if (graph == null) { return rst; } HashMap
           
             degrees = initalizeDegreeMap(graph); Queue
            
              q = initializeQueue(graph, degrees); while (!q.isEmpty()) { DirectedGraphNode node = q.poll(); rst.add(node); for (DirectedGraphNode neighbor : node.neighbors) { if (degrees.containsKey(neighbor)) { int inDegree = degrees.get(neighbor) - 1; if (inDegree == 0) { q.offer(neighbor); } degrees.put(neighbor, inDegree); } } } return rst; } private HashMap
             
               initalizeDegreeMap(ArrayList
              
                graph) { HashMap
               
                 degrees = new HashMap<>(); for (DirectedGraphNode node : graph) { for (DirectedGraphNode neighbor : node.neighbors) { if (!degrees.containsKey(neighbor)) { degrees.put(neighbor, 1); } else { degrees.put(neighbor, degrees.get(neighbor) + 1); } } } return degrees; } private Queue
                
                  initializeQueue(ArrayList
                 
                   graph, HashMap
                  
                    degrees) { Queue
                   
                     q = new LinkedList
                    
                     (); for (DirectedGraphNode node : graph) { if (!degrees.containsKey(node)) { q.offer(node); } } return q; }}