Topological Sorting in DAGs: Algorithms, Applications, and Step-by-Step Guide

Efficient dependency management is critical in modern computing, from parallel processing to large-scale workflow automation. Topological sorting in DAGs provides a structured way to handle dependencies by arranging nodes in a sequence where each node appears before those that rely on it. This ordering is determined by analyzing directed edges, ensuring tasks execute in the correct sequence without conflicts.

With the rise of cloud computing, CI/CD pipelines, and real-time data processing, algorithms for topological sorting in DAGs optimize execution. Tools like Make, Gradle, Apache Airflow, and Spark rely on DAG-based scheduling to prevent bottlenecks. This guide explores key algorithms like Kahn’s and DFS.

Understanding Topological Sorting in DAGs and Its Importance

Topological sorting in a DAG arranges nodes in a linear sequence where each directed edge (u → v) ensures u appears before v. This is crucial for managing dependencies in scheduling, workflow automation, and data processing. 

Topological sorting can only be done in Directed Acyclic Graphs (DAGs) because cycles would create conflicts in ordering. If a cycle exists, no valid order can be established since a node would depend on itself.

Example of a DAG and Its Topological Order:

Consider a DAG with the following directed edges:
A → B, A → C, B → D, C → D

One valid topological order is: A, B, C, D

Key Properties and Applications:

• DAGs always have at least one valid topological order, ensuring structured execution.
• If a cycle exists, sorting is impossible, making cycle detection crucial in dependency management.
• Software build systems (Make, Gradle, Bazel) use topological sorting to determine compilation order.
• Task scheduling in cloud computing (Apache Airflow, Kubernetes DAGs) ensures proper execution of dependent jobs.
• Course prerequisite planning in universities relies on DAGs to determine valid study sequences.

A DAG can have multiple valid topological orders, depending on how independent nodes and paths are processed—let’s explore why.

Why Does Topological Sorting Have Multiple Valid Orders?

Topological sorting doesn’t always yield a single order because multiple independent nodes can be placed in different sequences while still respecting dependencies. The final order depends on the processing approach, making it flexible for various applications.

Example Demonstrating Multiple Orders

Using the same DAG from earlier:
 A → B, A → C, B → D, C → D

Two valid topological orders are:

1. A, B, C, D
2. A, C, B, D

Both sequences follow the rule that A appears before B and C, and B and C appear before D.

Importance of Multiple Orders

• Fault Tolerance: In distributed systems, if one execution path fails, another valid order can be used for recovery.
• Custom Prioritization: Different industries may prioritize tasks differently—e.g., in supply chain logistics, dependencies may be ordered based on urgency.
• Optimized Graph Traversal: Some machine learning pipelines reorder data processing tasks dynamically for efficiency.
• Version Control Systems: In Git, commits with no direct dependencies can be ordered differently when merging branches.

The ability to compute a valid topological order efficiently is crucial for handling large-scale dependency graphs—let’s examine the key algorithms.

Efficient Algorithms for Topological Sorting in DAGs

Topological sorting requires efficient methods to determine a valid execution order, especially in large-scale scheduling, dependency resolution, and workflow automation. Two primary approaches are widely used:

• DFS-Based Approach: Uses recursion and a stack to explore nodes and determine order.
• BFS-Based Approach (Kahn’s Algorithm): Uses in-degree tracking and a queue to process nodes iteratively.

Each algorithm follows a distinct strategy to determine a valid topological order. Let's start with the DFS-based approach.

Depth-First Search (DFS) Approach for Topological Sorting

DFS-based topological sorting explores nodes deeply before backtracking, ensuring each node is processed only after its dependencies have been visited. This guarantees a valid execution order, making DFS a powerful method for dependency resolution in large-scale graphs.

How DFS-Based Topological Sorting Works?

• Start from an unvisited node and recursively explore all its outgoing edges.
• Once a node’s dependencies are visited, push it onto a stack, ensuring it appears later in the final order.
• Backtracking from leaf nodes naturally produces a valid topological sequence.
• After visiting all nodes, pop elements from the stack to retrieve the sorted order.

Why Does DFS Ensure a Correct Order?

• Nodes are added to the stack only after all their dependencies have been processed, ensuring correct sequencing.
• If a back edge is found during traversal, the graph contains a cycle, making topological sorting impossible.
• The order produced is reverse postorder of the DFS traversal, meaning dependencies are always processed first.

Key Properties of DFS-Based Topological Sorting:

• Recursive Approach: Uses function calls to manage traversal, making it easier to implement but requiring extra stack space.
• Efficient for Dense Graphs: Works well when there are many edges relative to nodes.
• Uses a Stack for Order Storage: Ensures that dependencies are resolved before nodes are processed.
• Cycle Detection is Built-in: If a node is revisited during traversal, the graph has a cycle.

When to Use DFS-Based Topological Sorting?

• When Recursion is Feasible: Works well when the graph is not excessively deep (avoiding stack overflow).
• For Cycle Detection: DFS traversal naturally detects cycles, making it useful when validating DAG structures.
• When Graphs Are Dense: DFS performs well when the number of edges is significantly higher than the number of nodes.

