Topological sort is the algorithmic equivalent of organizing chaos. Here's how it helps you conquer dependency problems and ace graph questions in interviews.

🧠 What Is Topological Sort?

Imagine you're trying to make a lasagna, but first you need to boil the pasta, chop the onions, and grate the cheese. Some steps depend on others. You can't bake the lasagna before you assemble it. Welcome to the world of Directed Acyclic Graphs (DAGs) — and topological sorting is your recipe.

➕ Definition

A topological sort of a DAG is a linear ordering of its vertices such that for every directed edge u → v, u comes before v.

🎯 Why Should You Care?

Topological sort is a must-have tool for:

  • Dependency resolution (package installers, build systems)
  • Course scheduling (prerequisites)
  • Job/task scheduling
  • Compiling code with imports
  • Interview questions at companies that love graph questions (cough Google, Meta, Amazon…)

📦 Real-World Examples

npm install: You can't install package B before package A if B depends on A.

make build: Compilers use topological sorting to decide the order of building files.

Course planners: Taking "Algorithms" before "Advanced Algorithms" is kind of the point.

🧩 When Is Topological Sort Possible?

Only when the graph is a DAG:

  • Directed: Because dependencies have a direction.
  • Acyclic: No loops. You can't depend on yourself — that's just unhealthy.

🧮 How Does It Work?

There are two classic approaches:

✅ 1. Kahn's Algorithm (BFS-based)

This one works by finding all nodes with no incoming edges (in-degree = 0) and gradually removing them from the graph.

Steps:

  1. Compute in-degree of all nodes.
  2. Add all nodes with in-degree 0 to a queue.
  3. While queue is not empty:
  • Pop node, add to result.
  • Decrease in-degree of its neighbors.
  • If in-degree becomes 0, add to queue.

4. If result length != total nodes → cycle exists.

Time Complexity: O(V + E) Space Complexity: O(V + E)

public List<Integer> topoSort(int[][] edges, int n) {

    List<List<Integer>> graph = new ArrayList<>();
    int[] inDegree = new int[n];
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        inDegree[edge[1]]++;
    }

    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) queue.offer(i);
    }

    List<Integer> result = new ArrayList<>();
    while (!queue.isEmpty()) {
        int curr = queue.poll();
        result.add(curr);
        for (int neighbor : graph.get(curr)) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] == 0) queue.offer(neighbor);
        }
    }

    return result.size() == n ? result : new ArrayList<>(); // return empty if cycle
}

🧘 2. DFS-Based Topological Sort

This one's a bit more recursive and elegant. You go deep, finish everything downstream, and then record the current node.

Steps:

  1. Use a visited set (or array).
  2. Recursively DFS on each unvisited node.
  3. After exploring all neighbors, push node onto stack.
  4. At the end, reverse the stack = topological order.

Time Complexity: O(V + E)

public List<Integer> topoSortDFS(int[][] edges, int n) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] edge : edges) graph.get(edge[0]).add(edge[1]);

    boolean[] visited = new boolean[n];
    Stack<Integer> stack = new Stack<>();

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

    List<Integer> result = new ArrayList<>();
    while (!stack.isEmpty()) result.add(stack.pop());
    return result;
}

private void dfs(int node, List<List<Integer>> graph, boolean[] visited, Stack<Integer> stack) {
    visited[node] = true;
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) dfs(neighbor, graph, visited, stack);
    }
    stack.push(node);
}

🧨 Interview Gotchas

  • Graph isn't a DAG? Detect cycles! Topological sort doesn't work if cycles exist.
  • Disconnected components? Make sure you visit all nodes.
  • 1-based or 0-based indexing? Know the input format before you go full BFS warrior.
  • Multiple valid orderings? That's normal — topological sort isn't unique.

🧠 Conclusion

None

🧵 Final Words

Topological sort turns a chaotic web of dependencies into an elegant execution order. Whether you're solving coding interviews, writing compilers, or organizing your weekend chores — understanding topological sort means you think like a real engineer.

Learn it. Master it. Apply it.

That's all folks here! Before you go: