# Topological Sorting
Aside from DFS and BFS, the most common graph concept that interviews will test is topological sorting. Topological sorting produces a linear ordering of nodes in a directed graph such that the direction of edges is respected.

A **topological sort** is an ordering of nodes for a directed acyclic graph (DAG) such that for every directed edge _uv_ from vertex _u_ to vertex _v_, _u_ comes before _v_ in the ordering.

## Example
An application of this algorithm is ordering a sequence of tasks given their dependencies on other tasks. In this application, there is an directed edge from _u_ to _v_ if task _u_ must be completed before task _v_ can start. For example, when cooking, we need to turn on the oven (task _u_) before we can bake the cookies (task _v_).

<img src="https://lh3.google.com/u/0/d/1-L8JMew3Q_00aj2w3TVobQjmTS6rwGQP=w2312-h1560-iv1"/>

## Implementation:
Topological sort is simply a modification of DFS. Topological sort simply involves running DFS on an entire graph and adding each node to the global ordering of nodes only after all of a node's children are visited. This ensures that parent nodes will be ordered before their child nodes honoring the forward direction of edges in the ordering.

### Graph with no cycles

from collections import deque

def top_sort(graph):
  sorted_nodes, visited = deque(), set()
  for node in graph.keys():
      if node not in visited:
        dfs(graph, node, visited, sorted_nodes)
  return list(sorted_nodes)
 

def dfs(graph, start_node, visited, sorted\_nodes):
  visited.add(start_node)
  if start_node in graph:
      neighbors = graph[start_node]
  for neighbor in neighbors:
      if neighbor not in visited:
          dfs(graph, neighbor, visited, sorted_nodes)
  sorted_nodes.appendleft(start_node)