DFS-based topological sorting is widely used in compilers (function inlining), dependency resolution (package managers), and build systems where recursive dependency resolution is required.

Also Read: DFS (Depth First Traversal) in Data Structure: What is, Ordering & Applications

Before implementing DFS-based topological sorting, let’s break it down into clear, actionable steps.

Step-by-Step Algorithm for DFS-Based Topological Sorting

To efficiently determine a valid execution order in a DAG, we use DFS to explore nodes and store them in a stack after all their dependencies are processed. This approach ensures that each node is only added once all prerequisite nodes have been visited, making it ideal for dependency resolution in software builds, task scheduling, and compilation order determination.

Here’s how the DFS-based topological sorting algorithm works step by step:

1. Initialize a visited array to track explored nodes

• Create a boolean array (visited) of size V (number of vertices) to keep track of which nodes have been processed.
• This prevents redundant visits and ensures each node is handled only once.

1. Perform DFS on each unvisited node, recursively exploring its dependencies

• Iterate through all nodes in the graph. If a node hasn’t been visited, start a DFS traversal from it.
• For each node, recursively explore all its adjacent (dependent) nodes before processing the current node itself.
• This ensures dependencies are resolved before the node is added to the final order.

1. Push nodes onto a stack after visiting all their dependencies

• Once a node has no more unvisited dependencies, push it onto a stack.
• This ensures that nodes with no further dependencies appear first in the output order.

1. Pop elements from the stack to obtain the topological order

• Since nodes were added to the stack only after their dependencies, popping from the stack gives the correct topological order.
• The final sequence ensures that every node appears before the nodes that depend on it.

Pseudo-Code for DFS-Based Topological Sorting:

def topological_sort_dfs(graph, V):
    visited = [False] * V
    stack = []
    def dfs(node):
        visited[node] = True
        for neighbor in graph[node]:
            if not visited[neighbor]:
                dfs(neighbor)
        stack.append(node)  # Push after exploring all dependencies
    for v in range(V):
        if not visited[v]:
            dfs(v)
    return stack[::-1]  # Reverse stack for topological order

Time Complexity Analysis:

• O(V + E) – Each node is visited once (O(V)), and all edges are processed once (O(E)).

Advantages of DFS-Based Topological Sorting:

• Efficient for dense graphs with a high edge-to-node ratio.
• Naturally detects cycles, making it useful for validating DAG structures.
• Optimized for recursive dependency resolution, such as function call dependencies in compilers.

Also Read: Why Is Time Complexity Important: Algorithms, Types & Comparison

While DFS provides a recursive approach, Kahn’s Algorithm offers an iterative solution that efficiently manages dependencies using in-degree tracking.

Breadth-First Search (BFS) Approach for Topological Sorting (Kahn’s Algorithm)

Kahn’s Algorithm is a BFS-based method for topological sorting that processes nodes iteratively by tracking their in-degree (number of incoming edges). Instead of relying on recursion, this approach systematically removes nodes with no dependencies, ensuring a valid execution order.

How Kahn’s Algorithm Works?

• Calculate in-degree for all nodes, identifying those with no incoming edges.
• Use a queue to process nodes with zero in-degree first, ensuring dependencies are resolved incrementally.
• Remove processed nodes and update the in-degree of their neighbors.
• Repeat the process until all nodes are ordered or a cycle is detected.

Why Does Kahn’s Algorithm Ensure a Correct Order?

• Nodes with zero in-degree (no incoming dependencies) are always processed first.
• Removing a node updates the in-degree of its neighbors, ensuring dependencies are resolved before nodes are added to the order.
• If all nodes are processed, a valid topological order exists; if not, the graph contains a cycle, making sorting impossible.

When to Use BFS-Based Topological Sorting?

• Best for large, sparse graphs where an iterative approach is more efficient than recursion.
• Useful in scheduling problems, ensuring tasks execute in dependency order.
• Explicitly detects cycles, making it ideal for validating DAGs before processing.

Key Properties of BFS-Based Topological Sorting

• Iterative Approach: Uses a queue instead of recursion, making it memory-efficient.
• Best for Large, Sparse Graphs: Works well when nodes significantly outnumber edges.
• Cycle Detection: If nodes remain unprocessed, a cycle exists in the graph.
• Predictable Execution Order: Ensures tasks execute in the correct dependency sequence, making it ideal for scheduling algorithms and workflow engines.

When to Use BFS-Based Topological Sorting?

• Large-scale scheduling systems (e.g., task execution in Apache Airflow).
• Build dependency management (e.g., resolving dependencies in Gradle, Make, and Bazel).
• Database query optimization, where execution plans rely on dependency resolution.

Step-by-Step Algorithm for BFS-Based Topological Sorting

Kahn’s Algorithm provides an efficient, iterative method for topological sorting by systematically resolving dependencies. Instead of relying on recursion like DFS, it processes nodes level by level, ensuring that tasks execute in the correct order.

Here’s how the BFS-based topological sorting algorithm works step by step:

1. Calculate in-degree for all nodes
   • Count the number of incoming edges for each node.
   • This determines which nodes have no dependencies and can be processed first.
2. Initialize a queue with nodes having zero in-degree
   • Nodes with no incoming edges represent independent tasks that can be executed immediately.
   • Enqueue all such nodes, as they will form the starting point of the sorted order.
