Algorithms · Lesson 13 of 17

Topological Sort

Learn topological sort in Python with Kahn's algorithm and DFS to order tasks, build systems and course prerequisites in a DAG and detect cycles.

Intermediate
16 min read
4 objectives

Before this lessonLesson 12: Shortest Paths: Dijkstra and Bellman-Ford

What you will learn

Explain what a DAG and a topological order are
Implement Kahn's algorithm with in-degrees
Implement the DFS post-order approach
Use the order for scheduling and longest-path problems

Your Progress

0 of 17 lessons 0%

Lessons0 / 17
Completed0
Est. time left~ 5 hours

Create a free account to keep your progress on every device.

Tip: pressing Next marks this lesson complete automatically.

Some tasks must happen before others. You install dependencies before building, build before testing, test before deploying. Course lessons have prerequisites. Spreadsheet cells depend on other cells. A topological sort takes a set of "A must come before B" rules and produces an order that respects all of them.

The rules form a directed graph: an edge A to B means A comes first. An order exists only if there are no cycles (if A needs B and B needs A, nothing can start). A directed graph without cycles is called a DAG (directed acyclic graph). Every DAG has at least one topological order, and often many. Tools you use daily, like pip, npm, Make, Airflow and Python's own graphlib module, run a topological sort under the hood.

The example: a stackcone learning path

prereqs = {
    "python":   ["pandas", "flask"],
    "sql":      ["pandas"],
    "pandas":   ["ml"],
    "flask":    ["deploy"],
    "ml":       ["deploy"],
    "deploy":   [],
}
# an edge u -> v means "take u before v"
for u, vs in prereqs.items():
    for v in vs:
        print(f"{u} -> {v}")

Output

python -> pandas
python -> flask
sql -> pandas
pandas -> ml
flask -> deploy
ml -> deploy

Kahn's algorithm (BFS with in-degrees)

The in-degree of a node is how many edges point into it: how many prerequisites it still has. A node with in-degree 0 can be done right now. Kahn's algorithm repeatedly takes a ready node, outputs it, and "removes" its outgoing edges by decrementing its neighbours' in-degrees. Any neighbour that drops to 0 becomes ready.

# from earlier in this lesson
prereqs = {
    "python":   ["pandas", "flask"],
    "sql":      ["pandas"],
    "pandas":   ["ml"],
    "flask":    ["deploy"],
    "ml":       ["deploy"],
    "deploy":   [],
}
# an edge u -> v means "take u before v"

# new code
from collections import deque

def kahn(graph):
    indegree = {n: 0 for n in graph}
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1
    ready = deque(n for n in graph if indegree[n] == 0)
    order = []
    while ready:
        u = ready.popleft()
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                ready.append(v)
    if len(order) != len(graph):
        raise ValueError("cycle detected")
    return order

print(kahn(prereqs))

Output

['python', 'sql', 'flask', 'pandas', 'ml', 'deploy']

If a cycle exists, the nodes in it never reach in-degree 0, so they never get output. Comparing len(order) with the number of nodes is a free cycle check. Time O(V + E), space O(V).

The DFS approach

The second method uses DFS. When DFS finishes a node (all its descendants are done), everything that must come after it has already been recorded. So if you append each node when it finishes, you get a reverse topological order. Reverse the list at the end.

# from earlier in this lesson
prereqs = {
    "python":   ["pandas", "flask"],
    "sql":      ["pandas"],
    "pandas":   ["ml"],
    "flask":    ["deploy"],
    "ml":       ["deploy"],
    "deploy":   [],
}
# an edge u -> v means "take u before v"

# new code
def topo_dfs(graph):
    WHITE, GREY, BLACK = 0, 1, 2
    color = {n: WHITE for n in graph}
    finished = []
    def visit(u):
        color[u] = GREY
        for v in graph[u]:
            if color[v] == GREY:
                raise ValueError(f"cycle through {v}")
            if color[v] == WHITE:
                visit(v)
        color[u] = BLACK
        finished.append(u)          # post-order
    for n in graph:
        if color[n] == WHITE:
            visit(n)
    return finished[::-1]

print(topo_dfs(prereqs))
try:
    topo_dfs({"a": ["b"], "b": ["a"]})
except ValueError as e:
    print("error:", e)

Output

['sql', 'python', 'flask', 'pandas', 'ml', 'deploy']
error: cycle through a

Notice the two methods returned different, equally valid orders. Both put python and sql before pandas, and deploy last. Time O(V + E), space O(V) plus recursion depth.

Use the standard library

Since Python 3.9, graphlib.TopologicalSorter does this for you. Note that it takes a mapping from each node to its predecessors (dependencies), the opposite of our adjacency list.

from graphlib import TopologicalSorter, CycleError

depends_on = {"pandas": {"python", "sql"}, "ml": {"pandas"},
              "flask": {"python"}, "deploy": {"flask", "ml"}}
order = list(TopologicalSorter(depends_on).static_order())
print(order.index("python") < order.index("pandas") < order.index("ml") < order.index("deploy"))

try:
    list(TopologicalSorter({"a": {"b"}, "b": {"a"}}).static_order())
except CycleError:
    print("CycleError raised")

Output

True
CycleError raised

Scheduling: the longest path in a DAG

If every task has a duration and independent tasks can run in parallel, the total project time is the longest path through the DAG (the critical path). Finding longest paths is hard in general graphs, but in a DAG it is easy: process nodes in topological order and relax edges, keeping the maximum.

# from earlier in this lesson
prereqs = {
    "python":   ["pandas", "flask"],
    "sql":      ["pandas"],
    "pandas":   ["ml"],
    "flask":    ["deploy"],
    "ml":       ["deploy"],
    "deploy":   [],
}
# an edge u -> v means "take u before v"

from collections import deque

def kahn(graph):
    indegree = {n: 0 for n in graph}
    for u in graph:
        for v in graph[u]:
            indegree[v] += 1
    ready = deque(n for n in graph if indegree[n] == 0)
    order = []
    while ready:
        u = ready.popleft()
        order.append(u)
        for v in graph[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                ready.append(v)
    if len(order) != len(graph):
        raise ValueError("cycle detected")
    return order

# new code
def project_time(graph, duration):
    finish = {}
    for u in kahn(graph):
        # a task starts when all its prerequisites have finished
        start = finish.get(u, 0)
        finish[u] = start + duration[u]
        for v in graph[u]:
            finish[v] = max(finish.get(v, 0), finish[u])
    return max(finish.values())

hours = {"python": 20, "sql": 8, "pandas": 10, "flask": 6, "ml": 25, "deploy": 4}
print(project_time(prereqs, hours), "hours")

Output

59 hours

Here we reuse finish[v] as "earliest start" before v is processed, then overwrite it with the real finish time. The critical path is python, pandas, ml, deploy: 20 + 10 + 25 + 4 = 59. The same idea gives shortest paths in a DAG in O(V + E), even with negative weights.

Recap

A topological order lists nodes so every edge points forward; it exists only for DAGs.
Kahn's algorithm repeatedly outputs nodes with in-degree 0; a short output means a cycle.
DFS post-order, reversed, is also a valid topological order.
Both run in O(V + E); graphlib.TopologicalSorter is the built-in option.
Processing a DAG in topological order solves longest and shortest path problems in linear time.

# Write your solution here

Finished reading? Mark this lesson complete to track your progress.

Up next · Lesson 14Minimum Spanning Trees: Kruskal and PrimLearn minimum spanning trees in Python with Kruskal's algorithm and union-find, Prim's algorithm with a heap, and when to use each one.