Topological Sort — Cycle Detection for Build Pipelines

Topological sort is the algorithm behind every dependency resolver, build system, and task scheduler. When you run npm install, pip install, or make, the tool is doing topological sort to figure out the order to install packages — package A must install before package B if B depends on A.

Unlike tree traversal algorithms where the structure forces an ordering, topological sort derives the ordering from the dependency relationships in the graph.

What Is Topological Sort and When Do You Need It?

Topological sort gives you a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u→v, vertex u comes before v. Think of it as figuring out the order to do tasks when some tasks depend on others.

You'll reach for topological sort whenever you're dealing with: - Build systems (Make, Gradle, Bazel) — compile libraries before the modules that depend on them - Package managers (npm, pip, apt) — install dependencies before the package - Task schedulers — run prerequisite tasks before dependent tasks - Spreadsheet formulas — evaluate cells in order so that referenced cells are already computed - Course prerequisite planning — determine a valid semester order

It only works on DAGs. If your graph has a cycle, no valid ordering exists — you'll need to break the cycle first.

Most textbooks present two algorithms: Kahn's (BFS) and DFS-based. Both run in O(V+E) time, but they differ in how they handle cycle detection and space usage.

Kahn's Algorithm — BFS with In-Degrees

Kahn's algorithm processes nodes in topological order by repeatedly removing nodes that have no remaining prerequisites. It's intuitive and naturally detects cycles.

How it works: 1. Compute the in-degree (number of incoming edges) for every node. 2. Enqueue all nodes with in-degree 0 — they have no dependencies. 3. While the queue is non-empty: - Dequeue a node, add it to the result. - For each neighbour, decrement its in-degree by 1 (the prerequisite is now satisfied). - If the neighbour's in-degree becomes 0, enqueue it. 4. After processing, if the result length equals the total number of nodes, the graph is a DAG and the result is a valid topological order. Otherwise, a cycle exists.

Example: Nodes A, B, C, D with edges A→C, B→C, C→D. - In-degrees: A=0, B=0, C=2, D=1. - Queue starts with [A, B]. - Dequeue A: result=[A]; C's in-degree becomes 1. - Dequeue B: result=[A,B]; C's in-degree becomes 0; enqueue C. - Dequeue C: result=[A,B,C]; D's in-degree becomes 0; enqueue D. - Dequeue D: result=[A,B,C,D]. Done. No cycle.

Cycle detection: If at the end result has fewer nodes than total, some nodes never reached in-degree 0 because they're part of a cycle.

# Package: io.thecodeforge.python.dsa

from collections import deque, defaultdict

def topological_sort_kahn(graph, nodes):
    """
    Kahn's algorithm: process nodes with in-degree 0 first.
    Returns sorted order or empty list if cycle detected.
    """
    in_degree = defaultdict(int)
    for node in nodes:
        in_degree[node] = in_degree.get(node, 0)
    for node in graph:
        for neighbour in graph[node]:
            in_degree[neighbour] += 1

    # Start with all nodes that have no dependencies
    queue = deque([n for n in nodes if in_degree[n] == 0])
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)

        for neighbour in graph.get(node, []):
            in_degree[neighbour] -= 1
            if in_degree[neighbour] == 0:
                queue.append(neighbour)

    # If result doesn't contain all nodes, there's a cycle
    return result if len(result) == len(nodes) else []

# Build system example: A → C, B → C, C → D
graph = {'A': ['C'], 'B': ['C'], 'C': ['D'], 'D': []}
nodes = ['A', 'B', 'C', 'D']
print(topological_sort_kahn(graph, nodes))  # ['A', 'B', 'C', 'D'] or ['B', 'A', 'C', 'D']

# Course prerequisite example
courses = {
    'Algorithms':  ['Advanced Algorithms'],
    'Data Structures': ['Algorithms'],
    'Math': ['Data Structures', 'Algorithms'],
    'Advanced Algorithms': []
}
course_nodes = list(courses.keys())
print(topological_sort_kahn(courses, course_nodes))

In-Degree Visualization: Tracing Queue Progression

Seeing the in-degree array evolve and the queue fill and drain helps solidify Kahn's algorithm. Below is a step-by-step visualization for the graph A→C, B→C, C→D.

Initial in-degrees: {A:0, B:0, C:2, D:1}. Queue: [A, B].

Step 1: Dequeue A. A's outgoing edge to C reduces C's in-degree from 2 to 1. Queue: [B].

Step 2: Dequeue B. B's outgoing edge to C reduces C's in-degree from 1 to 0. Enqueue C. Queue: [C].

Step 3: Dequeue C. C's outgoing edge to D reduces D's in-degree from 1 to 0. Enqueue D. Queue: [D].

Step 4: Dequeue D. No outgoing edges. Queue empty. Result: [A, B, C, D].

DAG Visual: Two Valid Topological Orderings

A common source of confusion is that topological order is rarely unique. For the graph A→C, B→C, C→D, both [A, B, C, D] and [B, A, C, D] are valid because A and B have no mutual dependency. In a build system, this means the order of compiling A and B is non-deterministic unless you enforce a tie-breaker.

The following Mermaid diagram shows the DAG and highlights two possible orderings.

C++ Implementation of Kahn's Algorithm

C++ is widely used for performance-critical dependency resolvers (e.g., build systems like Bazel and CMake). Below is a production-ready implementation of Kahn's algorithm with cycle detection, using standard library containers.

The implementation uses std::queue for BFS processing, std::unordered_map for in-degree tracking, and std::vector for the graph adjacency list. Cycle detection is performed by comparing the result size to the number of nodes.

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_map>
#include <algorithm>

// Edges: vector of pairs (from, to)
std::vector<int> topologicalSort(int V, const std::vector<std::pair<int,int>>& edges) {
    // Build adjacency list and in-degree map
    std::vector<std::vector<int>> adj(V);
    std::vector<int> inDegree(V, 0);
    for (const auto& e : edges) {
        adj[e.first].push_back(e.second);
        inDegree[e.second]++;
    }

    // Queue nodes with in-degree 0
    std::queue<int> q;
    for (int i = 0; i < V; i++) {
        if (inDegree[i] == 0) q.push(i);
    }

    std::vector<int> result;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        result.push_back(u);

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

    // If result doesn't contain all nodes, cycle exists
    if (result.size() != V) return {};
    return result;
}

int main() {
    // Example: A=0, B=1, C=2, D=3
    // Edges: 0->2, 1->2, 2->3
    std::vector<std::pair<int,int>> edges = {{0,2}, {1,2}, {2,3}};
    auto order = topologicalSort(4, edges);

    if (order.empty()) {
        std::cout << "Cycle detected!" << std::endl;
    } else {
        std::cout << "Topological order: ";
        for (int v : order) std::cout << v << " ";
        std::cout << std::endl;
    }
    return 0;
}

DFS-Based Topological Sort — Post-Order Processing

The DFS approach uses a recursive or iterative depth-first traversal. When DFS finishes exploring all neighbours of a node (i.e., on backtracking), the node is added to a list. Since a node is added only after all its descendants have been processed, the list (when reversed) gives a topological order.

How it works: 1. Mark all nodes as unvisited. 2. For each unvisited node, run DFS: - Mark the node as 'in progress' (gray) to detect cycles. - For each neighbour: - If neighbour is 'in progress', a cycle exists — stop. - If neighbour is unvisited, recursively visit it. - After all neighbours processed, mark node as 'done' and add it to the result stack. 3. After all nodes visited, reverse the stack to get topological order.

Cycle detection: If we encounter a node that is currently on the recursion stack (gray), there's a back-edge → cycle.

Example: Same graph A→C, B→C, C→D. - Start DFS from A: visit A, then C (from A), then D. Backtrack: push D, push C, push A. - Then DFS from B: visit B, then C (already done, skip). Backtrack: push B. - Stack (top to bottom): D, C, A, B → reverse: A, B, C, D (or B, A, C, D depending on order).

Recursion depth risk: In production graphs with deep chains, recursive DFS can overflow the call stack. Use an explicit stack or iterative DFS with manual stack to avoid this.

# Package: io.thecodeforge.python.dsa

def topological_sort_dfs(graph, nodes):
    visited  = set()      # fully processed
    in_stack = set()      # currently on recursion stack (gray)
    result   = []
    has_cycle = [False]

    def dfs(node):
        if has_cycle[0]:
            return
        in_stack.add(node)
        visited.add(node)

        for neighbour in graph.get(node, []):
            if neighbour in in_stack:  # back edge = cycle
                has_cycle[0] = True
                return
            if neighbour not in visited:
                dfs(neighbour)

        in_stack.discard(node)
        result.append(node)  # add AFTER all descendants processed

    for node in nodes:
        if node not in visited:
            dfs(node)

    if has_cycle[0]:
        return []  # cycle detected
    return result[::-1]  # reverse for topological order

graph = {'A': ['C'], 'B': ['C'], 'C': ['D'], 'D': []}
print(topological_sort_dfs(graph, ['A', 'B', 'C', 'D']))
# ['A', 'B', 'C', 'D'] — or ['B', 'A', 'C', 'D']

# Cycle detection
cyclic = {'A': ['B'], 'B': ['C'], 'C': ['A']}
print(topological_sort_dfs(cyclic, ['A', 'B', 'C']))  # []

Cycle Detection in Dependency Graphs

A cycle in a dependency graph means A depends on B which depends on C which depends on A — an impossible situation. Both topological sort algorithms detect cycles, but the information they provide differs.

Kahn's algorithm: If the result list contains fewer nodes than the total, a cycle exists. However, it doesn't tell you which nodes are in the cycle. You can find the cycle by removing all processed nodes from the graph and looking at the remaining subgraph — it will consist entirely of cycles.

DFS approach: When you encounter a back-edge (neighbour in the current recursion stack), you have a cycle. You can trace the cycle by walking back through the recursion stack until you hit the neighbour again.

In production: Don't just detect the cycle — report the cycle path. Tools like npm and Make do this: they print the exact dependency chain that forms the cycle, saving hours of manual debugging.

Real-world example: A microservice dependency graph where service A calls B, B calls C, and C calls A. This won't be caught by build systems but can cause cascading failures at runtime. Use static analysis with topological sort to detect such cycles before deployment.

Real-World Applications: Build Systems, Package Managers, and More

Topological sort is the unsung hero behind your daily development tools.

Package managers (npm, pip, apt): When you run npm install, npm reads the dependency tree, resolves conflicts, and then topologically sorts packages so that package A (which B depends on) is installed before B. If a cycle exists, npm reports it and refuses to install.

Build systems (Make, Gradle, Bazel): The build system computes the dependency graph of source files and test files. Topological sort tells it which files to compile first. If a cycle is found (e.g., header file A includes B which includes A), the build fails with a clear error message.

Spreadsheet formulas: When you write =A1+B1, the spreadsheet calculates the dependency graph of cells. Topological sort ensures that referenced cells are computed before the cells that reference them. Circular references cause #REF! errors.

Compiler optimization: Compilers use topological sort on basic block dependency graphs to reorder instructions for better pipelining.

Task scheduling in distributed systems: Workflow engines like Airflow and Dagster use topological sort to determine task execution order in a DAG. Cycles in the DAG definition cause scheduling failures.

Kahn's vs DFS: When to Use Which in Production

Both algorithms produce valid topological orders and run in O(V+E) time. The choice depends on your constraints.

Choose Kahn's algorithm when: - You need explicit cycle detection (result length check is trivial) - You have very deep dependency chains (no recursion depth risk) - You want deterministic tie-breaking (just sort the initial queue) - You're processing a graph where nodes become ready dynamically (e.g., streaming tasks)

Choose DFS when: - You already have DFS traversal for other reasons (e.g., strongly connected components) - You need to report the exact cycle path (DFS can give you the cycle by inspecting the recursion stack) - You're working with a small graph and prefer recursive simplicity

Performance considerations: Both are equally efficient in theory, but Kahn's algorithm has lower constant factors because it doesn't need to track recursion states. In practice, Kahn's is the default choice for most implementations.

Memory: Kahn's needs a queue that may hold up to V nodes. DFS needs a recursion stack that may hold up to V nodes. Both are O(V).

Advantages and Disadvantages of Topological Sort

Topological sort is a powerful tool for dependency resolution, but it has trade-offs. The following table summarizes the key advantages and disadvantages.

Understanding these trade-offs helps you decide when topological sort is appropriate and when you need to combine it with other techniques (e.g., priority queues for weighting, or cycle detection for dynamic graphs).

Practice Problems for Topological Sort

Master topological sort by solving these curated problems. They range from classic cycle detection to real-world scheduling tasks. All problems require Kahn's algorithm (BFS) or DFS-based sorting.

• LeetCode 207 — Course Schedule: Determine if you can finish all courses given prerequisites. Classic Kahn's algorithm.
• LeetCode 210 — Course Schedule II: Return a valid order of courses. Similar to 207 but requires the actual ordering.
• CSES — Courses: A simple DAG ordering problem from the CSES problem set.
• SPOJ — TOPOSORT: Topological sorting on a graph with up to 10,000 nodes. Tests performance and memory handling.
• LeetCode 329 — Longest Increasing Path in a Matrix: Use topological sort on a grid to find the longest increasing path.
• GeeksforGeeks — Alien Dictionary: Given a sorted dictionary, find the order of characters. Build a graph and apply topological sort.
• Codeforces — 510C (Fox And Names): Similar to Alien Dictionary but with constraints on lexicographic order.

Start with LeetCode 207/210 to solidify the basics, then move to CSES and SPOJ for more challenging input sizes. The Alien Dictionary problem is a popular interview favorite.

Topological Sort on Streaming Data — Why In-Degree Updates Fail Under Concurrency

Your build pipeline fans out 500 microservices. You run Kahn's on the dependency graph and it works locally. In production, workers race on shared in-degree counters and suddenly service X deploys before its database migration completes. Classic.

Kahn's algorithm assumes a static snapshot of edges. That's fine for offline DAGs, but real dependency graphs mutate — new packages publish, CI jobs retry, nodes get reprocessed. The fix isn't locking. It's idempotent edge handling with a versioned in-degree store.

Here's the production pattern: instead of decrementing an integer, model each dependency as a set of satisfied conditions. When a condition fires, you atomically add to a SatisfiedPredecessors set. Only when |SatisfiedPredecessors| == originalInDegree does the node become ready. This survives reordering, retries, and partial failures. You also need a lazy frontier — never pop from the queue eagerly. Batch-drain nodes whose conditions are fully met, then recheck after a timeout.

Your scheduler becomes eventually consistent. That's fine for builds. What isn't fine is thinking integers are thread-safe.

// io.thecodeforge — dsa tutorial

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

public class ConcurrentBuildScheduler {

    static class Task {
        final String name;
        final Set<String> dependencies = ConcurrentHashMap.newKeySet();
        final Set<String> satisfied = ConcurrentHashMap.newKeySet();
        final int required;

        Task(String name, Set<String> deps) {
            this.name = name;
            this.dependencies.addAll(deps);
            this.required = deps.size();
        }

        boolean isReady() {
            return satisfied.size() >= required;
        }

        void markSatisfied(String predecessor) {
            satisfied.add(predecessor);
        }
    }

    private final Map<String, Task> graph = new ConcurrentHashMap<>();

    public void addTask(String name, Set<String> deps) {
        graph.put(name, new Task(name, deps));
    }

    public void notifyCompletion(String taskName) {
        Task completed = graph.get(taskName);
        if (completed == null) return;
        // Propagate completion to downstream tasks
        for (Task downstream : graph.values()) {
            if (downstream.dependencies.contains(taskName)) {
                downstream.markSatisfied(taskName);
            }
        }
    }

    public List<String> getReadyTasks() {
        List<String> ready = new ArrayList<>();
        for (Task task : graph.values()) {
            if (task.isReady() && !task.marked) { // assume a boolean flag
                ready.add(task.name);
            }
        }
        return ready;
    }

    public static void main(String[] args) throws InterruptedException {
        ConcurrentBuildScheduler scheduler = new ConcurrentBuildScheduler();
        scheduler.addTask("db-migrate", new HashSet<>(Set.of()));
        scheduler.addTask("api-service", new HashSet<>(Set.of("db-migrate")));
        scheduler.addTask("web-ui", new HashSet<>(Set.of("api-service")));

        scheduler.notifyCompletion("db-migrate");
        Thread.sleep(100); // simulate async propagation
        System.out.println("Ready tasks: " + scheduler.getReadyTasks());
    }
}

Partial Ordering on Unstable Graphs — Why DFS Fails When Edges Appear Mid-Run

You've got a live dependency graph where services register themselves during startup, or CI jobs spawn new steps dynamically. You reach for DFS-based topological sort because the recursive elegance is tempting. Then your sort throws a StackOverflowError or produces an ordering that silently violates constraints.

DFS fails here because it assumes the graph is complete when you call dfs(). If node B gets an incoming edge from node C after you've already visited B, your post-order stack is now wrong. Kahn's is better, but even Kahn's assumes you know all edges upfront.

The fix for dynamic graphs is a topological sort that supports incremental edge insertion. You maintain a total order via a SortedMap<Integer, String> where keys are "layers" — the longest path from any source node. When a new edge appears, you recompute the layer of the target if it's <= source's layer, propagate the bump downstream via BFS. This is called "online topological sort" or "incremental topological ordering." It's O(V+E) per edge insertion in the worst case, but amortised lower if the graph is mostly stable.

Production lesson: if your DAG changes after you start processing, don't sort. Re-sort or use an incremental algorithm. And never use recursion for DFS on any graph with more than 10,000 nodes unless you want a fire drill.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class IncrementalTopologicalSorter {

    private final Map<String, Integer> layers = new HashMap<>();
    private final Map<String, List<String>> adjacency = new HashMap<>();

    public void addNode(String node) {
        layers.putIfAbsent(node, 0);
        adjacency.putIfAbsent(node, new ArrayList<>());
    }

    public void addEdge(String from, String to) {
        addNode(from);
        addNode(to);
        adjacency.get(from).add(to);

        // If new edge violates order, bump layers
        int fromLayer = layers.get(from);
        int toLayer = layers.get(to);
        if (toLayer <= fromLayer) {
            layers.put(to, fromLayer + 1);
            // Propagate to downstream nodes (BFS)
            Queue<String> queue = new LinkedList<>();
            queue.add(to);
            while (!queue.isEmpty()) {
                String current = queue.poll();
                int currentLayer = layers.get(current);
                for (String child : adjacency.get(current)) {
                    if (layers.get(child) <= currentLayer) {
                        layers.put(child, currentLayer + 1);
                        queue.add(child);
                    }
                }
            }
        }
    }

    public List<String> sort() {
        List<Map.Entry<String, Integer>> entries = new ArrayList<>(layers.entrySet());
        entries.sort(Map.Entry.comparingByValue());
        List<String> sorted = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : entries) {
            sorted.add(entry.getKey());
        }
        return sorted;
    }

    public static void main(String[] args) {
        IncrementalTopologicalSorter sorter = new IncrementalTopologicalSorter();
        sorter.addEdge("build", "test");
        sorter.addEdge("test", "deploy");
        sorter.addEdge("deploy", "monitor");

        // New edge inserted dynamically: test depends on lint
        sorter.addEdge("lint", "test");

        System.out.println("Order: " + sorter.sort());
    }
}

