All Notes
Code
Code – Graph Theory
Graph Theory – Theory
Understanding Topological Sort A Practical Guide for Developers

Topological sort. Sounds fancy, right? Like something out of a high-level math course. But for developers, it’s an incredibly practical and powerful algorithm. If you’ve ever dealt with dependencies – whether it’s compiling code, installing packages, or scheduling tasks – you’ve implicitly touched upon the core problem topological sort solves.

This post will demystify topological sort. We’ll explore what it is, why it’s essential, and how to implement it with clear, runnable code examples.

What is Topological Sort?

At its core, a topological sort (or topological ordering) of a directed acyclic graph (DAG) is a linear ordering of its vertices such that for every directed edge u -> v, vertex u comes before vertex v in the ordering.

Key takeaway: It’s all about ordering things that have dependencies.

The Critical Constraint: Directed Acyclic Graph (DAG)

You might have noticed me emphasizing “directed acyclic graph” (DAG). This is not just a fancy term; it’s a fundamental requirement.

  • Directed: The edges have a specific direction (e.g., A must happen before B, not just A and B are related).
  • Acyclic: There are no cycles. This means you can’t have A depends on B, B depends on C, and C depends on A. If a cycle exists, a topological sort is impossible, because you’d have a circular dependency where nothing can truly come first. Think of it like a deadlock in a software system.

Analogy: Imagine a list of courses you need to take for your degree. Some courses have prerequisites. “Calculus I” must be taken before “Calculus II.” “Calculus II” before “Differential Equations.” This forms a directed relationship. If “Differential Equations” also required “Calculus I” (which it implicitly does via “Calculus II”), but somehow “Calculus I” also required “Differential Equations” (a nonsensical scenario), that would be a cycle, and you’d never be able to start!

Why is Topological Sort Useful?

The applications are everywhere in software development:

  • Build Systems: Make, Maven, Gradle, Bazel, Cargo – all determine the order in which to compile source files or modules based on their dependencies. If module A depends on module B, B must be compiled before A.
  • Package Managers: npm, pip, apt, yum – when you install a package, its dependencies must be installed first. Topological sort helps figure out the correct installation order.
  • Task Scheduling: In project management or workflow automation, if Task B depends on Task A completing, Task A must be scheduled before Task B.
  • Course Scheduling: As mentioned, determining a valid sequence of courses to take given prerequisites.
  • Data Serialization: Ordering objects with dependencies for serialization or processing.
  • Pipeline Execution: Ordering stages in a data processing pipeline.

Representing a Graph for Topological Sort

Before we dive into algorithms, let’s establish how we’ll represent our DAGs. An adjacency list is generally a good choice. It’s a dictionary (or hash map) where keys are nodes and values are lists of nodes they point to.

Let’s use a simple course prerequisite example:

  • CS101 (Intro to CS)
  • CS201 (Data Structures) requires CS101
  • CS205 (Algorithms) requires CS201
  • MA101 (Calculus I)
  • MA201 (Calculus II) requires MA101
  • CS301 (Operating Systems) requires CS201 and MA201

This can be represented as:

graph = {
    "CS101": ["CS201"],
    "CS201": ["CS205", "CS301"],
    "CS205": [],
    "MA101": ["MA201"],
    "MA201": ["CS301"],
    "CS301": [],
}

Notice that nodes with no outgoing dependencies (like CS205, CS301) still exist as keys, but their value is an empty list. Nodes with no incoming dependencies (like CS101, MA101) are perfectly valid starting points.

Algorithm 1: Kahn’s Algorithm (BFS-based)

Kahn’s algorithm is an iterative approach that uses the concept of in-degree. The in-degree of a vertex is the number of incoming edges it has.

Intuition: Start with nodes that have no prerequisites (in-degree of 0). Once you “take” these courses, they no longer count as prerequisites for others. So, you decrement the in-degree of the courses that depended on them. If any of those courses now have an in-degree of 0, they become the next set of courses you can take. Repeat until all courses are taken.

Steps:

  1. Calculate In-Degrees: For every node in the graph, compute its in-degree.
  2. Initialize Queue: Add all nodes with an in-degree of 0 to a queue. These are your starting points.
  3. Process Queue:
    • While the queue is not empty:
      • Dequeue a node u. Add u to your topological sort result list.
      • For each neighbor v of u (i.e., u -> v):
        • Decrement the in-degree of v.
        • If v’s in-degree becomes 0, enqueue v.
  4. Cycle Detection: If the number of nodes in the topological sort result list is less than the total number of nodes in the graph, it means there was a cycle.

Example Walkthrough (Kahn’s)

Let’s use our course graph:

graph = {
    "CS101": ["CS201"],
    "CS201": ["CS205", "CS301"],
    "CS205": [],
    "MA101": ["MA201"],
    "MA201": ["CS301"],
    "CS301": [],
}

  1. Calculate In-Degrees:

    • CS101: 0
    • CS201: 1 (CS101)
    • CS205: 1 (CS201)
    • MA101: 0
    • MA201: 1 (MA101)
    • CS301: 2 (CS201, MA201)

  2. Initialize Queue: Nodes with in-degree 0: ["CS101", "MA101"] (order doesn’t strictly matter here, as long as they are processed). topological_order = []

  3. Process Queue:

    • Dequeue CS101:

      • topological_order = ["CS101"]
      • Neighbor of CS101 is CS201. Decrement CS201’s in-degree from 1 to 0.
      • CS201’s in-degree is now 0. Enqueue CS201.
      • Queue: ["MA101", "CS201"]

    • Dequeue MA101:

      • topological_order = ["CS101", "MA101"]
      • Neighbor of MA101 is MA201. Decrement MA201’s in-degree from 1 to 0.
      • MA201’s in-degree is now 0. Enqueue MA201.
      • Queue: ["CS201", "MA201"]

    • Dequeue CS201:

      • topological_order = ["CS101", "MA101", "CS201"]
      • Neighbors of CS201 are CS205, CS301.
      • Decrement CS205’s in-degree from 1 to 0. Enqueue CS205.
      • Decrement CS301’s in-degree from 2 to 1. (Still not 0)
      • Queue: ["MA201", "CS205"]

    • Dequeue MA201:

      • topological_order = ["CS101", "MA101", "CS201", "MA201"]
      • Neighbor of MA201 is CS301.
      • Decrement CS301’s in-degree from 1 to 0. Enqueue CS301.
      • Queue: ["CS205", "CS301"]

    • Dequeue CS205:

      • topological_order = ["CS101", "MA101", "CS201", "MA201", "CS205"]
      • CS205 has no outgoing neighbors.
      • Queue: ["CS301"]

    • Dequeue CS301:

      • topological_order = ["CS101", "MA101", "CS201", "MA201", "CS205", "CS301"]
      • CS301 has no outgoing neighbors.
      • Queue: [] (empty)

  4. Result: ["CS101", "MA101", "CS201", "MA201", "CS205", "CS301"]. All 6 nodes are in the result. No cycle detected.

Kahn’s Algorithm Implementation (Python) 

from collections import defaultdict, deque

def kahn_topological_sort(graph):
    """
    Performs topological sort using Kahn's algorithm (BFS-based).
    Args:
        graph (dict): An adjacency list representation of the graph.
                      e.g., {"A": ["B", "C"], "B": ["D"], ...}
    Returns:
        list: A list of nodes in topological order, or an empty list if a cycle is detected.
    """
    # 1. Calculate in-degrees for all nodes
    in_degrees = defaultdict(int)
    for node in graph:
        # Ensure all nodes are present in in_degrees, even if they have no incoming edges
        in_degrees[node] = in_degrees[node] 
        for neighbor in graph[node]:
            in_degrees[neighbor] += 1
    
    # 2. Initialize queue with nodes having in-degree 0
    queue = deque([node for node, degree in in_degrees.items() if degree == 0])
    
    topological_order = []
    
    # 3. Process the queue
    while queue:
        u = queue.popleft()
        topological_order.append(u)
        
        # For each neighbor v of u
        for v in graph[u]:
            in_degrees[v] -= 1
            # If v's in-degree becomes 0, add it to the queue
            if in_degrees[v] == 0:
                queue.append(v)
                
    # 4. Check for cycles
    # If the number of visited nodes is less than the total number of nodes,
    # it means there was a cycle.
    if len(topological_order) == len(in_degrees): # in_degrees has all unique nodes
        return topological_order
    else:
        print("Error: Graph contains a cycle, topological sort not possible.")
        return []

# Our example graph
course_graph = {
    "CS101": ["CS201"],
    "CS201": ["CS205", "CS301"],
    "CS205": [],
    "MA101": ["MA201"],
    "MA201": ["CS301"],
    "CS301": [],
}

# Example with a cycle (should return empty list and print error)
cycle_graph = {
    "A": ["B"],
    "B": ["C"],
    "C": ["A"]
}

# Example with multiple valid sorts (order depends on queue processing)
complex_graph = {
    "A": ["C"],
    "B": ["C", "D"],
    "C": ["E"],
    "D": ["E"],
    "E": []
}

print("--- Kahn's Algorithm ---")
print("Course Scheduling Example:")
sorted_courses = kahn_topological_sort(course_graph)
print(f"Topological Order: {sorted_courses}")

print("\nCycle Detection Example:")
sorted_cycle = kahn_topological_sort(cycle_graph)
print(f"Topological Order: {sorted_cycle}")

print("\nComplex Graph Example:")
sorted_complex = kahn_topological_sort(complex_graph)
print(f"Topological Order: {sorted_complex}")
--- Kahn's Algorithm ---
Course Scheduling Example:
Topological Order: ['CS101', 'MA101', 'CS201', 'MA201', 'CS205', 'CS301']

Cycle Detection Example:
Error: Graph contains a cycle, topological sort not possible.
Topological Order: []

Complex Graph Example:
Topological Order: ['A', 'B', 'C', 'D', 'E']

Note: The specific output order for the complex_graph might vary slightly (['B', 'A', 'D', 'C', 'E'] for example) depending on the initial order nodes are added to the queue when their in-degree becomes zero. All such variations are valid topological sorts.

Algorithm 2: DFS-based Topological Sort

The Depth-First Search (DFS) based approach builds the topological sort by exploring as far as possible down each path before backtracking. The key insight is that a node can only be added to the sorted list after all of its dependent nodes have been visited.

Intuition: When you finish exploring all paths from a node u (meaning all its descendants have been visited and added to the result list), then u can be added. If you add u to the front of your result list, it ensures that u always comes before its dependents.

Steps:

  1. Maintain State: Use a visited set to keep track of nodes already added to the topological sort. You also need a recursion_stack (or visiting set) to detect cycles.
  2. Iterate Nodes: For each node in the graph:
    • If the node has not been visited:
      • Perform a DFS starting from this node.
  3. DFS Function: dfs(node):
    • Mark node as visiting (add to recursion_stack).
    • For each neighbor v of node:
      • If v is visiting (in recursion_stack), a cycle is detected. Abort.
      • If v has not been visited:
        • Recursively call dfs(v). If a cycle was detected in the recursive call, propagate the error.
    • Mark node as visited (remove from recursion_stack).
    • Add to Result: Add node to the front of your topological sort list (or prepend it).

Example Walkthrough (DFS-based)

Using the same course_graph:

graph = {
    "CS101": ["CS201"],
    "CS201": ["CS205", "CS301"],
    "CS205": [],
    "MA101": ["MA201"],
    "MA201": ["CS301"],
    "CS301": [],
}

topological_order = [] (we’ll prepend) visited = set() recursion_stack = set()