3. Process nodes from the queue and add them to the topological order
   • Dequeue a node, process it, and append it to the result list.
   • This ensures that nodes are processed only after their prerequisites are completed.
4. Remove processed nodes and update the in-degree of their neighbors
   • For each outgoing edge from the processed node, decrement the in-degree of the connected nodes.
   • If a neighbor’s in-degree reaches zero, enqueue it, as all its dependencies have been resolved.
5. Repeat until all nodes are processed or a cycle is detected
   • If all nodes are processed, a valid topological order is obtained.
   • If nodes remain unprocessed, it indicates the presence of a cycle, making sorting impossible.

Both DFS and BFS offer efficient topological sorting, but choosing the right approach depends on your graph's structure and application needs.

DFS vs. BFS for Topological Sorting: Choosing the Right Approach for Your DAG

Both DFS and BFS (Kahn’s Algorithm) effectively perform topological sorting, but they operate differently based on graph structure, memory constraints, and execution order requirements. Understanding their differences helps in selecting the best approach for task scheduling, dependency resolution, and workflow management.

Here’s a structured comparison of DFS-based and BFS-based topological sorting:

Both methods ensure valid topological sorting, but DFS is suited for deep dependency trees, while BFS is better for explicit order resolution in real-time systems. 

Also Read: Difference Between DFS and BFS: DFS vs BFS, Similarities, and More

DFS-based topological sorting is widely used for task scheduling and dependency resolution. Let’s implement it in multiple programming languages to understand its practical applications.

DFS-Based Topological Sorting: Step-by-Step Implementation in Multiple Languages

Implementing DFS-based topological sorting in different programming languages is crucial for practical applications in scheduling, dependency management, and compiler design. Since DFS heavily relies on recursion, it is particularly well-suited for recursion-friendly languages like C++ and Java, where it efficiently resolves dependencies.

Why DFS-Based Sorting Is a Preferred Approach

• Recursion-friendly structure simplifies implementation in languages with strong stack management.
• Efficient for dependency resolution, making it ideal for build systems and function call analysis.
• Handles complex DAGs effectively, ensuring dependencies are processed before execution.

Key Aspects of Implementation

• Graph Representation: Uses adjacency lists for efficient traversal.
• Tracking Visits: Maintains a visited set to prevent redundant computations.
• Stack for Order Storage: Ensures nodes are processed in reverse postorder.
• Cycle Detection: Prevents infinite loops by identifying cyclic dependencies early.

Language-Specific Considerations

• C++: Manual memory management requires careful use of data structures like vector and stack.
• Java: Built-in collections (ArrayList, Stack) make implementation easier.
• JavaScript: Lacks built-in stack support, requiring Array manipulations for DFS.
• C#: LINQ optimizations can simplify adjacency list processing.

Now, let’s start with the C++ implementation of DFS-based topological sorting.

C++ Implementation: Optimized DFS-Based Topological Sorting with STL

In C++, DFS-based topological sorting is implemented using adjacency lists and a stack, ensuring an efficient, structured approach to dependency resolution. Standard Template Library (STL) containers like vector, stack, and unordered_map improve performance, making the implementation well-suited for large-scale scheduling, build systems, and compiler optimizations.

Why Use DFS for Topological Sorting in C++?

• Efficient for dependency graphs in build systems (Make, CMake), scheduling (OS process handling), and function call ordering in compilers.
• Recursive approach naturally ensures that each node is processed after its dependencies.
• STL-based implementation provides faster lookups (unordered_map for adjacency list) and efficient traversal (vector for graph representation).

Key Features of the Implementation

• Graph Representation: unordered_map<int, vector<int>> stores edges efficiently.
• Tracking Visits: vector<bool> ensures each node is processed only once.
• Stack for Order Storage: Nodes are stored in postorder for correct sequencing.
• Optimized Lookups: unordered_map reduces edge retrieval time.
• Handles Disconnected Graphs: Ensures all nodes are processed, even if unconnected.

C++ Code Implementation

#include <iostream>
#include <vector>
#include <stack>
#include <unordered_map>
using namespace std;
// DFS function for topological sorting
void dfs(int node, unordered_map<int, vector<int>> &graph, vector<bool> &visited, stack<int> &topoStack) {
    visited[node] = true;  
    // Recursively visit all adjacent nodes
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited, topoStack);
        }
    }
    // Push current node to stack after visiting all dependencies
    topoStack.push(node);
}
// Function to perform topological sorting
vector<int> topologicalSort(int vertices, unordered_map<int, vector<int>> &graph) {
    vector<bool> visited(vertices, false);
    stack<int> topoStack;
    // Perform DFS for all unvisited nodes
    for (int i = 0; i < vertices; i++) {
        if (!visited[i]) {
            dfs(i, graph, visited, topoStack);
        }
    }
    // Retrieve topological order
    vector<int> topoOrder;
    while (!topoStack.empty()) {
        topoOrder.push_back(topoStack.top());
        topoStack.pop();
    }
    return topoOrder;
}
int main() {
    unordered_map<int, vector<int>> graph;
    // Example DAG:  
    // 5 → 2, 5 → 0  
    // 4 → 0, 4 → 1  
    // 2 → 3, 3 → 1  
    graph[5] = {2, 0};
    graph[4] = {0, 1};
    graph[2] = {3};
    graph[3] = {1};
    int vertices = 6; // Number of nodes (0 to 5)
    vector<int> result = topologicalSort(vertices, graph)
    // Output the topological order
    cout << "Topological Sorting Order: ";
    for (int node : result) {
        cout << node << " ";
    }
    cout << endl;
    return 0;
}

