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.

An application of this algorithm is ordering a sequence of tasks given their dependencies on other tasks. In this application, there is a 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*).

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, but only after all of a node's *children* are visited. This ensures that parent nodes will be ordered before their child nodes, and honors the forward direction of edges in the ordering.

```
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)
```