Let’s assume we iterate nodes alphabetically: CS101, CS201, CS205, CS301, MA101, MA201.

  1. dfs("CS101"):

    • Add CS101 to recursion_stack.
    • Neighbor: CS201. Call dfs("CS201").
      • dfs("CS201"):
        • Add CS201 to recursion_stack.
        • Neighbors: CS205, CS301.
        • Call dfs("CS205").
          • dfs("CS205"):
            • Add CS205 to recursion_stack.
            • No neighbors.
            • Remove CS205 from recursion_stack. Add CS205 to topological_order (front). topological_order = ["CS205"].
            • Return.
        • Call dfs("CS301"). (Note: CS301 also depends on MA201, but DFS explores one path fully).
          • dfs("CS301"):
            • Add CS301 to recursion_stack.
            • No neighbors.
            • Remove CS301 from recursion_stack. Add CS301 to topological_order (front). topological_order = ["CS301", "CS205"].
            • Return.
        • Remove CS201 from recursion_stack. Add CS201 to topological_order (front). topological_order = ["CS201", "CS301", "CS205"].
        • Return.
    • Remove CS101 from recursion_stack. Add CS101 to topological_order (front). topological_order = ["CS101", "CS201", "CS301", "CS205"].
    • Return.

  2. Next unvisited: MA101. Call dfs("MA101").

    • dfs("MA101"):
      • Add MA101 to recursion_stack.
      • Neighbor: MA201. Call dfs("MA201").
        • dfs("MA201"):
          • Add MA201 to recursion_stack.
          • Neighbor: CS301. CS301 is already visited. Do nothing.
          • Remove MA201 from recursion_stack. Add MA201 to topological_order (front). topological_order = ["MA201", "CS101", "CS201", "CS301", "CS205"].
          • Return.
      • Remove MA101 from recursion_stack. Add MA101 to topological_order (front). topological_order = ["MA101", "MA201", "CS101", "CS201", "CS301", "CS205"].
      • Return.

All nodes are now visited.

Result: ["MA101", "MA201", "CS101", "CS201", "CS301", "CS205"] (or similar, depending on initial iteration order and recursive path choices). This is also a valid topological sort.

DFS-based Algorithm Implementation (Python) 

from collections import defaultdict

def dfs_topological_sort(graph):
    """
    Performs topological sort using a DFS-based algorithm.
    Args:
        graph (dict): An adjacency list representation of the graph.
                      e.g., {"A": ["B", "C"], "B": ["D"], ...}
    Returns:
        list: A list of nodes in topological order, or an empty list if a cycle is detected.
    """
    visited = set()         # Nodes fully processed and added to sort
    recursion_stack = set() # Nodes currently in the recursion stack (being visited)
    topological_order = []  # Stores the sorted nodes
    
    # Flag to detect cycles globally
    has_cycle = [False] # Using a list to allow modification in nested function scope

    # Collect all unique nodes in the graph to ensure disconnected components are also processed
    all_nodes = set(graph.keys())
    for node_list in graph.values():
        all_nodes.update(node_list)

    def dfs(node):
        if has_cycle[0]: # Early exit if cycle already detected
            return

        visited.add(node)
        recursion_stack.add(node)

        for neighbor in graph.get(node, []): # Use .get() for nodes with no outgoing edges
            if neighbor in recursion_stack:
                # Cycle detected: neighbor is already in the current recursion path
                has_cycle[0] = True
                return
            if neighbor not in visited:
                dfs(neighbor)
                if has_cycle[0]: # Propagate cycle detection up the recursion
                    return
        
        recursion_stack.remove(node)
        topological_order.insert(0, node) # Add to the front (prepending)

    for node in all_nodes:
        if node not in visited:
            dfs(node)
            if has_cycle[0]:
                print("Error: Graph contains a cycle, topological sort not possible.")
                return []
    
    return topological_order

# Our example graph
course_graph = {
    "CS101": ["CS201"],
    "CS201": ["CS205", "CS301"],
    "CS205": [],
    "MA101": ["MA201"],
    "MA201": ["CS301"],
    "CS301": [],
}

# Example with a cycle (should return empty list and print error)
cycle_graph = {
    "A": ["B"],
    "B": ["C"],
    "C": ["A"]
}

# Example with multiple valid sorts
complex_graph = {
    "A": ["C"],
    "B": ["C", "D"],
    "C": ["E"],
    "D": ["E"],
    "E": []
}

print("\n--- DFS-based Algorithm ---")
print("Course Scheduling Example:")
sorted_courses_dfs = dfs_topological_sort(course_graph)
print(f"Topological Order: {sorted_courses_dfs}")

print("\nCycle Detection Example:")
sorted_cycle_dfs = dfs_topological_sort(cycle_graph)
print(f"Topological Order: {sorted_cycle_dfs}")

