Topological sort

Time: O(V+E)

Space: O(V)

Intuition

Kahn's BFS approach: repeatedly remove nodes with in-degree 0. DFS approach: after exploring all descendants, push node to stack; the reverse of the stack gives topological order.

Algorithm

1DFS: TopoSort(node): mark visited. For each neighbor: if not visited, DFS. Push node to stack AFTER recursion.
2Collect nodes by finishing time (descending).

Example Walkthrough

Input: DAG: 5â†’0, 5â†’2, 4â†’0, 4â†’1, 2â†’3, 3â†’1

1.One valid topological order: 5,4,2,3,1,0.

Output: [5,4,2,3,1,0]

Common Pitfalls

•Topological sort is only valid for DAGs (Directed Acyclic Graphs). Detect cycles first.

Topological sort.java

Java

// Approach: DFS-based topological sort. Add node to stack after visiting all its descendants. Reverse for order.
// Time: O(V+E) Space: O(V)
import java.util.*;

class Solution {
    public static ArrayList<Integer> topoSort(int V, int[][] edges) {
        ArrayList<Integer> ans = new ArrayList<>();
        ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

        for (int i = 0; i < V; i++)
            adj.add(new ArrayList<>());

        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            adj.get(v).add(u);
        }

        int[] vis = new int[V];

        for (int i = 0; i < V; i++) {
            if (vis[i] == 0)
                dfs(vis, adj, i, ans);
        }

        return ans;
    }

    public static void dfs(int[] vis, ArrayList<ArrayList<Integer>> adj, int u, ArrayList<Integer> ans) {
        vis[u] = 1;
        for (int v : adj.get(u)) {
            if (vis[v] == 0)
                dfs(vis, adj, v, ans);
        }

        ans.add(u);
    }
}

Was this solution helpful?