Topological Sort in Graph | Simple DFS + Stack Solution in Python

Learn how to find a topological sort of a directed acyclic graph (DAG) using depth-first search (DFS) and a stack. Clear intuition, step-by-step guide, commented Python code, dry run, and Big-O analysis.

Here’s the [Problem Link] to begin with.

What does the problem ask?

You are given a directed acyclic graph (DAG) with V vertices (numbered 0…V-1) and a list of directed edges.
Your task is to return any valid topological ordering of the vertices, an ordering where every edge u → v appears with u before v.

Example

V = 6
Edges = [
  (5, 0), (5, 2),
  (4, 0), (4, 1),
  (2, 3), (3, 1)
]

One correct topological order is
5 4 2 3 1 0

Other valid orders exist; any that respect all edge directions is accepted.

Intuition & Approach

1. DFS explores forward edges.
   When DFS finishes exploring a node, all its outgoing neighbors are already placed somewhere before we push that node onto a stack.
2. Stack collects finished nodes.
   After we visit every node reachable from the start, we push the start node onto the stack.
3. Reverse the stack.
   If we pop elements (or simply reverse the stack list) we get a sequence where every parent appears before its children, exactly what we need.
4. Handle every component.
   The graph can have more than one disconnected part, so we start DFS from every unvisited vertex.

Code (original lines kept, only comments added)

class Solution:
    # DFS helper: visit node, then its children, then push node to stack
    def dfs(self, current_node, visited, stack, adj_list):
        visited[current_node] = 1                # mark as visited
        for adjNode in adj_list[current_node]:   # explore all outgoing edges
            if visited[adjNode] == 0:
                self.dfs(adjNode, visited, stack, adj_list)
        stack.append(current_node)               # post-order push

    def topoSort(self, V, edges):
        adj_list = [[] for _ in range(V)]        # build adjacency list
        for u, v in edges:                       # edge u → v
            adj_list[u].append(v)

        stack = []
        visited = [0 for _ in range(V)]          # 0 = not visited
        for i in range(0, V):                    # check every vertex
            if visited[i] == 0:
                self.dfs(i, visited, stack, adj_list)

        return stack[::-1]                       # reverse = topo order

Code explanation (step-by-step)

1. Adjacency list – converts edge pairs into lists for quick lookup.
2. visited array – keeps us from visiting a node twice.
3. Outer loop – starts DFS from any node still unvisited (covers all components).
4. Inside dfs()
   • Mark node visited.
   • Recursively visit each neighbor.
   • After children are done, push the node onto stack.
5. Return reversed stack for the final topological order.

Dry run on the sample graph

Reverse → 5 2 3 4 1 0 (also valid).

Complexity

Reason

• We visit each vertex once and scan each edge once → V + E.
• Adjacency list and recursion stack together store up to V + E items.

Conclusion

Topological sorting of a DAG can be done easily with DFS:

1. Build an adjacency list.
2. Perform a post-order DFS, pushing nodes onto a stack after visiting children.
3. Reverse the stack to get a valid ordering.

The method is linear, simple, and works for any directed acyclic graph.

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.