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


  • 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.

Topological Sort

  • 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]


from Graph import Graph
class TopologicalSort:
def __init__(self, g):
self.post_order = []
self.marked = {}
def init_marked(self, vertices):
for vertex in vertices:
self.marked[vertex] = False
def perform_dfs(self, g):
for vertex in g.get_vertices():
if(vertex in self.marked and not self.marked[vertex]):
self.dfs(g, vertex)
def dfs(self, g, v):
self.marked[v] = True
for w in g.get_adjacent(v):
w_id = w.get_id()
if(w_id in self.marked and not self.marked[w_id]):
self.dfs(g, w_id)
# we have completed dfs on v
# returns the reversed post order
def get_reverse_post_order(self):
return self.post_order[::-1]


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.