Skip to main content

Documentation Index

Fetch the complete documentation index at: https://swe.aboneda.com/llms.txt

Use this file to discover all available pages before exploring further.

​
Topological Sort

A linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u → v, vertex u comes before v.

​
Two Approaches

​
1. Kahn’s Algorithm (BFS-based)

Uses in-degree counting:
  1. Compute in-degree for every node
  2. Add all nodes with in-degree 0 to a queue
  3. Process queue: for each node, reduce in-degree of neighbors
  4. If a neighbor’s in-degree becomes 0, add it to the queue
  5. If result contains all nodes → valid ordering; otherwise → cycle exists
from collections import deque

def topo_sort_bfs(graph, n):
    in_degree = [0] * n
    for u in range(n):
        for v in graph[u]:
            in_degree[v] += 1

    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []

    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)

    return order if len(order) == n else []  # empty = cycle

​
2. DFS-based

Use post-order DFS and reverse the result:
  1. Run DFS from each unvisited node
  2. After visiting all neighbors, add current node to stack
  3. Reverse the stack for topological order

​
Complexity

TimeSpace
Kahn’s (BFS)O(V + E)O(V)
DFS-basedO(V + E)O(V)

​
Cycle Detection

  • Kahn’s: if result has fewer than V nodes → cycle exists
  • DFS: if you encounter a node in the current recursion stack → cycle exists

​
Classic Problems

  • Course Schedule I & II
  • Alien Dictionary
  • Minimum Height Trees
  • Parallel Courses
  • Build Order (project dependencies)
  • Sequence Reconstruction

​
When to Use

  • Task scheduling with dependencies
  • Build systems and compilation order
  • Course prerequisite chains
  • Any problem involving ordering with constraints on a DAG