Expected Output

Topological Sorting Order: 5 4 2 3 1 0  

Explanation of the Implementation:

1. DFS Traversal:
   • The algorithm starts DFS from each unvisited node.
   • Nodes are recursively visited before being pushed onto the stack, ensuring all dependencies are processed first.
2. Stack-Based Ordering:
   • Nodes are added to the stack only after all dependencies are resolved.
   • The stack is then popped to get the final topological order.
3. Use of unordered_map for Optimization:
   • The adjacency list uses an unordered_map<int, vector<int>>, allowing fast edge lookups.
   • This improves performance compared to using a simple vector array.

Time and Space Complexity Analysis:

• Time Complexity: O(V + E)
  • Each vertex is visited once (O(V)).
  • Each edge is processed once (O(E)).
• Space Complexity: O(V + E)
  • unordered_map stores V nodes and E edges.
  • visited array uses O(V) space.
  • Stack stores O(V) elements.

Advantages of DFS-Based Topological Sorting in C++:

• Fast for dense graphs with many edges.
• Works well with recursion-friendly structures.
• Ideal for compilers, build systems, and task scheduling.

This C++ implementation demonstrates how DFS-based topological sorting efficiently handles dependency resolution.

Java Implementation: DFS-Based Topological Sorting with Efficient Data Structures

In Java, DFS-based topological sorting can be efficiently implemented using ArrayList for adjacency lists and Stack for order storage. Java’s built-in HashMap and HashSet improve lookup efficiency and enable cycle detection, ensuring robustness in handling DAGs. Additionally, we explore an iterative DFS approach using an explicit stack, avoiding Java’s recursion limits for deep graphs.

Why Use DFS for Topological Sorting in Java?

• Efficient recursion handling with Java’s function calls and call stack.
• Built-in collections like ArrayList, HashMap, and Stack simplify implementation.
• Cycle detection using HashSet, ensuring valid DAGs before processing.
• Supports both recursive and iterative DFS, making it adaptable for different scenarios.

Key Features of the Implementation

• Graph Representation: Uses HashMap<Integer, ArrayList<Integer>> for adjacency lists.
• Tracking Visits: HashSet<Integer> prevents redundant computations.
• Stack for Order Storage: Ensures nodes are processed in reverse postorder.
• Cycle Detection: Prevents infinite loops by tracking recursion stack.
• Iterative Alternative: Uses Stack to simulate recursion for deep graphs.

Recursive DFS-Based Topological Sorting in Java: 

import java.util.*;
public class DFSTopologicalSort { 
    // Recursive DFS function
    private static void dfs(int node, Map<Integer, List<Integer>> graph, Set<Integer> visited, Stack<Integer> stack) {
        visited.add(node);
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                dfs(neighbor, graph, visited, stack);
            }
        }
        stack.push(node); // Push node to stack after processing dependencies
    }
    // Function to perform topological sorting
    public static List<Integer> topologicalSort(int vertices, Map<Integer, List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();
        Stack<Integer> stack = new Stack<>(); 
        // Perform DFS for all unvisited nodes
        for (int i = 0; i < vertices; i++) {
            if (!visited.contains(i)) {
                dfs(i, graph, visited, stack);
            }
        }
        // Retrieve topological order
        List<Integer> topoOrder = new ArrayList<>();
        while (!stack.isEmpty()) {
            topoOrder.add(stack.pop());
        }
        return topoOrder;
    }
    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>(); 
        // Example DAG:  
        // 5 → 2, 5 → 0  
        // 4 → 0, 4 → 1  
        // 2 → 3, 3 → 1  
        graph.put(5, Arrays.asList(2, 0));
        graph.put(4, Arrays.asList(0, 1));
        graph.put(2, Arrays.asList(3));
        graph.put(3, Arrays.asList(1));
        int vertices = 6; // Number of nodes (0 to 5)
        List<Integer> result = topologicalSort(vertices, graph);
        System.out.println("Topological Sorting Order: " + result);
    }
}

Expected Output: 

Topological Sorting Order: [5, 4, 2, 3, 1, 0]

Explanation:

1. DFS Traversal:
   • Visits each node and recursively explores all dependencies.
   • Pushes nodes onto a stack after processing all their dependencies.
2. Stack-Based Ordering:
   • Nodes are retrieved in reverse postorder by popping from the stack.
3. Use of HashMap for Graph Representation:
   • Allows fast adjacency list lookups.
4. Cycle Handling:
   • If a cycle exists, an additional cycle detection mechanism can be integrated to prevent infinite recursion.

Iterative DFS-Based Topological Sorting in Java

