🏗️ Topological Sort & DAG Problems

This content originally appeared on DEV Community and was authored by Dev Cookies

When dealing with Directed Acyclic Graphs (DAGs), ordering of vertices becomes a powerful tool. This is where Topological Sort comes into play.

It’s the backbone of problems like course scheduling, dependency resolution, and task scheduling.

🔑 What is Topological Sort?

A linear ordering of vertices such that for every directed edge u → v, vertex u comes before v.
Only valid in DAGs (Directed Acyclic Graphs).
Multiple valid orders may exist.

Example:
Graph:

Possible topological order: 1, 4, 5, 2, 3.

⚡ Approaches

1. DFS-Based Topological Sort

Perform DFS.
After visiting all neighbors of a node, push it onto a stack.
At the end, pop elements from the stack = topological order.

Java Snippet (DFS-based):

import java.util.*;

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

    public static List<Integer> topoSort(int n, List<List<Integer>> graph) {
        boolean[] visited = new boolean[n];
        Stack<Integer> stack = new Stack<>();

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

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

    public static void main(String[] args) {
        int n = 6;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        graph.get(5).add(2);
        graph.get(5).add(0);
        graph.get(4).add(0);
        graph.get(4).add(1);
        graph.get(2).add(3);
        graph.get(3).add(1);

        System.out.println("Topological Sort (DFS): " + topoSort(n, graph));
    }
}

✅ Output Example:

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

2. Kahn’s Algorithm (BFS-based)

Compute indegree (number of incoming edges) for each vertex.
Put vertices with indegree = 0 in a queue.
Remove them one by one, decrease indegree of neighbors.
Continue until queue is empty.

Java Snippet (Kahn’s Algorithm):

import java.util.*;

public class TopoSortBFS {
    public static List<Integer> topoSort(int n, List<List<Integer>> graph) {
        int[] indegree = new int[n];
        for (int i = 0; i < n; i++) {
            for (int nei : graph.get(i)) {
                indegree[nei]++;
            }
        }

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

        List<Integer> result = new ArrayList<>();
        while (!q.isEmpty()) {
            int node = q.poll();
            result.add(node);
            for (int nei : graph.get(node)) {
                indegree[nei]--;
                if (indegree[nei] == 0) q.add(nei);
            }
        }

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

    public static void main(String[] args) {
        int n = 6;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        graph.get(5).add(2);
        graph.get(5).add(0);
        graph.get(4).add(0);
        graph.get(4).add(1);
        graph.get(2).add(3);
        graph.get(3).add(1);

        System.out.println("Topological Sort (BFS/Kahn): " + topoSort(n, graph));
    }
}

🎯 Common Problems

Course Schedule (LeetCode 207) → detect cycle in DAG using BFS/DFS.
Course Schedule II (LeetCode 210) → return valid topological order.
Alien Dictionary → infer letter order using topological sort.
Task Scheduling with Dependencies → check if valid execution order exists.

⚡ Key Insights

DFS is recursive & stack-based → good for implementation, but harder for cycle detection.
Kahn’s algorithm (BFS) → directly checks cycles (if some nodes never get indegree=0).
Works only in DAGs → cycle detection is often integrated.

📌 With this, you’ve mastered ordering in DAGs — a must-have skill for scheduling and dependency problems.

This content originally appeared on DEV Community and was authored by Dev Cookies

Print Share Comment Cite Upload Translate Updates

APA

Dev Cookies | Sciencx (2025-09-01T12:51:24+00:00) 🏗️ Topological Sort & DAG Problems. Retrieved from https://www.scien.cx/2025/09/01/%f0%9f%8f%97%ef%b8%8f-topological-sort-dag-problems/

MLA

" » 🏗️ Topological Sort & DAG Problems." Dev Cookies | Sciencx - Monday September 1, 2025, https://www.scien.cx/2025/09/01/%f0%9f%8f%97%ef%b8%8f-topological-sort-dag-problems/

HARVARD

Dev Cookies | Sciencx Monday September 1, 2025 » 🏗️ Topological Sort & DAG Problems., viewed ,<https://www.scien.cx/2025/09/01/%f0%9f%8f%97%ef%b8%8f-topological-sort-dag-problems/>

VANCOUVER

Dev Cookies | Sciencx - » 🏗️ Topological Sort & DAG Problems. [Internet]. [Accessed ]. Available from: https://www.scien.cx/2025/09/01/%f0%9f%8f%97%ef%b8%8f-topological-sort-dag-problems/

CHICAGO

" » 🏗️ Topological Sort & DAG Problems." Dev Cookies | Sciencx - Accessed . https://www.scien.cx/2025/09/01/%f0%9f%8f%97%ef%b8%8f-topological-sort-dag-problems/

IEEE

" » 🏗️ Topological Sort & DAG Problems." Dev Cookies | Sciencx [Online]. Available: https://www.scien.cx/2025/09/01/%f0%9f%8f%97%ef%b8%8f-topological-sort-dag-problems/. [Accessed: ]

rf:citation

» 🏗️ Topological Sort & DAG Problems | Dev Cookies | Sciencx | https://www.scien.cx/2025/09/01/%f0%9f%8f%97%ef%b8%8f-topological-sort-dag-problems/ |

Please log in to upload a file.

There are no updates yet.
Click the Upload button above to add an update.

You must be logged in to translate posts. Please log in or register.