# Topological Sort

## Introduction

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 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). ## 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, 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.

### 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): 