Recursion depth in Java can be a limitation for large graphs. Instead, an iterative DFS approach using an explicit stack ensures better memory handling.

import java.util.*;
public class IterativeDFSTopologicalSort {
    public static List<Integer> topologicalSort(int vertices, Map<Integer, List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();
        Stack<Integer> stack = new Stack<>();
        Stack<Integer> nodeStack = new Stack<>(); // Explicit stack for DFS traversal
        Map<Integer, Boolean> inStack = new HashMap<>(); // Track nodes in recursion stack
        for (int i = 0; i < vertices; i++) {
            if (!visited.contains(i)) {
                nodeStack.push(i);
                inStack.put(i, true);
                while (!nodeStack.isEmpty()) {
                    int node = nodeStack.peek();
                    if (!visited.contains(node)) {
                        visited.add(node);
                        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
                            if (!visited.contains(neighbor)) {
                                nodeStack.push(neighbor);
                                inStack.put(neighbor, true);
                            }
                        }
                    } else {
                        nodeStack.pop();
                        stack.push(node);
                    }
                }
            }
        }
        List<Integer> topoOrder = new ArrayList<>();
        while (!stack.isEmpty()) {
            topoOrder.add(stack.pop());
        }
        return topoOrder;
    }
    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(5, Arrays.asList(2, 0));
        graph.put(4, Arrays.asList(0, 1));
        graph.put(2, Arrays.asList(3));
        graph.put(3, Arrays.asList(1));
        int vertices = 6;
        List<Integer> result = topologicalSort(vertices, graph);
        System.out.println("Topological Sorting Order: " + result);
    }
}

Expected Output: 

Topological Sorting Order: [5, 4, 2, 3, 1, 0]

Why Use Iterative DFS?

• Avoids recursion depth issues in deep graphs.
•  Explicit stack-based approach mimics recursion without excessive memory usage.
• More suitable for handling very large DAGs in scheduling and dependency management systems.

Time and Space Complexity Analysis

• Time Complexity: O(V + E)
  • Each vertex is visited once (O(V)).
  • Each edge is processed once (O(E)).
• Space Complexity:
  • Recursive Approach: O(V) (for recursion stack in worst case).
  • Iterative Approach: O(V) (for explicit stack, avoiding call stack overflow).

Advantages of DFS-Based Topological Sorting in Java

• Works efficiently with Java collections (ArrayList, HashMap, Stack).
• Supports both recursive and iterative DFS implementations.
• Handles large DAGs with cycle detection and explicit stack management.

This Java implementation demonstrates the power of DFS-based topological sorting for scheduling, dependency resolution, and graph-based computations.

JavaScript Implementation: DFS-Based Topological Sorting with ES6 Features

In JavaScript, DFS-based topological sorting can be implemented using Map for adjacency lists, ensuring efficient lookups and structured graph representation. Unlike languages with built-in stack support, JavaScript handles recursion using the call stack, requiring careful cycle detection to prevent infinite loops. Using ES6 features like Set and Map, we can optimize performance and simplify traversal.

Why Use DFS for Topological Sorting in JavaScript?

• Efficient graph representation with Map, allowing fast key-based lookups.
• Handles recursion without explicit stack management, relying on JavaScript’s call stack.
• Cycle detection with Set ensures DAG validation before sorting.
• ES6 optimizations (Set, Map) improve performance over plain objects and arrays.

Key Features of the Implementation

• Graph Representation: Uses Map to store adjacency lists dynamically.
• Tracking Visits: Set ensures each node is processed only once.
• Stack for Order Storage: Nodes are pushed post-traversal for correct sequencing.
• Cycle Detection: Uses a recursion stack (Set) to detect cycles.
• Optimized with ES6 Features: Map and Set provide efficient lookups and insertions.

Recursive DFS-Based Topological Sorting in JavaScript

class Graph {
    constructor() {
        this.adjList = new Map();
    }
    addEdge(u, v) {
        if (!this.adjList.has(u)) this.adjList.set(u, []);
        this.adjList.get(u).push(v);
    }
    // DFS function for topological sorting
    dfs(node, visited, stack, recStack) {
        if (recStack.has(node)) {
            throw new Error("Cycle detected! Topological sorting is not possible.");
        }
        if (!visited.has(node)) {
            visited.add(node);
            recStack.add(node); // Add to recursion stack for cycle detection
            // Explore all adjacent nodes
            if (this.adjList.has(node)) {
                for (let neighbor of this.adjList.get(node)) {
                    this.dfs(neighbor, visited, stack, recStack);
                }
            }
            recStack.delete(node); // Remove from recursion stack after processing
            stack.push(node); // Push after processing dependencies
        }
    }
    // Function to perform topological sorting
    topologicalSort(vertices) {
        let visited = new Set();
        let recStack = new Set(); // Tracks recursion depth for cycle detection
        let stack = [];
        for (let i = 0; i < vertices; i++) {
            if (!visited.has(i)) {
                this.dfs(i, visited, stack, recStack);
            }
        }
        return stack.reverse(); // Reverse stack for correct topological order
    }
}
// Create graph and add edges
const graph = new Graph();
// Example DAG:  
// 5 → 2, 5 → 0  
// 4 → 0, 4 → 1  
// 2 → 3, 3 → 1  
graph.addEdge(5, 2);
graph.addEdge(5, 0);
graph.addEdge(4, 0);
graph.addEdge(4, 1);
graph.addEdge(2, 3);
graph.addEdge(3, 1);
const vertices = 6; // Nodes: 0 to 5
try {
    console.log("Topological Sorting Order:", graph.topologicalSort(vertices));
} catch (error) {
    console.error(error.message);
}

