Topological Sort

Topological Sort is one of the most useful algorithms for dependency-based coding interview problems. It appears often in medium and hard questions involving scheduling, ordering constraints, and prerequisite relationships, i.e., situations where the order matters more than simple reachability. Interviewers at Google, Amazon, Meta, Microsoft, and other FAANG-level companies like it because it tests whether you can model real-world constraints as a directed graph, reason about dependencies, detect cycles when an order is impossible, and implement a solution cleanly using BFS (Kahn’s algorithm) or DFS.

In practice, many well-known LeetCode interview problems such as Course Schedule, Alien Dictionary, and Parallel Courses are direct applications of topological sorting. A reliable signal is wording like “must be done before,” “prerequisite,” or “dependency.” Once you see these constraints as a DAG, the problem becomes much more structured: you are no longer guessing an order, you are constructing one that satisfies all prerequisites.

Topological sort intuition

To understand topological sorting intuitively, consider a project workflow with dependencies. Suppose you are releasing a software feature: you must finalize the requirements before designing the solution, complete the design before implementation, and finish implementation before testing. Finally, testing must happen before deployment.

There is often more than one valid way to execute the work because some tasks may be independent. However, dependency rules must always be respected. Any sequence that satisfies all prerequisites is valid. This flexibility is exactly what topological sort provides: it produces an ordering that honors dependencies without claiming the ordering is unique.

In graph terms, each task is a node, and each prerequisite relationship becomes a directed edge from “must happen first” to “happens later.” A topological order is any linear arrangement of tasks that respects every directed edge.

What is Topological Sort?

A Topological Sort is a linear ordering of the vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u → v, vertex u appears before vertex v in the ordering.

Two conditions are critical.

1. The graph must be directed because dependencies have direction.
2. The graph must be acyclic, i.e., it cannot have cycles. If there is a cycle (e.g., C → B → C), a valid topological sort is impossible.

The two core Topological Sort algorithms

In an interview, you can usually choose between BFS and DFS. However, Kahn’s Algorithm (BFS) is often preferred because it makes cycle detection very intuitive. In both approaches, the graph is typically stored as an adjacency list, since it supports efficient traversal of outgoing edges and keeps memory usage at O(V + E).

Kahn’s Algorithm (BFS approach)

Kahn’s algorithm uses two core pieces of graph bookkeeping: an adjacency list and an in-degree array. The adjacency list stores, for each node, which nodes depend on it (outgoing edges). The in-degree array tracks how many prerequisites each node still has. Nodes with in-degree 0 have no remaining prerequisites, so they can be processed first.

The intuition: Repeatedly pick a node with no remaining dependencies, add it to the result, and “remove” it from the graph by decrementing the in-degree of its neighbors. If a neighbor’s in-degree drops to zero, it becomes ready to process next.

Step-by-step:

1. Initialize an adjacency list graph and an indegree array of size V (all zeros).
2. Process every directed edge u → v:
   1. Add v to graph[u].
   2. Increment indegree[v] by 1.
3. Add all nodes with indegree == 0 to a queue.
4. While the queue is not empty:
   1. Pop a node, append it to the result.
   2. For each neighbor, decrement its indegree.
   3. If a neighbor’s indegree becomes 0, push it into the queue.
5. If the result list contains all nodes, a valid topological order exists. If not, the graph has a cycle.

Kahn’s algorithm’s implementation in Python

Let’s look at the Python code for Kahn’s algorithm.

from collections import defaultdict, deque

def topological_sort_kahn(n, edges):
    # Step 1: Build adjacency list + indegree array
    graph = defaultdict(list)
    indegree = [0] * n

    for u, v in edges:
        graph[u].append(v)   # u -> v
        indegree[v] += 1     # v has one more prerequisite

    # Step 2: Push all nodes with indegree 0 into the queue
    queue = deque(node for node in range(n) if indegree[node] == 0)

    topo_order = []

    # Step 3: Pop available nodes and reduce indegrees of neighbors
    while queue:
        node = queue.popleft()
        topo_order.append(node)

        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    # Step 4: If we didn't process all nodes, there's a cycle
    return topo_order if len(topo_order) == n else []


# ---------------- Example usage ----------------

# Example DAG:
# 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3
n = 4
edges = [(0, 1), (0, 2), (1, 3), (2, 3)]

order = topological_sort_kahn(n, edges)
print("Input DAG:  0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3\n")
print("Topological Order:", order)

• Time complexity: The time complexity is O(V + E), where V is the number of vertices and E is the number of edges. Each node and edge is processed once.
• Space complexity: The space complexity is also O(V + E) due to storing the adjacency list and indegree array.

Let’s look at the slides below to get a better understanding of Kahn’s algorithm.

1 / 6

DFS-based topological sort

The DFS approach also starts by representing the directed graph using an adjacency list. Then, it performs a post-order DFS: after fully exploring all outgoing neighbors of a node, it appends the node to a result list (or pushes it onto a stack). Reversing this post-order produces a valid topological ordering.

