DEV Community

DevCorner2
DevCorner2

Posted on

🔥 Blog 2: Topological Sort & Kahn’s Algorithm in DSA

When you have tasks with dependencies — like building software modules, scheduling jobs, or determining course prerequisites — you need to process tasks in a valid order. This is where Topological Sorting comes in.

🔹 What is Topological Sort?

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

  • Only valid for DAGs (Directed Acyclic Graphs).
  • Multiple valid orders may exist.

🔹 Applications

  • Course scheduling (Course Schedule problem on LeetCode).
  • Task scheduling in Operating Systems.
  • Build systems (Maven, Gradle, Makefiles).
  • Dependency resolution in package managers (npm, pip, apt).

🔹 Approaches to Topological Sort

1. DFS-based Topological Sort

  • Perform a DFS, push nodes into a stack after visiting all children.
  • Pop stack to get topological order.

Java Code:

import java.util.*;

class DFSTopoSort {
    private int V;
    private List<List<Integer>> adj;

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

    void addEdge(int u, int v) {
        adj.get(u).add(v);
    }

    void topoSort() {
        boolean[] visited = new boolean[V];
        Stack<Integer> stack = new Stack<>();

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

        while (!stack.isEmpty()) {
            System.out.print(stack.pop() + " ");
        }
    }

    void dfs(int v, boolean[] visited, Stack<Integer> stack) {
        visited[v] = true;
        for (int nei : adj.get(v)) {
            if (!visited[nei]) dfs(nei, visited, stack);
        }
        stack.push(v);
    }

    public static void main(String[] args) {
        DFSTopoSort g = new DFSTopoSort(6);
        g.addEdge(5, 2);
        g.addEdge(5, 0);
        g.addEdge(4, 0);
        g.addEdge(4, 1);
        g.addEdge(2, 3);
        g.addEdge(3, 1);

        System.out.println("Topological Sort (DFS):");
        g.topoSort();
    }
}
Enter fullscreen mode Exit fullscreen mode

Output Example:

5 4 2 3 1 0
Enter fullscreen mode Exit fullscreen mode

2. Kahn’s Algorithm (BFS-based)

  • Count in-degree (number of incoming edges) for each node.
  • Start with nodes having in-degree = 0.
  • Repeatedly remove nodes and reduce in-degree of neighbors.

Java Code:

import java.util.*;

class KahnsAlgorithm {
    private int V;
    private List<List<Integer>> adj;

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

    void addEdge(int u, int v) {
        adj.get(u).add(v);
    }

    void topoSort() {
        int[] indegree = new int[V];
        for (int u = 0; u < V; u++) {
            for (int v : adj.get(u)) {
                indegree[v]++;
            }
        }

        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < V; i++) {
            if (indegree[i] == 0) q.offer(i);
        }

        List<Integer> topoOrder = new ArrayList<>();
        while (!q.isEmpty()) {
            int node = q.poll();
            topoOrder.add(node);

            for (int nei : adj.get(node)) {
                indegree[nei]--;
                if (indegree[nei] == 0) q.offer(nei);
            }
        }

        if (topoOrder.size() != V) {
            System.out.println("Graph has a cycle! No Topological Order exists.");
        } else {
            System.out.println("Topological Sort (Kahn’s): " + topoOrder);
        }
    }

    public static void main(String[] args) {
        KahnsAlgorithm g = new KahnsAlgorithm(6);
        g.addEdge(5, 2);
        g.addEdge(5, 0);
        g.addEdge(4, 0);
        g.addEdge(4, 1);
        g.addEdge(2, 3);
        g.addEdge(3, 1);

        g.topoSort();
    }
}
Enter fullscreen mode Exit fullscreen mode

Output Example:

Topological Sort (Kahn’s): [4, 5, 2, 3, 1, 0]
Enter fullscreen mode Exit fullscreen mode

🔹 Key Differences (DFS vs Kahn’s)

Aspect DFS-based Kahn’s Algorithm (BFS)
Method Uses recursion + stack Uses queue + in-degree
Detect cycle Indirect (via visited + recursion stack) Direct (if nodes remain unprocessed)
Space O(V) O(V)
Use case Recursive backtracking style problems Dependency scheduling, course schedule

🔹 Real-World Example: Course Scheduling

LeetCode #207, #210 use Kahn’s Algorithm directly.

  • Courses = Nodes
  • Prerequisites = Directed Edges
  • If cycle → impossible schedule.

✅ Key Takeaways

  • Topological Sort works only for DAGs.
  • DFS method is intuitive, good for recursion lovers.
  • Kahn’s Algorithm is practical for dependency resolution and cycle detection.

👉 Next in this series (Blog 3) we’ll go to Pattern 17: Segment Tree & Fenwick Tree (BIT) — mastering range queries and updates.

Top comments (0)