Expected Output: 

Topological Sorting Order: [5, 4, 2, 3, 1, 0]

Explanation of the Implementation:

1. DFS Traversal:
   • The algorithm starts DFS from each unvisited node.
   • Recursively explores all dependencies before pushing nodes onto the stack.
2. Stack-Based Ordering:
   • Nodes are stored in postorder traversal.
   • The stack is reversed to get the final topological order.
3. Cycle Handling with Recursion Stack (Set)
   • If a node is revisited while in the recursion stack, a cycle exists, and sorting is not possible.
   • Throws an error if a cycle is detected.
4. Use of Map for Graph Representation
   • Provides faster adjacency list lookups than plain objects.

Iterative DFS-Based Topological Sorting in JavaScript

Since JavaScript recursion can lead to stack overflow for deep graphs, an iterative DFS approach using an explicit stack avoids recursion depth issues.

class GraphIterative {
    constructor() {
        this.adjList = new Map();
    }
    addEdge(u, v) {
        if (!this.adjList.has(u)) this.adjList.set(u, []);
        this.adjList.get(u).push(v);
    }
    topologicalSort(vertices) {
        let visited = new Set();
        let stack = [];
        let result = [];
        let tempStack = [];
        for (let i = 0; i < vertices; i++) {
            if (!visited.has(i)) {
                tempStack.push(i);
                while (tempStack.length > 0) {
                    let node = tempStack[tempStack.length - 1];
                    if (!visited.has(node)) {
                        visited.add(node);
                        if (this.adjList.has(node)) {
                            for (let neighbor of this.adjList.get(node)) {
                                if (!visited.has(neighbor)) {
                                    tempStack.push(neighbor);
                                }
                            }
                        }
                    } else {
                        tempStack.pop();
                        stack.push(node);
                    }
                }
            }
        }
        while (stack.length > 0) {
            result.push(stack.pop());
        }
        return result;
    }
}
// Create graph and add edges
const graphIterative = new GraphIterative();
graphIterative.addEdge(5, 2);
graphIterative.addEdge(5, 0);
graphIterative.addEdge(4, 0);
graphIterative.addEdge(4, 1);
graphIterative.addEdge(2, 3);
graphIterative.addEdge(3, 1);
console.log("Topological Sorting Order:", graphIterative.topologicalSort(6));

Expected Output: 

Topological Sorting Order: [5, 4, 2, 3, 1, 0]

Why Use Iterative DFS?

• Avoids recursion depth issues in deep graphs.
• Explicit stack-based approach mimics recursion without excessive memory usage.
• More suitable for handling large DAGs in scheduling and dependency resolution.

Time and Space Complexity Analysis

• Time Complexity: O(V + E)
  • Each vertex is visited once (O(V)).
  • Each edge is processed once (O(E)).
• Space Complexity:
  • Recursive Approach: O(V) (for recursion stack).
  • Iterative Approach: O(V) (for explicit stack, avoiding call stack overflow).

Advantages of DFS-Based Topological Sorting in JavaScript

• Works efficiently with ES6 data structures (Map, Set).
• Supports both recursive and iterative DFS implementations.
• Handles cycle detection and dependency resolution effectively.

This JavaScript implementation of DFS-based topological sorting ensures optimized performance, cycle detection, and ES6 compatibility.

C# Implementation: DFS-Based Topological Sorting with Optimized Data Structures

In C#, DFS-based topological sorting can be efficiently implemented using List and Dictionary for graph representation. The recursive approach uses a stack-based DFS traversal, ensuring that dependencies are processed before a node is added to the final order. 

HashSet is used for cycle detection, and LINQ optimizations improve performance. Additionally, an iterative DFS version avoids recursion depth limitations using an explicit stack.

Why Use DFS for Topological Sorting in C#?

• Dictionary-based adjacency list for fast edge lookups.
• Efficient recursion handling with C#’s function call stack.
• Cycle detection with HashSet prevents infinite loops in cyclic graphs.
• LINQ optimizations simplify filtering and processing.
• Supports both recursive and iterative DFS implementations, making it adaptable for different scenarios.

Key Features of the Implementation

• Graph Representation: Uses Dictionary<int, List<int>> for adjacency lists.
• Tracking Visits: HashSet<int> ensures each node is processed only once.
• Stack for Order Storage: Ensures nodes are processed in reverse postorder.
• Cycle Detection: Uses HashSet to prevent infinite recursion.
• Optimized with LINQ: Enhances efficiency in list and dictionary operations.

Recursive DFS-Based Topological Sorting in C#

