Topological Sorting for DAGs — Kahn's Algorithm and DFS-Based Sort (Interactive Simulator)

The Story — Getting Dressed in the Right Order

Topological sorting works on a DAG: a Directed Acyclic Graph. "Directed" means edges have arrows. "Acyclic" means you can never follow arrows and come back to where you started. If there is a cycle (A before B, B before C, C before A), no valid order exists.

Watch It Work — Animated Diagram

The getting-dressed graph. Pick Kahn to watch in-degree counters (the small badges) drop to zero. Pick DFS to watch nodes finish from the deepest one upwards. The order is built at the bottom.

The Topological Sort Simulator — Build Your Own DAG

Draw tasks and the arrows between them. Run Kahn's or DFS one step at a time. Watch the queue and in-degree table, or the call stack and finish stack. You can also play My Order: click nodes in your own order, and the simulator stops you if you break a rule.

Kahn's Algorithm — Step by Step

Graph: 5→2, 5→0, 4→0, 4→1, 2→3, 3→1. Starting in-degrees: 0:2, 1:2, 2:1, 3:1, 4:0, 5:0.

DFS-Based Sort — Step by Step (same graph)

Python Implementation

1. Kahn's Algorithm

from collections import deque

graph = {5: [2, 0], 4: [0, 1], 2: [3], 3: [1], 0: [], 1: []}

def kahn(graph):
    indeg = {u: 0 for u in graph}
    for u in graph:                        # count incoming arrows
        for v in graph[u]:
            indeg[v] += 1
    queue = deque(sorted(u for u in graph if indeg[u] == 0))
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in sorted(graph[u]):       # "remove" u's arrows
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)          # v is now ready
    if len(order) < len(graph):
        raise ValueError("Cycle found! No topological order.")
    return order

print("Kahn order:", kahn(graph))

2. DFS-Based Topological Sort (with cycle check)

WHITE, GRAY, BLACK = 0, 1, 2        # not seen, on path, finished

def dfs_topo(graph):
    color = {u: WHITE for u in graph}
    stack = []

    def visit(u):
        color[u] = GRAY
        for v in sorted(graph[u]):
            if color[v] == GRAY:           # back edge
                raise ValueError(f"Cycle found at edge {u} -> {v}")
            if color[v] == WHITE:
                visit(v)
        color[u] = BLACK
        stack.append(u)                    # u is finished

    for u in sorted(graph):
        if color[u] == WHITE:
            visit(u)
    print("Finish order:", stack)
    return stack[::-1]                       # reverse

print("DFS order:", dfs_topo(graph))

try:
    dfs_topo({'A': ['B'], 'B': ['C'], 'C': ['A']})
except ValueError as e:
    print("Error:", e)

3. Bonus — Minimum Number of Semesters (Kahn by levels)

def semesters(graph):
    indeg = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1
    level = sorted(u for u in graph if indeg[u] == 0)
    result = []
    while level:
        result.append(level)                 # everything ready now
        nxt = []
        for u in level:
            for v in graph[u]:
                indeg[v] -= 1
                if indeg[v] == 0:
                    nxt.append(v)
        level = sorted(nxt)
    return result

courses = {
    'Python': ['DS', 'Web'], 'Math': ['DS', 'ML'], 'DS': ['Algo', 'DBMS'],
    'Algo': ['ML'], 'DBMS': ['Project'], 'Web': ['Project'],
    'ML': ['Project'], 'Project': [],
}
for i, lv in enumerate(semesters(courses), 1):
    print(f"Semester {i}: {lv}")

Complexity

Where Topological Sorting Is Used

Golden Rules