Topological Sort

What is Topological Sort?

Topological Sort is a linear ordering algorithm for vertices in a Directed Acyclic Graph (DAG) such that for every directed edge (u, v), vertex u comes before v in the ordering. It's impossible to perform topological sort on graphs with cycles, making it useful for cycle detection as well. Note: Edge weights are ignored by Topological Sort - it only considers the direction of edges, not their weights.

Two Main Approaches

There are two main algorithms for topological sort:

• Kahn's Algorithm (Queue-based): Processes nodes with no incoming edges (in-degree 0) first, then updates in-degrees of neighbors. More intuitive for understanding dependencies and better for parallel processing.
• DFS-based: Uses Depth-First Search to explore the graph deeply, then adds nodes to the order when backtracking. More visually engaging and better demonstrates the exploration pattern.

This visualization uses the DFS-based approach because it's more visually engaging. You can see the algorithm go deep into the graph and backtrack, making the exploration pattern clear and intuitive to follow.

How It Works (DFS-Based)

The DFS-based implementation works as follows:

1. Start DFS from an unvisited node
2. Go deep: recursively visit all unvisited neighbors first
3. When backtracking (all neighbors processed), add the node to the topological order
4. If a back edge is detected (visiting a node already in the DFS path), a cycle exists
5. Repeat from step 1 for any remaining unvisited nodes
6. Reverse the order to get the final topological sort

Implementation

Here's a Python implementation using DFS:

from typing import Dict, List, Optional

def topological_sort_dfs(graph: Dict[str, List[str]]) -> Optional[List[str]]:
    """
    Perform topological sort on a directed acyclic graph (DAG) using DFS.
    
    Returns a linear ordering of vertices such that for every directed edge (u, v),
    vertex u comes before v in the ordering. If the graph contains cycles, returns None.
    
    Uses DFS-based approach: explores deeply, then adds nodes to the order when
    backtracking (after all neighbors are processed).
    
    Args:
        graph: Adjacency list representation of a directed graph.
    
    Returns:
        List of nodes in topological order, or None if a cycle is detected.
    
    Time Complexity: O(V + E) where V is vertices and E is edges.
    Space Complexity: O(V) for recursion stack and sets.
    """
    visited: set[str] = set()
    finished: set[str] = set()
    result: List[str] = []
    
    def dfs(node: str) -> bool:
        """Inner DFS function that detects cycles and builds topological order."""
        if node in finished:
            return True  # Already processed
        if node in visited:
            return False  # Back edge detected (cycle)
        
        visited.add(node)
        
        # Go deep: visit all neighbors first
        for neighbor in graph.get(node, []):
            if not dfs(neighbor):
                return False  # Cycle detected
        
        # Backtrack: add to order when all neighbors processed
        finished.add(node)
        result.append(node)
        return True
    
    # Start DFS from all unvisited nodes
    for node in graph:
        if node not in finished:
            if not dfs(node):
                return None  # Cycle detected
    
    # Reverse to get topological order
    result.reverse()
    return result

# Example
graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
print(topological_sort_dfs(graph))
# ['A', 'B', 'C', 'D'] or ['A', 'C', 'B', 'D'] (multiple valid orders)

Time Complexity

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges. Each vertex and edge is processed exactly once, making it very efficient.

Edge Cases: If the graph contains cycles, the algorithm will detect them and indicate that not all nodes can be ordered. If the graph has disconnected components, the algorithm will process each component separately.

Real-World Applications

• Build systems: determining the order to compile source files with dependencies
• Task scheduling: scheduling tasks with prerequisites
• Course prerequisites: determining the order to take courses
• Package managers: resolving dependency installation order
• Event-driven systems: determining the order of event processing
• Cycle detection: detecting cycles in directed graphs