All Topological Sorts of a DAG

All Topological Sorts of a DAG takes the classic topological-sort question one step further: instead of producing one valid ordering, list every valid ordering. It is a clean showcase of backtracking driven by in-degrees.

The slow way first

You could generate every permutation of the vertices and keep the ones that respect all edges. With n vertices that is n! permutations, and each check is O(edges) — wildly slow, and most permutations get thrown away.

The wasted work is the giveaway: we keep building orderings that were doomed from the start. The fix is to only ever extend an ordering with a vertex that is legal right now.

The idea: pick any free vertex, then undo

Track each vertex's in-degree — the count of incoming edges. A vertex is free to be placed next exactly when its in-degree is 0 (everything that must precede it is already placed).

So at each level of a depth-first search, loop over every free vertex. For each one: append it, decrement the in-degrees of its out-neighbors (which may free new vertices), and recurse. When the ordering reaches length n, record a copy. Then backtrack — pop the vertex and restore the in-degrees — so the loop can try the next free vertex.

The branching at the first level (A or B) is exactly what produces the two different orderings.

Walk through it

Step through the animation. A and B start with in-degree 0, so both are choices. We pick A, then B, which frees C, then C frees D — giving [A, B, C, D]. Then we backtrack all the way to the first decision, restoring in-degrees, and pick B before A instead, producing [B, A, C, D].

Pseudocode

compute in-degree of every vertex
order = empty list, result = empty list
 
dfs():
    for each vertex v:
        if in-degree[v] == 0 and v not yet placed:
            append v to order
            for each neighbor w of v: in-degree[w] -= 1
            dfs()
            if order has all n vertices: save a copy to result
            pop v from order                 # undo
            for each neighbor w of v: in-degree[w] += 1   # undo
dfs()
return result

The Python solution

def all_topo_sorts(n, adj, indeg):
    result, order = [], []
    def dfs():
        progressed = False
        for v in range(n):
            if indeg[v] == 0 and v not in order:
                order.append(v)
                for w in adj[v]:
                    indeg[w] -= 1
                dfs()
                if len(order) == n:
                    result.append(order[:])
                order.pop()
                for w in adj[v]:
                    indeg[w] += 1
                progressed = True
    dfs()
    return result

• indeg holds the current in-degree of every vertex; order is the ordering we are building.
• The loop on line 5 scans for a vertex that is free (indeg[v] == 0) and not already placed (line 6).
• Appending v and decrementing each neighbor (lines 7-9) simulates removing v from the graph, which may free new vertices for the recursive call.
• When order reaches length n, we save a copy with order[:] — copying matters, because we mutate order in place.
• Lines 13-15 are the backtrack: pop v and add 1 back to every neighbor, exactly reversing the move so the loop can try the next free vertex.

Complexity

The number of topological sorts can itself be as large as n! (an edgeless graph has every permutation), so no algorithm can do better than the output size in the worst case. The win is that backtracking never wastes time on invalid prefixes — each recursion step only extends with a currently-free vertex.

When this pattern shows up

Practice