Workspace

Problem workspace

3 day streakD

Topological Sort (Kahn’s Algorithm)

MediumGraphsOrdering

The challenge

Order the vertices of a directed graph so every prerequisite u appears before its dependent v for each edge u → v. Report failure if a directed cycle prevents a complete ordering.

A full topological ordering exists exactly when the directed graph is acyclic (a DAG).

Example

A → B → F → C → D → E is valid. Adding D → B creates a cycle; Kahn outputs only the unblocked prefix.

Use the walkthrough below to inspect the input and each state change.

See Kahn, step by step

Follow the edges. Watch the state change.

Directed · 6 vertices · 6 edgesA = 0, B = 1, …
DAGDirected graph with 6 vertices. Find vertices with no prerequisites. Count incoming edges. Only vertices with indegree zero may enter the initial queue. The edge list and state table below provide the graph in text.ABCDEF
CurrentVisited / acceptedUnvisited
Remaining indegree
ABCDEF
012111
Step 01 / 14

Find vertices with no prerequisites.

Count incoming edges. Only vertices with indegree zero may enter the initial queue.

queue = all vertices with indegree 0

Zero-indegree queue · front first

A
View input edges

A → B · A → F · B → C · F → C · C → D · D → E

Put it into code

A zero-indegree vertex is ready because none of its remaining prerequisites block it.

Vertices are numbered 0 to V − 1. C++ uses C++17 or later.

from collections import deque

def topological_sort(adj):
    indegree = [0] * len(adj)
    for neighbors in adj:
        for v in neighbors:
            indegree[v] += 1
    queue = deque(u for u, d in enumerate(indegree) if d == 0)
    order = []

    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    return order if len(order) == len(adj) else None

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap