Topological Sort Using DFS and BFS (Kahn's Algorithm)

Key Insights

Topological sort orders vertices in a directed acyclic graph (DAG) such that for every edge (u, v), vertex u appears before v—essential for dependency resolution in build systems, task schedulers, and package managers.
DFS-based topological sort uses reverse post-order traversal and is simpler to implement, while Kahn’s algorithm (BFS-based) naturally detects cycles and can enumerate all valid orderings.
Both algorithms run in O(V + E) time and space, but Kahn’s algorithm is often preferred in production systems because it fails fast on cycles and processes nodes in a more intuitive “ready when dependencies are met” manner.

Introduction to Topological Sorting

Topological sorting answers a fundamental question in computer science: given a set of tasks with dependencies, in what order should we execute them so that every task runs only after its prerequisites complete?

Formally, a topological sort of a directed acyclic graph (DAG) produces a linear ordering of vertices such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. This ordering isn’t unique—most DAGs have multiple valid topological orderings.

You encounter topological sort constantly in real systems:

Build systems like Make, Bazel, and Gradle determine compilation order
Package managers like npm, pip, and apt resolve installation sequences
Task schedulers order jobs with dependencies in CI/CD pipelines
Course planning systems ensure prerequisites are taken before advanced courses
Spreadsheet engines calculate cells in dependency order

The constraint that the graph must be acyclic is non-negotiable. A cycle means circular dependencies—task A requires B, B requires C, and C requires A. No valid ordering exists.

Prerequisites and Graph Representation

We’ll use an adjacency list representation, which provides O(1) edge addition and efficient neighbor iteration. Here’s our foundation:

from collections import defaultdict, deque
from typing import List, Set

class Graph:
    def __init__(self, vertices: int):
        self.V = vertices
        self.adj = defaultdict(list)
    
    def add_edge(self, u: int, v: int) -> None:
        """Add directed edge from u to v (u must come before v)."""
        self.adj[u].append(v)
    
    def get_neighbors(self, v: int) -> List[int]:
        return self.adj[v]

class Graph {
  constructor(vertices) {
    this.V = vertices;
    this.adj = new Map();
    for (let i = 0; i < vertices; i++) {
      this.adj.set(i, []);
    }
  }

  addEdge(u, v) {
    this.adj.get(u).push(v);
  }

  getNeighbors(v) {
    return this.adj.get(v) || [];
  }
}

The edge direction matters: add_edge(A, B) means A is a prerequisite for B, so A must appear before B in any valid ordering.

DFS-Based Approach (Reverse Post-Order)

The DFS approach exploits a key insight: when we finish exploring a vertex (all its descendants have been visited), that vertex can safely appear after all vertices reachable from it. By collecting vertices in the order we finish them and reversing, we get a valid topological order.

def topological_sort_dfs(graph: Graph) -> List[int]:
    visited = set()
    stack = []
    
    def dfs(v: int) -> None:
        visited.add(v)
        for neighbor in graph.get_neighbors(v):
            if neighbor not in visited:
                dfs(neighbor)
        # Post-order: add to stack after all descendants processed
        stack.append(v)
    
    # Process all vertices (handles disconnected components)
    for v in range(graph.V):
        if v not in visited:
            dfs(v)
    
    # Reverse post-order gives topological order
    return stack[::-1]

Why does this work? When we add a vertex to the stack, we’ve already processed all vertices reachable from it. Those vertices are already in the stack, meaning they’ll appear later in the reversed result. This guarantees our vertex comes before its dependents.

For production code, an iterative version avoids stack overflow on deep graphs:

def topological_sort_dfs_iterative(graph: Graph) -> List[int]:
    visited = set()
    result = []
    
    for start in range(graph.V):
        if start in visited:
            continue
            
        # Stack holds (vertex, iterator over neighbors)
        stack = [(start, iter(graph.get_neighbors(start)))]
        visited.add(start)
        
        while stack:
            v, neighbors = stack[-1]
            
            try:
                neighbor = next(neighbors)
                if neighbor not in visited:
                    visited.add(neighbor)
                    stack.append((neighbor, iter(graph.get_neighbors(neighbor))))
            except StopIteration:
                # All neighbors processed, add to result
                stack.pop()
                result.append(v)
    
    return result[::-1]

The iterative version maintains an explicit stack with the current vertex and an iterator over its unvisited neighbors. When the iterator exhausts, we’ve finished that vertex.

BFS-Based Approach (Kahn’s Algorithm)

Kahn’s algorithm takes a different perspective: start with vertices that have no prerequisites (in-degree zero), process them, remove their outgoing edges, and repeat. Vertices become “ready” when all their dependencies have been processed.

def topological_sort_kahn(graph: Graph) -> List[int]:
    # Calculate in-degrees
    in_degree = [0] * graph.V
    for v in range(graph.V):
        for neighbor in graph.get_neighbors(v):
            in_degree[neighbor] += 1
    
    # Initialize queue with zero in-degree vertices
    queue = deque()
    for v in range(graph.V):
        if in_degree[v] == 0:
            queue.append(v)
    
    result = []
    
    while queue:
        v = queue.popleft()
        result.append(v)
        
        # "Remove" edges by decrementing in-degrees
        for neighbor in graph.get_neighbors(v):
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    # Cycle detection: if we didn't process all vertices, cycle exists
    if len(result) != graph.V:
        raise ValueError("Graph contains a cycle - no valid topological order")
    
    return result

Kahn’s algorithm has a built-in cycle detector. If a cycle exists, some vertices will never reach in-degree zero because they’re waiting on each other. We simply check if we processed all vertices:

def has_cycle_kahn(graph: Graph) -> bool:
    in_degree = [0] * graph.V
    for v in range(graph.V):
        for neighbor in graph.get_neighbors(v):
            in_degree[neighbor] += 1
    
    queue = deque(v for v in range(graph.V) if in_degree[v] == 0)
    processed = 0
    
    while queue:
        v = queue.popleft()
        processed += 1
        for neighbor in graph.get_neighbors(v):
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    
    return processed != graph.V

Complexity Analysis and Comparison

Both algorithms share the same asymptotic complexity:

Aspect	DFS	Kahn’s (BFS)
Time	O(V + E)	O(V + E)
Space	O(V)	O(V)
Cycle Detection	Requires extra state	Built-in
Implementation	Simpler	Slightly more setup
Parallelization	Harder	Natural (process all zero in-degree vertices simultaneously)

DFS visits each vertex once and traverses each edge once. Kahn’s algorithm similarly processes each vertex and edge exactly once when decrementing in-degrees.

Choose DFS when you need a quick implementation and trust your input is acyclic. Choose Kahn’s when you need cycle detection, want to parallelize, or need to enumerate all valid orderings (by exploring all choices when multiple vertices have zero in-degree).

Practical Application: Build System Example

Let’s model a real build system where source files depend on headers and libraries:

from dataclasses import dataclass
from typing import Dict, List

@dataclass
class BuildTarget:
    name: str
    dependencies: List[str]
    
    def compile(self):
        print(f"Compiling {self.name}...")

class BuildSystem:
    def __init__(self):
        self.targets: Dict[str, BuildTarget] = {}
        self.name_to_id: Dict[str, int] = {}
        self.id_to_name: Dict[int, str] = {}
    
    def add_target(self, target: BuildTarget) -> None:
        self.targets[target.name] = target
    
    def build_all(self) -> None:
        # Assign IDs to targets
        names = list(self.targets.keys())
        self.name_to_id = {name: i for i, name in enumerate(names)}
        self.id_to_name = {i: name for i, name in enumerate(names)}
        
        # Build dependency graph
        graph = Graph(len(names))
        for target in self.targets.values():
            target_id = self.name_to_id[target.name]
            for dep_name in target.dependencies:
                if dep_name not in self.name_to_id:
                    raise ValueError(f"Unknown dependency: {dep_name}")
                dep_id = self.name_to_id[dep_name]
                graph.add_edge(dep_id, target_id)
        
        # Get build order using Kahn's algorithm
        try:
            order = topological_sort_kahn(graph)
        except ValueError as e:
            raise ValueError(f"Circular dependency detected: {e}")
        
        # Execute builds in order
        for target_id in order:
            target_name = self.id_to_name[target_id]
            self.targets[target_name].compile()

# Example usage
if __name__ == "__main__":
    build = BuildSystem()
    build.add_target(BuildTarget("utils.o", []))
    build.add_target(BuildTarget("config.o", []))
    build.add_target(BuildTarget("logger.o", ["utils.o"]))
    build.add_target(BuildTarget("database.o", ["config.o", "logger.o"]))
    build.add_target(BuildTarget("server.o", ["database.o", "utils.o"]))
    build.add_target(BuildTarget("main", ["server.o"]))
    
    build.build_all()
    # Output:
    # Compiling utils.o...
    # Compiling config.o...
    # Compiling logger.o...
    # Compiling database.o...
    # Compiling server.o...
    # Compiling main...

Edge Cases and Common Pitfalls

Production code must handle several edge cases:

import unittest

class TestTopologicalSort(unittest.TestCase):
    def test_empty_graph(self):
        g = Graph(0)
        self.assertEqual(topological_sort_kahn(g), [])
    
    def test_single_vertex(self):
        g = Graph(1)
        self.assertEqual(topological_sort_kahn(g), [0])
    
    def test_disconnected_components(self):
        g = Graph(4)
        g.add_edge(0, 1)  # Component 1: 0 -> 1
        g.add_edge(2, 3)  # Component 2: 2 -> 3
        result = topological_sort_kahn(g)
        # Verify ordering constraints
        self.assertLess(result.index(0), result.index(1))
        self.assertLess(result.index(2), result.index(3))
    
    def test_self_loop_detected(self):
        g = Graph(2)
        g.add_edge(0, 0)  # Self-loop
        with self.assertRaises(ValueError):
            topological_sort_kahn(g)
    
    def test_cycle_detected(self):
        g = Graph(3)
        g.add_edge(0, 1)
        g.add_edge(1, 2)
        g.add_edge(2, 0)  # Creates cycle
        with self.assertRaises(ValueError):
            topological_sort_kahn(g)
    
    def test_multiple_valid_orderings(self):
        g = Graph(4)
        g.add_edge(0, 2)
        g.add_edge(1, 2)
        g.add_edge(2, 3)
        result = topological_sort_kahn(g)
        # Both [0,1,2,3] and [1,0,2,3] are valid
        self.assertLess(result.index(0), result.index(2))
        self.assertLess(result.index(1), result.index(2))
        self.assertLess(result.index(2), result.index(3))
    
    def test_linear_chain(self):
        g = Graph(4)
        g.add_edge(0, 1)
        g.add_edge(1, 2)
        g.add_edge(2, 3)
        self.assertEqual(topological_sort_kahn(g), [0, 1, 2, 3])

if __name__ == "__main__":
    unittest.main()

Common pitfalls to avoid:

Forgetting disconnected components: Always iterate over all vertices, not just those reachable from an arbitrary start
Confusing edge direction: Clarify whether edges point from prerequisite to dependent or vice versa
Assuming unique ordering: Multiple valid orderings exist; don’t depend on a specific one unless you enforce it
Ignoring cycles in DFS: The basic DFS algorithm silently produces garbage on cyclic graphs; add explicit cycle detection using recursion stack tracking

Topological sort is foundational. Master both approaches, understand their trade-offs, and you’ll have a powerful tool for any dependency resolution problem.