Topological Sort Visualizer

How it works

1. Count the in-degree of every node: how many edges point into it.
2. Put every node with in-degree 0 into a queue — nothing has to come before them.
3. Dequeue a node u and append it to the order.
4. For each edge u → v, decrement indeg[v]; when it reaches 0, all of v's prerequisites are placed, so enqueue v.
5. Repeat until the queue is empty. If fewer than V nodes were output, the rest lie on or behind a cycle and no topological order exists.

Intuition: peel off nodes with no prerequisites

A node with in-degree 0 depends on nothing, so it can safely go first. Remove it together with its outgoing edges and you are left with a smaller DAG — which again has at least one node with in-degree 0. (If every node had an incoming edge, you could walk backwards along those edges forever, and in a finite graph that walk must eventually repeat a node: a cycle.) Repeating the peel produces a complete order.

Kahn's algorithm does the peeling without actually deleting anything: it just decrements in-degree counters and keeps a queue of nodes whose counter has reached 0.

Worked example

The page opens on a DAG of prerequisites: F → A, F → C, B → C, A → D, C → D, D → E, B → G, G → E. The in-degrees are A 1, B 0, C 2, D 2, E 2, F 0, G 1.

• The queue starts with B and F (ties are taken alphabetically).
• Output B: C drops to 1 and G to 0, so G joins the queue.
• Output F: A and C both drop to 0 and join the queue.
• Output G (E drops to 1), then A (D drops to 1), then C (D drops to 0 and joins).
• Output D (E drops to 0), then E.

The order is B, F, G, A, C, D, E, and every arrow points from left to right. It is not the only valid answer — F, B, A, C, D, G, E works too. A DAG has a unique topological order only when it contains a path through all of its nodes, in which case the queue never holds more than one node.

Cycles: when no order exists

Take the directed graph A → B, B → C, C → D, D → B, A → E, E → D: Kahn's algorithm outputs A and E, then stops: B, C and D each keep an incoming edge from inside the cycle B → C → D → B, so none of their counters ever reaches 0.

That makes "did we output all V nodes?" a free cycle detector, and it is the standard answer to questions like "can all the courses be finished?". Nodes that are not on a cycle but depend on one are also left out, because their prerequisites are never completed.

The DFS alternative

Topological order can also come from depth-first search: run DFS over every node, append each node to a list when it finishes, and reverse the list. It works because for every edge u → v in a DAG, v finishes before u. If DFS meets a back edge (a node still on the stack), there is a cycle.

Both versions are O(V + E). Kahn's algorithm is iterative (no recursion limits), detects cycles naturally, and can return the lexicographically smallest order if you swap its queue for a min-heap. The DFS version is shorter if you already have a DFS, and it is the first half of Kosaraju's SCC algorithm.

Where topological sorting is used

• Build systems and package managers: compile or install every dependency before the things that need it (make, Bazel, npm, apt).
• Spreadsheets recalculate cells in topological order of their formulas; data pipelines such as Airflow run task DAGs.
• Scheduling: course plans, project tasks and the critical path method, where the longest path through the DAG gives the minimum project duration.
• Dynamic programming on DAGs: relaxing edges in topological order gives shortest or longest paths in O(V + E), even with negative weights.

Interview classics: Course Schedule I and II, Alien Dictionary, Parallel Courses (the number of BFS "layers" is the minimum number of semesters), and Sequence Reconstruction.

Time and space complexity

Topological Sort in Python

from collections import deque


def topo_sort(graph):
    """Kahn's algorithm. graph: {node: [successors]}.
    Returns a topological order, or None if there is a cycle."""
    indeg = {v: 0 for v in graph}
    for u in graph:
        for v in graph[u]:
            indeg[v] += 1                  # count incoming edges
    Q = deque(v for v in graph if indeg[v] == 0)
    order = []
    while Q:
        u = Q.popleft()                    # u <- Q.dequeue()
        order.append(u)                    # output u
        for v in graph[u]:                 # each edge u -> v
            indeg[v] -= 1
            if indeg[v] == 0:
                Q.append(v)
    if len(order) < len(graph):
        return None                        # cycle!
    return order

The visualizer above shows the same code in Python, C++, Java and JavaScript.

Frequently asked questions

Keep learning

• DFS Visualizer — Depth-First SearchDepth-first search explores a graph by going as deep as possible, then backtracking. See DFS step by step with discovery and finish times, back edges and code.
• Strongly Connected Components VisualizerStrongly connected components are groups of nodes in a directed graph that can all reach each other. Watch Kosaraju's algorithm find them step by step.
• BFS Visualizer — Breadth-First SearchBreadth-first search explores a graph level by level with a queue and finds fewest-edge paths. Watch BFS run step by step, with code and O(V + E) analysis.
• Bellman-Ford Algorithm VisualizerBellman-Ford finds shortest paths even with negative edge weights and detects negative cycles. Watch each relaxation pass step by step, with O(V·E) code.
• Graph Algorithm VisualizerInteractive graph algorithm visualizer: draw or generate a graph and step through BFS, DFS, Dijkstra, Bellman-Ford, Kruskal, Prim, topological sort and SCCs.