Topological Sort

Use when: Ordering tasks with dependencies, detecting cycles in directed graphs.

Complexity: O(V + E)

Kahn’s Algorithm (BFS-based)

from collections import deque
 
def topo_sort(n, prerequisites):
    graph = [[] for _ in range(n)]
    indegree = [0] * n
 
    for a, b in prerequisites:
        graph[b].append(a)  # b -> a (b must come before a)
        indegree[a] += 1
 
    queue = deque([i for i in range(n) if indegree[i] == 0])
    order = []
 
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)
 
    return order if len(order) == n else []  # empty = cycle detected

DFS-based

def topo_sort_dfs(n, graph):
    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    result = []
    has_cycle = [False]
 
    def dfs(u):
        if has_cycle[0]:
            return
        color[u] = GRAY
        for v in graph[u]:
            if color[v] == GRAY:
                has_cycle[0] = True
                return
            if color[v] == WHITE:
                dfs(v)
        color[u] = BLACK
        result.append(u)
 
    for i in range(n):
        if color[i] == WHITE:
            dfs(i)
 
    if has_cycle[0]:
        return []
    return result[::-1]

Signals in a Problem

• “Course schedule” / “task ordering”
• Dependencies between items
• Detect cycle in directed graph
• “Can all tasks be completed?”