# Topological Sorting

{% tabs %}
{% tab title="Java" %}

```java
public class Solution {
    public ArrayList<DirectedGraphNode> topSort(ArrayList<DirectedGraphNode> graph) {
        HashMap<DirectedGraphNode, Integer> map = new HashMap();
        for (DirectedGraphNode node : graph) {
            if(!map.containsKey(node)) map.put(node, 0);
            for (DirectedGraphNode neighbor : node.neighbors) {
                if (map.containsKey(neighbor)) {
                    map.put(neighbor, map.get(neighbor) + 1);
                } else {
                    map.put(neighbor, 1); 
                }
            }
        }
        ArrayList<DirectedGraphNode> result = new ArrayList<DirectedGraphNode>();
        for(DirectedGraphNode node : graph){
            if(!map.containsKey(node) || map.get(node) == 0)dfs(node, map, graph, result);
        }
        return result;
    }
    
    public void dfs(DirectedGraphNode node, 
                    HashMap<DirectedGraphNode, Integer> map, 
                    ArrayList<DirectedGraphNode> graph, 
                    ArrayList<DirectedGraphNode> result){
        map.put(node, -1);
        result.add(node);
        for(DirectedGraphNode neighbor : node.neighbors){
            map.put(neighbor, map.get(neighbor) - 1);
            if(map.get(neighbor) == 0) dfs(neighbor, map, graph, result);
        }
        return ;
    }
}
```

{% endtab %}

{% tab title="Python" %}

```python
class Solution:
    """
    @param: graph: A list of Directed graph node
    @return: Any topological order for the given graph.
    """
    def topSort(self, graph):

        #define indegree with dict
        indegree = dict((i,0) for i in graph)
        for i in graph:
            for j in i.neighbors:
                indegree[j]+=1
                
        #define queue and put the 0 degree nodes
        import Queue
        q = Queue.Queue()
        for i in graph:
            if indegree[i] == 0:
                q.put(i)
                
        #result and bfs       
        result = []        
        while not q.empty():
            node = q.get()
            result.append(node)
            for j in node.neighbors:
                indegree[j]-=1
                if indegree[j] == 0:
                    q.put(j)
                    
        return result
```

{% endtab %}
{% endtabs %}

![](https://2784211123-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M-ELB26IpzCEJWSDi0m%2F-M-ELbsic2B8wwsarT-C%2F-M-EMqc6UhBUlpM3zyHy%2F1580805867266.jpg?alt=media\&token=11a20b67-9e32-4c02-bf02-c405dac8ef0f)