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

or

By clicking below, you agree to our terms of service.

Sign in via Facebook
Sign in via Twitter
Sign in via GitHub
Sign in via Dropbox
Sign in with Wallet

Wallet
(
)

Connect another wallet
New to HackMD? Sign up