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).
- 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.
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]
Topological 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.