Topological Sort

    DSA · Advanced

    Definition

    Topological sort orders nodes of a directed acyclic graph so every edge goes from earlier to later.

    Used for task scheduling, course prerequisites and build systems.

    Diagram

    A → BA → CB → DC → D

    Flowchart

    Compute in-degree of each nodeQueue nodes with in-degree 0Pop and append to orderDecrease neighbors' in-degreeIf order < n, a cycle exists

    Example: Kahn's algorithm

    from collections import deque
g = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
indeg = {k: 0 for k in g}
for u in g:
    for v in g[u]: indeg[v] += 1
q = deque([k for k in g if indeg[k] == 0])
order = []
while q:
    u = q.popleft(); order.append(u)
    for v in g[u]:
        indeg[v] -= 1
        if indeg[v] == 0: q.append(v)
print(order)

    Output: ['A', 'B', 'C', 'D']

    Complexity

    O(V + E)

    Key points

    • Only works on DAGs
    • DFS post-order reversed also works

    Interview questions

    Course Schedule problem?

    Run Kahn's algorithm; if all courses appear in the order, they can be finished.

    More DSA topics

    ArraysLinked ListStackQueue