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 is5 4 2 3 1 0
Other valid orders exist; any that respect all edge directions is accepted.
Intuition & Approach
- 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. - Stack collects finished nodes.
After we visit every node reachable from the start, we push the start node onto the stack. - 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. - 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)
- Adjacency list – converts edge pairs into lists for quick lookup.
visited
array – keeps us from visiting a node twice.- Outer loop – starts DFS from any node still unvisited (covers all components).
- Inside
dfs()
- Mark node visited.
- Recursively visit each neighbor.
- After children are done, push the node onto
stack
.
- Return reversed
stack
for the final topological order.
Dry run on the sample graph
Action | stack (bottom → top) | visited |
---|---|---|
Start DFS at 0 ? No, unreachable yet | [] | … |
Start DFS at 1 ? reachable later | ||
Start at 2 ? No, will hit via 5 | ||
Start at 3 ? No | ||
Start at 4 | mark 4 | |
Visit 0 → push 0 | [0] | mark 0 |
Visit 1 → push 1 | [0,1] | mark 1 |
Push 4 | [0,1,4] | |
Start at 5 | mark 5 | |
Visit 0 (already done) | ||
Visit 2 | mark 2 | |
Visit 3 | mark 3 | |
Visit 1 (done) | ||
Push 3 | [0,1,4,3] | |
Push 2 | [0,1,4,3,2] | |
Push 5 | [0,1,4,3,2,5] |
Reverse → 5 2 3 4 1 0
(also valid).
Complexity
Measure | Value |
---|---|
Time | O(V + E) |
Space | O(V + E) |
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:
- Build an adjacency list.
- Perform a post-order DFS, pushing nodes onto a stack after visiting children.
- 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.