Topological Sort (Kahn’s Algorithm) – Simple BFS Solution in Python

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)

1. Indegree
   For every vertex count how many incoming edges it has.
   Vertices with indegree 0 have no prerequisites; they can start the order.
2. Queue of ready vertices
   Put all indegree-0 vertices in a queue.
3. Process the queue
   • Pop a vertex, add it to the answer list.
   • For each outgoing edge u → v, reduce v’s indegree by 1.
   • If v’s indegree becomes 0, push v into the queue.
4. Repeat until the queue is empty.
   If we output V 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

1. Build
   • adj_list[u] holds all vertices reachable from u.
   • indegrees[v] counts how many edges come into v.
2. Initial queue
   All vertices with no incoming edges can be placed first in the order.
3. 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.
4. Finish
   When the queue is empty, result has one valid topological order.

Dry run on the sample graph

Final order: 4 5 0 2 3 1 —valid.

Complexity

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.