Topological Sort Explained: Kahn's Algorithm and DFS

A topological order of a directed graph lists the vertices so that every edge u → v has u before v. If edges mean "must happen before", a topological order is a valid schedule.

• Courses: take "Python" before "DSA" before "Machine Learning".
• Build tools compile a file's dependencies before the file.
• Spreadsheets recalculate a cell after the cells it refers to.

A topological order exists only for a DAG (directed acyclic graph). With a cycle (A needs B, B needs A) no order works.

Kahn's algorithm (BFS style)#

1. Count each vertex's in-degree: how many edges point into it (how many prerequisites it has).
2. Put every vertex with in-degree 0 in a queue: they can be done now.
3. Repeatedly take a vertex from the queue, add it to the order, and "remove" its outgoing edges by decreasing its neighbours' in-degrees. Any neighbour that reaches 0 joins the queue.
4. If the order contains every vertex, it is valid. Otherwise there is a cycle.

from collections import deque

def topo_sort(graph):
    in_degree = {v: 0 for v in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1
    queue = deque(sorted(v for v in graph if in_degree[v] == 0))
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    return order if len(order) == len(graph) else None

courses = {
    "python": ["dsa", "data"],
    "math": ["ml"],
    "dsa": ["ml"],
    "data": ["ml"],
    "ml": [],
}
print(topo_sort(courses))

cyclic = {"a": ["b"], "b": ["c"], "c": ["a"]}
print(topo_sort(cyclic))

['math', 'python', 'dsa', 'data', 'ml']
None

"python" and "math" have no prerequisites, so they come first; "ml" has three and comes last. On the cyclic graph no vertex ever reaches in-degree 0, so the result is None. The cost is O(V + E).

A graph can have many valid topological orders; sorting the starting vertices just makes the output predictable.

DFS postorder#

The DFS version adds a vertex to a list after all its descendants are finished (postorder), then reverses the list. A vertex finishes only after everything that depends on it, so the reversed finishing order puts prerequisites first:

def topo_sort_dfs(graph):
    visited, finished = set(), []

    def visit(u):
        visited.add(u)
        for v in graph[u]:
            if v not in visited:
                visit(v)
        finished.append(u)          # all of u's dependents are done

    for u in sorted(graph):
        if u not in visited:
            visit(u)
    return finished[::-1]

courses = {
    "python": ["dsa", "data"],
    "math": ["ml"],
    "dsa": ["ml"],
    "data": ["ml"],
    "ml": [],
}
print(topo_sort_dfs(courses))

['python', 'math', 'dsa', 'data', 'ml']

This order is different from Kahn's, but it is equally valid: every course still comes after its prerequisites. (This simple version assumes there is no cycle; combine it with the three-colour check from DFS to detect one.)

Checking an order#

It is easy to verify any proposed order: every edge must point forward.

def is_valid_order(graph, order):
    position = {v: i for i, v in enumerate(order)}
    return all(position[u] < position[v] for u in graph for v in graph[u])

courses = {"python": ["dsa", "data"], "math": ["ml"], "dsa": ["ml"], "data": ["ml"], "ml": []}
print(is_valid_order(courses, ["math", "python", "data", "dsa", "ml"]))
print(is_valid_order(courses, ["python", "ml", "dsa", "data", "math"]))

True
False

The second order puts "ml" before "dsa", "data" and "math", which it depends on.

Common mistakes#

Practice#

from collections import deque

def can_finish(n, pairs):
    graph = {i: [] for i in range(n)}
    in_degree = [0] * n
    for course, pre in pairs:
        graph[pre].append(course)
        in_degree[course] += 1
    queue = deque(i for i in range(n) if in_degree[i] == 0)
    done = 0
    while queue:
        u = queue.popleft()
        done += 1
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    return done == n

print(can_finish(2, [[1, 0]]))
print(can_finish(2, [[1, 0], [0, 1]]))
print(can_finish(4, [[1, 0], [2, 1], [3, 2]]))

True
False
True

Key takeaway#

Next: shortest paths when edges have weights, with Dijkstra's Shortest Path.