Why Your Build System Crashes: Cycle Detection in Live Dependency Graphs

You think a cycle is just a textbook error? In production, a circular dependency means your build system hangs forever, a package manager refuses to install, or your task scheduler deadlocks at 3 AM. Topological sort only works on DAGs — if there's a cycle, both Kahn's and DFS will tell you exactly where the graph broke.

Kahn's algorithm detects cycles trivially: if the queue empties but not all nodes are processed, edges remain. That leftover edge is your smoking gun. DFS-based detection is subtler — you need a recursion stack. If you revisit a node currently on the call stack, you've got a cycle. Don't confuse this with revisiting a fully processed node; that's just a DAG with multiple paths.

In production, you never trust the graph. Always validate. Always report the cycle. Your CI pipeline depends on it, and nobody wants to debug a silent deadlock.

// io.thecodeforge — dsa tutorial

import java.util.*;

class DependencyGraph {
    // Returns first cycle node or -1
    static int findCycle(Map<Integer, List<Integer>> graph) {
        int n = graph.size();
        boolean[] visited = new boolean[n];
        boolean[] onStack = new boolean[n];
        
        for (int v = 0; v < n; v++) {
            if (hasCycle(v, graph, visited, onStack)) return v;
        }
        return -1;
    }
    
    static boolean hasCycle(int v, Map<Integer, 
            List<Integer>> g, boolean[] vis, boolean[] stack) {
        if (stack[v]) return true;
        if (vis[v]) return false;
        vis[v] = true;
        stack[v] = true;
        for (int nbr : g.getOrDefault(v, List.of())) {
            if (hasCycle(nbr, g, vis, stack)) return true;
        }
        stack[v] = false;
        return false;
    }
}

Performance Fire: Why Big-O Hides Memory Blowups in Large-Scale Graphs

Everyone parrots O(V+E) for topological sort. Nobody warns you that adjacency lists for 10 million nodes consume gigabytes. Kahn's algorithm needs an in-degree array and a queue — that's cheap. But the graph representation itself is the real cost.

Adjacency lists using HashMap<Integer, List<Integer>> are fine for 10K nodes. For 10M edges, you're looking at 500MB+ in overhead alone. Java's Integer boxing adds another 16 bytes per entry. At scale, you must use primitive collections (fastutil, trove) or flat arrays. Otherwise your "efficient" topological sort triggers GC pauses every 10 seconds.

For streaming graphs where edges arrive continuously, you can't even store the whole graph. Compute in-degree deltas incrementally and forget the edges. Your bottleneck isn't the algorithm — it's the data structure. Optimize memory first, then measure runtime.

// io.thecodeforge — dsa tutorial

// Compact representation for large graphs
class CompactGraph {
    int[] edges;        // flat array of edges [src, dst, src, dst, ...]
    int[] nodeOffset;   // start index for each node's neighbors
    int[] inDegree;     // deg for Kahn's
    
    // For 10M edges: edges[20M], nodeOffset[N+1], inDegree[N]
    // ≈ 160MB total vs 500MB+ with HashMap
    
    int[] topologicalOrder(int n) {
        int[] order = new int[n];
        int[] q = new int[n];
        int head = 0, tail = 0;
        
        for (int v = 0; v < n; v++) {
            if (inDegree[v] == 0) q[tail++] = v;
        }
        
        int idx = 0;
        while (head < tail) {
            int v = q[head++];
            order[idx++] = v;
            for (int i = nodeOffset[v]; i < nodeOffset[v+1]; i++) {
                int nbr = edges[i];
                if (--inDegree[nbr] == 0) q[tail++] = nbr;
            }
        }
        return order;
    }
}

