Topological Sort - Theory

What is Topological Sorting?

A Topological Sort of a directed graph is a linear ordering of its vertices such that for every directed edge u → v, vertex u comes before v in the ordering.

It answers the question:

“Given a set of dependencies, what order should tasks be performed in?”

Applications of Topological Sorting

• Task Scheduling (e.g., course prerequisites)

• Compilation order of source code files

• Build Systems (like Makefiles)

• Dependency Resolution (package managers)

• Instruction scheduling in CPUs

Why is Topological Sort Only for DAGs?

Topological Sort is only defined for Directed Acyclic Graphs (DAGs). Here's why:

DAG (Directed Acyclic Graph)

• "Directed": edges point one way (u → v)

• "Acyclic": no cycle exists

• This guarantees a partial ordering

Cycles Cause a Contradiction

Suppose there's a cycle:
A → B → C → A

Topological sort would require:
A < B < C < A — which is a contradiction.

Hence, topological sorting is not possible if the graph contains cycles.

Two Main Algorithms for Topological Sort

Link : Topological sort

1. Kahn’s Algorithm (BFS-Based Topological Sort)

Intuition

• Build a queue of nodes with in-degree 0 (no dependencies).

• Pick such a node, add to result, and reduce in-degree of neighbors.

• If neighbor becomes in-degree 0, push it to the queue.

• If at the end, not all nodes are processed → cycle detected.

Steps

1. Calculate in-degrees of all vertices.

2. Initialize a queue with all vertices having in-degree 0.

3. While queue is not empty:

   • Pop a node u and add to the topoSort list.

   • For each neighbor v of u:

     • inDegree[v]--

     • If inDegree[v] == 0, enqueue v

4. If the topoSort list contains all nodes, it is a valid ordering. Otherwise, a cycle exists.

Java Code (Kahn’s Algorithm)

public class Solution {
    public int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj) {
        int[] inDegree = new int[V];
        
        // Step 1: Compute in-degrees
        for (int u = 0; u < V; u++) {
            for (int v : adj.get(u)) {
                inDegree[v]++;
            }
        }

        // Step 2: Add nodes with in-degree 0 to queue
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < V; i++) {
            if (inDegree[i] == 0) q.add(i);
        }

        // Step 3: Process queue
        ArrayList<Integer> topo = new ArrayList<>();
        while (!q.isEmpty()) {
            int u = q.poll();
            topo.add(u);

            for (int v : adj.get(u)) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    q.add(v);
                }
            }
        }

        // Step 4: Check for cycle
        if (topo.size() != V) return new int[0]; // cycle exists
        return topo.stream().mapToInt(i -> i).toArray();
    }
}

Dry Run (Example)

Given graph:

0 → 1
0 → 2
1 → 3
2 → 3

• In-degrees: [0, 1, 1, 2]

• Queue starts with 0

• Process:

  • 0 → topo = [0], in-degrees: [0, 0, 0, 2], queue = [1, 2]

  • 1 → topo = [0, 1], in-degrees: [0, 0, 0, 1], queue = [2]

  • 2 → topo = [0, 1, 2], in-degrees: [0, 0, 0, 0], queue = [3]

  • 3 → topo = [0, 1, 2, 3]

Final result = [0, 1, 2, 3]

2. DFS-Based Topological Sort

Intuition

• Use post-order DFS (add node to result after exploring its neighbors).

• Once all descendants are explored, push the current node to a stack.

• Finally, reverse the stack to get the topological order.

Steps

1. Maintain a visited[] array.

2. For every unvisited node, call DFS.

3. In DFS:

   • Mark the current node as visited

   • For every neighbor, if not visited, recurse DFS

   • After recursion, add the current node to the stack

4. Pop the stack for the topological sort order.

Java Code (DFS Topo Sort)

public class Solution {
    public void dfs(int node, boolean[] visited, Stack<Integer> stack, ArrayList<ArrayList<Integer>> adj) {
        visited[node] = true;

        for (int v : adj.get(node)) {
            if (!visited[v]) {
                dfs(v, visited, stack, adj);
            }
        }

        stack.push(node); // post-order
    }

    public int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj) {
        boolean[] visited = new boolean[V];
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                dfs(i, visited, stack, adj);
            }
        }

        int[] result = new int[V];
        int idx = 0;
        while (!stack.isEmpty()) {
            result[idx++] = stack.pop();
        }
        return result;
    }
}

Dry Run

Same graph:

0 → 1
0 → 2
1 → 3
2 → 3

DFS:

• Start from 0

  • DFS(1) → DFS(3) → push 3, push 1

  • DFS(2) → DFS(3) already visited → push 2

  • push 0

Stack = [3, 1, 2, 0]
Reverse = [0, 2, 1, 3]

Time and Space Complexity

Cycle Detection Using Topological Sort

• In Kahn’s Algorithm: if the topoSort list size is less than V, a cycle exists.

• In DFS-based approach: maintain a recStack[] (recursion stack) to detect back edges, which indicate a cycle.

When to Use Which?