using System;
using System.Collections.Generic;
using System.Linq;
class DFSTopologicalSort
{
    // Recursive DFS function
    private static void DFS(int node, Dictionary<int, List<int>> graph, HashSet<int> visited, Stack<int> stack, HashSet<int> recStack)
    {
        if (recStack.Contains(node))
        {
            throw new InvalidOperationException("Cycle detected! Topological sorting is not possible.");
        }
        if (!visited.Contains(node))
        {
            visited.Add(node);
            recStack.Add(node); // Track recursion stack for cycle detection
            foreach (var neighbor in graph.GetValueOrDefault(node, new List<int>()))
            {
                DFS(neighbor, graph, visited, stack, recStack);
            }
            recStack.Remove(node);
            stack.Push(node); // Push node after processing dependencies
        }
    }
    // Function to perform topological sorting
    public static List<int> TopologicalSort(int vertices, Dictionary<int, List<int>> graph)
    {
        HashSet<int> visited = new HashSet<int>();
        HashSet<int> recStack = new HashSet<int>(); // Tracks recursion depth for cycle detection
        Stack<int> stack = new Stack<int>();
        for (int i = 0; i < vertices; i++)
        {
            if (!visited.Contains(i))
            {
                DFS(i, graph, visited, stack, recStack);
            }
        }
        return stack.ToList(); // Convert stack to list in topological order
    }
    public static void Main()
    {
        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>
        {
            {5, new List<int> {2, 0}},
            {4, new List<int> {0, 1}},
            {2, new List<int> {3}},
            {3, new List<int> {1}}
        };
        int vertices = 6; // Number of nodes (0 to 5)
        try
        {
            List<int> result = TopologicalSort(vertices, graph);
            Console.WriteLine("Topological Sorting Order: " + string.Join(", ", result));
        }
        catch (Exception ex)
        {
            Console.WriteLine(ex.Message);
        }
    }
}

Expected Output:

Topological Sorting Order: 5, 4, 2, 3, 1, 0

Explanation of the Implementation:

1. DFS Traversal:
   • The algorithm starts DFS from each unvisited node.
   • Recursively explores all dependencies before pushing nodes onto the stack.
2. Stack-Based Ordering:
   • Nodes are stored in postorder traversal.
   • The stack is converted to a list in reverse order for correct sequencing.
3. Cycle Handling with Recursion Stack (HashSet)
   • If a node is revisited while in the recursion stack, a cycle exists, and sorting is not possible.
   • Throws an exception if a cycle is detected.
4. Use of Dictionary for Graph Representation
   • Provides fast adjacency list lookups.
   • GetValueOrDefault(node, new List<int>()) prevents null reference errors.

Iterative DFS-Based Topological Sorting in C#

To avoid recursion depth issues, an iterative DFS approach using an explicit stack ensures better memory management and execution stability.

using System;
using System.Collections.Generic;
using System.Linq;
class IterativeDFSTopologicalSort
{
    public static List<int> TopologicalSort(int vertices, Dictionary<int, List<int>> graph)
    {
        HashSet<int> visited = new HashSet<int>();
        Stack<int> stack = new Stack<int>();
        Stack<int> tempStack = new Stack<int>();
        for (int i = 0; i < vertices; i++)
        {
            if (!visited.Contains(i))
            {
                tempStack.Push(i);
                while (tempStack.Count > 0)
                {
                    int node = tempStack.Peek();
                    if (!visited.Contains(node))
                    {
                        visited.Add(node);
                        if (graph.ContainsKey(node))
                        {
                            foreach (var neighbor in graph[node])
                            {
                                if (!visited.Contains(neighbor))
                                {
                                    tempStack.Push(neighbor);
                                }
                            }
                        }
                    }
                    else
                    {
                        tempStack.Pop();
                        stack.Push(node);
                    }
                }
            }
        }
        return stack.ToList();
    }
    public static void Main()
    {
        Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>
        {
            {5, new List<int> {2, 0}},
            {4, new List<int> {0, 1}},
            {2, new List<int> {3}},
            {3, new List<int> {1}}
        };
        List<int> result = TopologicalSort(6, graph);
        Console.WriteLine("Topological Sorting Order: " + string.Join(", ", result));
    }
}

Expected Output:

Topological Sorting Order: 5, 4, 2, 3, 1, 0

Why Use Iterative DFS?

• Avoids recursion depth issues in deep graphs.
• Explicit stack-based approach mimics recursion without excessive memory usage.
• More suitable for handling large DAGs in scheduling and dependency resolution.

Time and Space Complexity Analysis:

• Time Complexity: O(V + E)
  • Each vertex is visited once (O(V)).
  • Each edge is processed once (O(E)).
• Space Complexity:
  • Recursive Approach: O(V) (for recursion stack).
  • Iterative Approach: O(V) (for explicit stack, avoiding call stack overflow).

Advantages of DFS-Based Topological Sorting in C#

• Optimized with LINQ for concise graph processing.
• Supports both recursive and iterative DFS implementations.
• Handles cycle detection and dependency resolution efficiently.

This C# implementation of DFS-based topological sorting ensures optimized performance, cycle detection, and efficient memory handling.

Understanding the logic behind DFS-based topological sorting is easier with graphical representation and step-by-step examples.

Illustrating Topological Sorting: Graphical Representation and Examples

