# Topological Sort

Our goal in topological sort is this:

Given a set of tasks to be completed with precedence constraints (eg: module prerequisites), in which order should we schedule the tasks?

Topological sort works on *Directed Acyclic Graphs (DAG)*.

## #

Process- We apply DFS from a source node.
- Return the vertices in reverse postorder.

We add the vertex into a stack when we cannot DFS further from it anymore. We need to ensure *all* vertices are visited. To do so, we run a for loop through all vertices to see if they are marked. Else, we perform dfs starting from that vertex.

**Post-Order**

The order in which we were "finished" with the vertices when performing DFS. Reversing this order gives us the *topological order*.

- 0 -> 1 -> 4 (done -> add to stack) -> 1 (done) -> 0
- 0 -> 5 -> 2 (done) -> 5 (done) -> 0 (done)
- We pick one of the other remaining vertices. 3 -> 6 (done)
- 3 (done)
- Final stack: [4,1,2,5,0,6,3]
- Topological Sort: [3,6,0,5,2,1,4]

## #

Implementation## #

AnalysisTopological sort has a time complexity of `O(E + V)`

where `V`

is the number of vertices in the graph and `E`

is the number of edges.