Topological Sort

Definition

Topological Sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG). The rule is simple: For every directed edge from vertex U to vertex V, vertex U must come before vertex V in the ordering.

Note: This only works if the graph has NO cycles. If there is a cycle (A needs B, B needs A), you cannot sort them.

How it Works

Think of this as a To-Do List with Prerequisites.

1. Find a task that has zero prerequisites (no arrows pointing to it).
2. “Do” that task (add to sorted list).
3. Cross it off. Now, look at the tasks that were waiting for it. If any of them now have zero remaining prerequisites, they are ready to be done next.
4. Repeat.

Real-World Analogy

University Course Prerequisites:

• You cannot take Calculus II until you pass Calculus I.
• You cannot take Physics until you pass Calculus I.
• Topological Sort: Calculus I $\rightarrow$ Physics $\rightarrow$ Calculus II. (This is a valid valid order because dependencies are respected).

Example

Dependencies:

• A rightarrow C
• B rightarrow C
• C rightarrow D

Valid Sort: A, B, C, D OR B, A, C, D. (A and B have no dependencies, so either can go first. But C must wait for both, and D must wait for C).

Code Example (Kahn’s Algorithm – BFS Approach)

from collections import deque

def topological_sort(vertices, edges):
    # 1. Initialize Graph and Indegree (count of incoming edges)
    graph = {i: [] for i in range(vertices)}
    indegree = {i: 0 for i in range(vertices)}

    for u, v in edges:
        graph[u].append(v)
        indegree[v] += 1

    # 2. Add all nodes with 0 indegree to queue
    queue = deque([node for node in indegree if indegree[node] == 0])
    result = []

    # 3. Process queue
    while queue:
        node = queue.popleft()
        result.append(node)

        # Decrease indegree of neighbors
        for neighbor in graph[node]:
            indegree[neighbor] -= 1
            # If neighbor has no more prerequisites, add to queue
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    # Cycle Detection check
    if len(result) != vertices:
        return "Graph has a cycle! Cannot Sort."
   
    return result

# Usage
# 0->2, 1->2, 2->3
edges = [(0, 2), (1, 2), (2, 3)]
print("Topological Sort:", topological_sort(4, edges))
# Output: [0, 1, 2, 3] or [1, 0, 2, 3]

Complexity Analysis

• Time Complexity: O(V + E). We process every node and every edge exactly once.
• Space Complexity: O(V). We need an array for Indegrees and a Queue.

Use Cases & Interview Relevance

• Build Systems (Makefiles/Maven/Gradle): Determining which files to compile first. If File B imports File A, A must be compiled first.
• Task Scheduling: Operating systems scheduling jobs that depend on each other.
• React/Frontend Initialization: Deciding the order to load components or scripts.
• Interview Tip: If a question mentions “prerequisites,” “dependencies,” or “ordering tasks,” it is almost 100% a Topological Sort question.