Related Articles: Deepening Your Mastery of Topological Sort

Understanding topological sort in isolation is useful, but its true power emerges when connected to adjacent concepts. For example, the relationship between topological ordering and shortest-path algorithms in Directed Acyclic Graphs (DAGs) is profound—a topologically sorted DAG allows O(V+E) dynamic programming solutions for longest paths or critical paths. Explore how cycle detection logic from topological sort directly enables deadlock detection algorithms in operating systems, where resource allocation graphs mirror dependency graphs. Additionally, the partial order semantics of topological sort underpin conflict resolution in distributed version control systems like Git, where commit histories require merging linear sequences. For performance tuning, review how adjacency list representations impact memory locality in large-scale graph processing frameworks (e.g., Apache Spark's GraphX). Finally, contrast topological sort with topological ordering in hypergraphs or with probabilistic graphical models (Bayesian networks) where ordering constraints drive inference efficiency.

// io.thecodeforge — dsa tutorial
// Shortest path using topological order
import java.util.*;
public class RelatedDfsExample {
    public int[] shortestPath(int V, List<int[]> edges, int src) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[V];
        for (int[] e : edges) {
            adj.get(e[0]).add(new int[]{e[1], e[2]});
            indeg[e[1]]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < V; i++) if (indeg[i] == 0) q.add(i);
        int[] topo = new int[V]; int idx = 0;
        while (!q.isEmpty()) { int u = q.poll(); topo[idx++] = u;
            for (int[] v : adj.get(u)) if (--indeg[v[0]] == 0) q.add(v[0]); }
        int[] dist = new int[V]; Arrays.fill(dist, Integer.MAX_VALUE); dist[src] = 0;
        for (int u : topo) if (dist[u] != Integer.MAX_VALUE)
            for (int[] v : adj.get(u)) if (dist[u] + v[1] < dist[v[0]]) dist[v[0]] = dist[u] + v[1];
        return dist;
    }
}

Related Articles: Bridging Theory and Production Systems

Topological sort does not exist in a vacuum—it connects to several high-impact areas in system design and algorithm theory. First, study the connection between topological order and the Longest Path Problem (LP) in DAGs, which is polynomial-time solvable only via topological sort and contradicts NP-hardness of general LP—a key insight for interview and system design contexts. Second, explore how topological sort relates to the concept of linear extensions in posets, critical for scheduling algorithms in real-time systems like rate-monotonic scheduling. Third, examine the relationship with BFS and DFS variations in graph algorithms for transitive closure computation (e.g., Floyd-Warshall vs. topological DP). Fourth, for concurrent systems, investigate how optimistic concurrency control (OCC) uses a partial order similar to topological sort to detect conflicts during transaction commit, avoiding locks. Finally, review implementing topological sort on GPU architectures (CUDA) to handle millions of dependencies with parallelized Kahn's algorithm using vertex-centric partitioning.

// io.thecodeforge — dsa tutorial
// Longest path in DAG via topological sort
import java.util.*;
public class LongestPathDP {
    public int longestPath(int V, List<int[]> edges) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        int[] indeg = new int[V];
        for (int[] e : edges) { adj.get(e[0]).add(new int[]{e[1], e[2]}); indeg[e[1]]++; }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < V; i++) if (indeg[i] == 0) q.add(i);
        int[] topo = new int[V]; int idx = 0;
        while (!q.isEmpty()) { int u = q.poll(); topo[idx++] = u;
            for (int[] v : adj.get(u)) if (--indeg[v[0]] == 0) q.add(v[0]); }
        int[] dist = new int[V];
        for (int u : topo) for (int[] v : adj.get(u))
            if (dist[u] + v[2] > dist[v[0]]) dist[v[0]] = dist[u] + v[2];
        int max = 0; for (int d : dist) max = Math.max(max, d);
        return max;
    }
}