Understanding topological sorting in DAGs is easier with visual representation. By breaking down the algorithms for topological sorting in DAGs into step-by-step processes, we can see how dependencies are resolved and the correct execution order is determined. A graph-based approach helps clarify how nodes are explored, stored, and ordered in a DFS-based topological sort.

Graph Representation of the Process

• Nodes represent tasks or events, and edges represent dependencies.
• DFS explores nodes recursively, ensuring each dependency is processed before the node itself.
• Nodes are pushed onto a stack after their dependencies are visited, forming the correct topological order when popped.

Example Walkthrough with a Sample Graph

Consider the following Directed Acyclic Graph (DAG):

• Graph structure:

5 → 2, 5 → 0  
4 → 0, 4 → 1  
2 → 3, 3 → 1  

• Step-by-step execution:

1. Start DFS from an unvisited node (e.g., 5).
2. Recursively visit its dependencies (2 → 3 → 1).
3. Push each node onto the stack after processing dependencies.
4. Retrieve the topological order by popping from the stack.

Now, let’s visualize this process with an illustration showing DFS traversal and stack operations.

The above graph visualization represents the Directed Acyclic Graph (DAG) used for DFS-based topological sorting. The nodes represent tasks, and the directed edges indicate dependencies.

Visualizing topological sorting in DAGs helps in understanding its real-world applications. Let’s discover where it plays a critical role.

Topological Sorting in Action: Key Applications in Computing and Scheduling

Topological sorting is widely used in task scheduling, dependency resolution, and network optimization. By ensuring that each task is completed before its dependents, algorithms for topological sorting in DAGs are essential in various domains.

Key Applications of Topological Sorting:

• Genetic and Bioinformatics Analysis
  • Used in gene regulatory networks to model biological pathways.
  • Helps in sequencing protein interaction studies by ordering genes based on dependencies.
• Automated Manufacturing and Robotics
  • Industrial automation systems use topological sorting to define the order of assembly line operations.
  • Ensures robotic arms follow a dependency-aware sequence to prevent misalignment in manufacturing.
• Cybersecurity and Access Control Systems
  • Used in role-based access control (RBAC) to enforce hierarchical security policies.
  • Ensures users receive appropriate permissions in a dependency-driven manner.
• Database Query Optimization
  • Query planners in databases use topological sorting to order SQL operations efficiently.
  • Ensures JOINs, aggregations, and indexing are executed in the correct dependency sequence.
• Automated Legal and Contract Processing
  • Used in smart contracts and blockchain to validate multi-step contract execution.
  • Ensures that legal dependencies (e.g., loan approvals before fund disbursement) are processed correctly.

Also Read: Explore the Top 30+ DSA projects with source code in 2025

Despite its wide applicability, topological sorting in DAGs comes with challenges that impact its efficiency and feasibility in complex systems.

Key Challenges and Limitations of Applying Topological Sorting

To effectively use topological sorting in DAGs, it is important to understand its limitations and how they impact different applications. The table below highlights key challenges and their implications in real-world scenarios.

While topological sorting in DAGs is essential for ordering dependencies, its effectiveness depends on the problem constraints and graph structure. Let’s weigh its advantages and limitations.

Advantages and Disadvantages of Topological Sorting

Topological sorting provides a structured way to handle task sequencing, dependency resolution, and execution workflows, but it has limitations that restrict its applicability in certain cases.

 The table below outlines when it is most useful and where it falls short.

A strong foundation in graph theory and algorithmic problem-solving is essential for applying topological sorting in DAGs. upGrad’s expert-led courses help you develop these skills for real-world applications.

How Can upGrad Help You Learn Topological Sorting in DAGs?

Professionals across industries rely on graph algorithms like topological sorting to optimize task scheduling, dependency management, and computational workflows. upGrad’s industry-focused programs provide in-depth training in graph theory, algorithmic problem-solving, and large-scale data processing, helping you apply these concepts in real-world scenarios.

With a global network of 10 million+ learners, 200+ courses, and 1,400+ hiring partners, upGrad ensures career growth through hands-on learning and industry collaboration.

Here are some of upGrad’s advanced courses to help you gain industry-ready expertise in algorithmic optimization, data structures, and graph-based computing:

• Master’s Degree in Artificial Intelligence and Data Science
• Masters in Data Science Degree
• Post Graduate Certificate in Data Science & AI (Executive)

upGrad also offers specialized diplomas and certification programs for rapid upskilling in graph analytics, data structures, and AI-driven optimization:

• Executive Diploma in Data Science & AI with IIIT-B
• Professional Certificate Program in AI and Data Science

Wondering how topological sorting and graph algorithms apply to real-world challenges?  Get personalized career counseling to identify the best opportunities for you. Visit upGrad’s offline centers for expert mentorship, hands-on workshops, and networking sessions to connect you with industry leaders!

Unlock the power of data with our popular Data Science courses, designed to make you proficient in analytics, machine learning, and big data!

Explore our Popular Data Science Courses

Elevate your career by learning essential Data Science skills such as statistical modeling, big data processing, predictive analytics, and SQL!

Top Data Science Skills to Learn

Stay informed and inspired with our popular Data Science articles, offering expert insights, trends, and practical tips for aspiring data professionals!

Read our popular Data Science Articles