Learn how to perform topological sorting of a DAG using Kahn’s algorithm (BFS based). Clear steps, commented Python code, dry-run example, and Big-O complexity.
Here’s the [Problem Link] to begin with.
What does the problem ask?
Given a directed acyclic graph (DAG) with V
vertices (0 … V-1
) and a list of directed edges, return any order of the vertices such that for every edge u → v
, vertex u
appears before v
in the list.
Example
V = 6
Edges = [
(5, 0), (5, 2),
(4, 0), (4, 1),
(2, 3), (3, 1)
]
A correct topological order is 5 4 2 3 1 0
.
(Other valid orders are possible.)
Intuition & Approach
Kahn’s algorithm (BFS idea)
- Indegree
For every vertex count how many incoming edges it has.
Vertices with indegree 0 have no prerequisites; they can start the order. - Queue of ready vertices
Put all indegree-0 vertices in a queue. - Process the queue
- Pop a vertex, add it to the answer list.
- For each outgoing edge
u → v
, reducev
’s indegree by 1. - If
v
’s indegree becomes 0, pushv
into the queue.
- Repeat until the queue is empty.
If we outputV
vertices, we have a valid topological order.
(If fewer—this would mean the graph had a cycle, but the problem guarantees a DAG.)
Code
from collections import deque
class Solution:
def topoSort(self, V, edges):
adj_list = [[] for _ in range(V)] # adjacency list
indegrees = [0 for _ in range(V)] # incoming edge counts
# build graph and indegree array
for u, v in edges: # edge u → v
adj_list[u].append(v)
indegrees[v] += 1
queue = deque() # vertices ready to be processed
result = [] # final topological order
# add all starting points (indegree == 0)
for i in range(V):
if indegrees[i] == 0:
queue.append(i)
# BFS over the DAG
while queue:
current_node = queue.popleft()
result.append(current_node)
# remove current_node’s edges
for adjNode in adj_list[current_node]:
indegrees[adjNode] -= 1
if indegrees[adjNode] == 0: # new node becomes ready
queue.append(adjNode)
return result # contains V vertices in order
Code walkthrough
- Build
adj_list[u]
holds all vertices reachable fromu
.indegrees[v]
counts how many edges come intov
.
- Initial queue
All vertices with no incoming edges can be placed first in the order. - Loop
- Take the next ready vertex.
- Add it to
result
. - “Delete” its outgoing edges by lowering each neighbor’s indegree.
- When a neighbor’s indegree hits 0, push it onto the queue.
- Finish
When the queue is empty,result
has one valid topological order.
Dry run on the sample graph
Step | Queue | Result | indegrees (key changes) |
---|---|---|---|
Start | [4, 5] | [] | 4→0,5→0 |
Pop 4 | [5] | [4] | 0→1,1→1 |
Process edges 4→0, 4→1 | [5] (no new zeros) | ||
Pop 5 | [] | [4,5] | 0→0,2→1 |
Edge 5→0 lowers indegree(0) to 0 → queue [0] | |||
Edge 5→2 lowers indegree(2) to 0 → queue [0,2] | |||
Pop 0 | [2] | [4,5,0] | (0 has no children) |
Pop 2 | [] | [4,5,0,2] | 3→0 → queue [3] |
Pop 3 | [] | [4,5,0,2,3] | 1→0 → queue [1] |
Pop 1 | [] | [4,5,0,2,3,1] | done |
Final order: 4 5 0 2 3 1
—valid.
Complexity
Measure | Value |
---|---|
Time | O(V + E) |
Space | O(V + E) |
We look at each vertex and each edge once. We store the adjacency list (E
) and two arrays of size V
.
Conclusion
Kahn’s algorithm uses a simple queue and indegree counts to produce a topological order with breadth-first style processing. It is intuitive, runs in linear time, and is often the first choice for scheduling tasks with dependencies.
For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.