In DFS-based topological sort, you must append a node to the result only after all of its outgoing neighbors are fully processed (post-order). Appending earlier (pre-order) can produce an invalid ordering that violates dependencies.

The Intuition: A node should appear after everything that depends on it is resolved. Post-order DFS naturally processes descendants before ancestors, so reversing (or using a stack) gives us the ordering we need.

Cycle detection is critical in DFS-based topological sort and is often expected in interviews. The standard way is to use a 3-state visited array:

• 0 = unvisited (node has not been seen yet)
• 1 = visiting (node is currently in the recursion stack)
• 2 = visited (node is fully processed)

A cycle exists if, during DFS, you reach a node that is already in state 1 (visiting). That means you found a back edge into the current recursion stack, so a topological ordering is impossible.

Python implementation of DFS-based topological sort

Let’s look at the Python code for the DFS-based topological sort.

from collections import defaultdict

def topological_sort_dfs(n, edges):
    # Step 1: Build adjacency list (graph representation)
    # graph[u] = list of nodes v such that there is an edge u -> v
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)

    # Step 2: Track visit state for cycle detection
    # 0 = unvisited, 1 = visiting (in current recursion stack), 2 = visited (fully processed)
    state = [0] * n

    topo_order = []     # stores nodes in reverse topological order (postorder)
    has_cycle = False   # flag to mark if a cycle is detected

    def dfs(node):
        nonlocal has_cycle

        # If we re-enter a node that is currently in recursion stack, we found a cycle
        if state[node] == 1:
            has_cycle = True
            return

        # If already processed, no need to do anything
        if state[node] == 2:
            return

        # Mark as visiting (enter recursion stack)
        state[node] = 1

        # Step 3: Visit all outgoing neighbors
        for neighbor in graph[node]:
            dfs(neighbor)

        # Mark as visited (exit recursion stack)
        state[node] = 2

        # Step 4: Postorder append (node is placed after all its dependencies)
        topo_order.append(node)

    # Step 5: Run DFS from every node to handle disconnected components
    for i in range(n):
        if state[i] == 0:
            dfs(i)

    # Step 6: If a cycle exists, topological ordering is impossible
    if has_cycle:
        return []

    # Step 7: Reverse postorder to get topological order
    return topo_order[::-1]

# ---------------- Example usage ----------------
n = 4
edges = [(0, 1), (0, 2), (1, 3), (2, 3)]

print("Input DAG: 0 -> 1, 0 -> 2, 1 -> 3, 2 -> 3\n")
order = topological_sort_dfs(n, edges)
print("Topological Order (DFS):", order)

• Time complexity: O(V + E)
• Space complexity: O(V + E) for the adjacency list, recursion stack, and visited array.

Let’s look at the slides below to get a better understanding of DFS-based Topological Sort algorithm.

1 / 8

How to identify Topological Sort problems in interviews

Topological sort comes up whenever a problem describes dependencies and asks for an order or whether an order is possible.

A quick distinction you’ll see constantly:

• “Is it possible/ can we finish?”, you only need cycle detection (e.g., Course Schedule I).
• “Return an order/ output a schedule”, you must construct a topological ordering (e.g., Course Schedule II).

Look for signals like:

• “prerequisite”
• “must be done before”
• “depends on”
• “schedule these tasks”
• “is there a valid ordering?”

Most variations then ask you to:

• Return true/false (cycle or no cycle),
• Return any valid order,
• Compute minimum rounds/semesters,
• Or, return the lexicographically smallest valid order.

Implementation-wise, the setup is consistent: build a directed graph as an adjacency list, then use Kahn’s BFS or DFS with 3-state cycle detection depending on what the prompt requires.

Common mistakes and edge cases in Topological Sort

Although topological sorting is conceptually straightforward, many incorrect implementations fail due to subtle edge cases and overlooked details. Being aware of these pitfalls can prevent avoidable mistakes in interviews.

1. Forgetting to handle disconnected components: A directed graph may consist of multiple independent components. If your algorithm only starts traversal from a single node, you may miss other parts of the graph. Always ensure that you process all vertices, even if they are not reachable from one starting point.
2. Not checking for cycles properly: In Kahn’s algorithm, many candidates forget to verify whether all nodes were processed. If the size of the resulting ordering is smaller than the total number of vertices, a cycle exists. Without this check, you may incorrectly return a partial ordering.
3. Duplicate edges inflating indegree counts: If the input contains duplicate edges and you do not account for them, the indegree values may be incremented multiple times. This can prevent certain nodes from ever reaching indegree zero, leading to incorrect cycle detection.
4. Confusion between 1-based and 0-based indexing: Many interview problems use 1-based node labels, while programming languages typically use 0-based indexing. Failing to convert correctly can lead to out-of-bounds errors or incorrect graph construction.
5. Graph with a single node: A graph containing only one vertex and no edges is a valid DAG. The topological ordering is simply that single node. This edge case should be handled naturally by your implementation.
6. Empty graph: If the number of vertices is zero, the correct result is an empty ordering. Your code should gracefully handle this scenario without errors.