print("\nComplex Graph Example:")
sorted_complex_dfs = dfs_topological_sort(complex_graph)
print(f"Topological Order: {sorted_complex_dfs}")
--- DFS-based Algorithm ---
Course Scheduling Example:
Topological Order: ['MA101', 'MA201', 'CS101', 'CS201', 'CS301', 'CS205']

Cycle Detection Example:
Error: Graph contains a cycle, topological sort not possible.
Topological Order: []

Complex Graph Example:
Topological Order: ['B', 'D', 'A', 'C', 'E']

Note: Similar to Kahn’s, the DFS-based topological sort can yield different valid orderings depending on the order in which the for node in all_nodes loop processes the initial unvisited nodes and the order of neighbors in the adjacency list.

Choosing an Algorithm: Kahn’s vs. DFS

Both algorithms have the same time complexity: O(V + E), where V is the number of vertices (nodes) and E is the number of edges. This is because both visit each node and each edge once. Space complexity is also O(V + E) to store the graph and auxiliary data structures (in-degrees, queues, recursion stacks).

  • Kahn’s Algorithm (BFS-based):
    • Pros: Generally easier to understand and implement for many. Naturally handles disconnected graphs. Cycle detection is straightforward (check if len(topological_order) equals len(all_nodes)).
    • Cons: Requires computing in-degrees upfront, which adds an extra pass over the graph.
  • DFS-based Algorithm:
    • Pros: Often more concise to implement recursively. Can be slightly more intuitive if you’re comfortable with DFS.
    • Cons: Cycle detection requires careful tracking of nodes in the current recursion path (the recursion_stack). Can lead to deep recursion for long paths (though Python’s recursion limit often handles this, it’s a theoretical consideration).

General advice: For most practical applications, either works well. Kahn’s might be marginally preferred for its clear cycle detection and iterative nature, which can be less prone to stack overflow issues on extremely deep graphs in languages without tail-call optimization.

Edge Cases and Important Considerations

  1. Graphs with Cycles: This is crucial: Topological sort is only possible on a Directed Acyclic Graph (DAG). If your graph contains a cycle, no valid topological ordering exists. Both algorithms presented include mechanisms to detect cycles. If a cycle is detected, the algorithm should ideally report it and stop.
  2. Multiple Valid Sorts: For a given DAG, there might be multiple valid topological orderings. Both Kahn’s and DFS-based algorithms can produce different valid orders depending on implementation details (e.g., the order nodes are added to the queue in Kahn’s, or the order of exploring neighbors in DFS). This is perfectly fine, as long as the fundamental “u before v” rule is maintained for all u -> v edges.
  3. Disconnected Graphs: Both algorithms handle disconnected graphs correctly. They will simply process each connected component in turn (Kahn’s will add all initial zero-in-degree nodes from all components; DFS will iterate through all nodes, initiating a DFS from any unvisited node, effectively traversing all components).
  4. Self-Loops: A node A pointing to itself (A -> A) is a cycle. A topological sort is not possible.
  5. Parallel Edges: Multiple edges between the same two nodes (A -> B and another A -> B) don’t affect topological sort logic, as they don’t change the in-degree or the dependency.

Conclusion

Topological sort is not just an academic curiosity; it’s a workhorse algorithm that underpins many essential software systems. From managing complex build processes to orchestrating task workflows, understanding and being able to implement a topological sort is a valuable skill for any developer.

We’ve covered two primary approaches: Kahn’s algorithm (BFS-based) and the DFS-based method. Both offer O(V + E) efficiency and can detect cycles. Choose the one that feels most intuitive to you or best fits the specific constraints of your project.

Practice these implementations, experiment with different graphs, and you’ll soon find yourself identifying and solving real-world dependency problems with confidence!

Demystifying String Matching - Algorithms and Practical Use Cases
Jun 18, 2025
How the Nyquist Limit Defines Your Webcam and Microphone
Jun 17, 2025
Sudoku Solver with Backtracking in Python
Jun 18, 2025
Disjoint Set Union (DSU) A Practical Guide for Developers
Jun 18, 2025
How Devs Can Embrace AI Without Losing the Craft
Jun 17, 2025
My Actual Alias File Explained and Rated
Jun 17, 2025
Last updated on
Share this post: Twitter Facebook LinkedIn
Understanding Breadth-First Search (BFS) for Developers