📐 Topological Sort Fundamentals

🎯 What is Topological Sort?

Topological sort is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every directed edge (u, v), vertex u comes before vertex v in the ordering. It's a way to represent dependencies.

Requirement: Graph must be a DAG (no cycles)
Ordering: All edges go from earlier to later in the order
Applications: Task scheduling, dependency resolution, build systems
Algorithms: Kahn's Algorithm (BFS) and DFS-based

📌 DAG Only📌 Linear Ordering📌 Dependency Resolution

The Core Insight

Key Insight: Topological sort gives us a valid order to process tasks or vertices where all prerequisites are satisfied before a task is processed.

Two Main Algorithms:

Kahn's Algorithm BFS-based, uses in-degree
DFS Algorithm Recursive, uses post-order

# Topological Sort - Problem Statement
# Given: Directed Acyclic Graph (DAG) with V vertices and E edges
# Find: Linear ordering such that for all edges (u, v), u appears before v

# Example:
# Graph: 5 → 0, 5 → 2, 4 → 0, 4 → 1, 2 → 3, 3 → 1
# One valid topological sort: [5, 4, 2, 3, 1, 0]
# Another: [4, 5, 0, 2, 3, 1]
# Invalid: [4, 0, 5, 1, 2, 3] (5 appears after 0, but edge 5→0 exists)

# Real-world analogy:
# University courses with prerequisites:
# Calculus I → Calculus II → Physics I → Physics II
# A valid order to take courses must respect these prerequisites

🔬 Properties & Definitions

🎯 Key Properties of Topological Sort

DAG Only: Only directed acyclic graphs have a topological sort
Non-Unique: Multiple valid topological sorts exist for most DAGs
Vertex Cover: Every vertex appears exactly once in the ordering
Edge Direction: All edges point forward in the ordering
Existence: Every DAG has at least one topological sort

# Understanding DAG Properties
# What makes a graph a DAG?

# Graph 1: Valid DAG
# 1 → 2 → 3
#     ↓
#     4
# No cycles, topological sort exists

# Graph 2: Not a DAG (has cycle)
# 1 → 2 → 3
# ↑       ↓
#  ← ← ← ←
# Cycle: 1→2→3→1, no topological sort

# Graph 3: Multiple topological sorts
#     a
#    / \
#   b   c
#    \ /
#     d
# Valid sorts: [a, b, c, d] and [a, c, b, d]

# Graph 4: Chain (unique topological sort)
# 1 → 2 → 3 → 4 → 5
# Only valid sort: [1, 2, 3, 4, 5]

🔵 Kahn's Algorithm (BFS)

🎯 BFS-Based Topological Sort

Kahn's algorithm uses in-degree counts and a queue to iteratively remove vertices with no incoming edges.

Approach: Start with vertices with in-degree 0
Data Structure: Queue (FIFO)
Time: O(V + E)
Space: O(V)

# Kahn's Algorithm (BFS)
from collections import deque, defaultdict

def kahn_topological_sort(vertices, edges):
    # Build adjacency list and in-degree
    adj = defaultdict(list)
    in_degree = {v: 0 for v in vertices}
    
    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 1
    
    # Initialize queue with vertices with in-degree 0
    queue = deque([v for v in vertices if in_degree[v] == 0])
    result = []
    
    while queue:
        u = queue.popleft()
        result.append(u)
        
        # Reduce in-degree of neighbors
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    # If result length != vertices count, graph has a cycle
    if len(result) != len(vertices):
        return None  # Cycle detected
    
    return result

# Example
vertices = [0, 1, 2, 3, 4, 5]
edges = [(5, 0), (5, 2), (4, 0), (4, 1), (2, 3), (3, 1)]
print(kahn_topological_sort(vertices, edges))
# Output: [5, 4, 2, 3, 1, 0] or [4, 5, 2, 3, 1, 0]

# Step-by-step:
# Initial in-degrees: 0:2, 1:2, 2:1, 3:1, 4:0, 5:0
# Queue: [4, 5]
# Pop 4 → result: [4], decrease in-degree of 0,1
# Pop 5 → result: [4, 5], decrease in-degree of 0,2
# Queue: [2]
# Pop 2 → result: [4, 5, 2], decrease in-degree of 3
# Queue: [3]
# Pop 3 → result: [4, 5, 2, 3], decrease in-degree of 1
# Queue: [1]
# Pop 1 → result: [4, 5, 2, 3, 1], decrease in-degree of 0
# Queue: [0]
# Pop 0 → result: [4, 5, 2, 3, 1, 0]

🟣 DFS-Based Topological Sort

🎯 Recursive Post-Order Traversal

The DFS-based algorithm performs a depth-first search and adds vertices to the result in post-order (after all descendants are visited).

Approach: DFS on each unvisited vertex
Key: Add to result after processing all children
Time: O(V + E)
Space: O(V) (recursion stack)

# DFS-Based Topological Sort
def dfs_topological_sort(vertices, edges):
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
    
    visited = set()
    result = []
    
    def dfs(u):
        visited.add(u)
        for v in adj[u]:
            if v not in visited:
                dfs(v)
        result.append(u)  # Post-order
    
    for v in vertices:
        if v not in visited:
            dfs(v)
    
    # Reverse to get topological order
    return list(reversed(result))

# For cycle detection in DFS
def dfs_topological_sort_with_cycle_detection(vertices, edges):
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
    
    visited = set()  # Fully processed
    visiting = set()  # Currently in recursion stack
    result = []
    has_cycle = False
    
    def dfs(u):
        nonlocal has_cycle
        if u in visiting:  # Back edge found
            has_cycle = True
            return
        if u in visited:
            return
        
        visiting.add(u)
        for v in adj[u]:
            dfs(v)
        visiting.remove(u)
        visited.add(u)
        result.append(u)
    
    for v in vertices:
        if v not in visited:
            dfs(v)
            if has_cycle:
                return None
    
    return list(reversed(result))

# Example
vertices = [0, 1, 2, 3, 4, 5]
edges = [(5, 0), (5, 2), (4, 0), (4, 1), (2, 3), (3, 1)]
print(dfs_topological_sort(vertices, edges))
# Output: [4, 5, 2, 3, 1, 0] (one possible order)

🔄 Cycle Detection in DAG

🎯 Detecting Cycles During Topological Sort

Both algorithms can detect cycles. A cycle indicates the graph is not a DAG and has no valid topological sort.

Kahn's: If result length < vertices, cycle exists
DFS: If back edge found, cycle exists
Applications: Validating dependency graphs

# Cycle Detection with Kahn's Algorithm
def has_cycle_kahn(vertices, edges):
    adj = defaultdict(list)
    in_degree = {v: 0 for v in vertices}
    
    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 1
    
    queue = deque([v for v in vertices if in_degree[v] == 0])
    count = 0
    
    while queue:
        u = queue.popleft()
        count += 1
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    return count != len(vertices)

# Cycle Detection with DFS
def has_cycle_dfs(vertices, edges):
    adj = defaultdict(list)
    for u, v in edges:
        adj[u].append(v)
    
    visited = set()
    visiting = set()
    
    def dfs(u):
        if u in visiting:
            return True
        if u in visited:
            return False
        
        visiting.add(u)
        for v in adj[u]:
            if dfs(v):
                return True
        visiting.remove(u)
        visited.add(u)
        return False
    
    for v in vertices:
        if v not in visited:
            if dfs(v):
                return True
    return False

# Example with cycle
vertices = [0, 1, 2]
edges = [(0, 1), (1, 2), (2, 0)]  # Cycle!
print(has_cycle_kahn(vertices, edges))  # True
print(has_cycle_dfs(vertices, edges))   # True

# Example without cycle
vertices = [0, 1, 2]
edges = [(0, 1), (1, 2)]  # No cycle
print(has_cycle_kahn(vertices, edges))  # False
print(has_cycle_dfs(vertices, edges))   # False

📊 All Topological Sorts

🎯 Generating All Possible Orderings

For a given DAG, there can be multiple valid topological sorts. This section shows how to generate all of them.

Approach: Backtracking with Kahn's algorithm
Time: O(V! ) in worst case (exponential)
Use Case: Finding optimal ordering, exploring possibilities

# Generate All Topological Sorts
def all_topological_sorts(vertices, edges):
    adj = defaultdict(list)
    in_degree = {v: 0 for v in vertices}
    
    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 1
    
    result = []
    
    def backtrack(path, in_deg):
        # Check if all vertices are processed
        if len(path) == len(vertices):
            result.append(path[:])
            return
        
        # Find vertices with in-degree 0
        candidates = [v for v in vertices if in_deg[v] == 0 and v not in path]
        
        for candidate in candidates:
            # Try this vertex
            path.append(candidate)
            
            # Decrease in-degree of neighbors
            for neighbor in adj[candidate]:
                in_deg[neighbor] -= 1
            
            backtrack(path, in_deg)
            
            # Backtrack
            path.pop()
            for neighbor in adj[candidate]:
                in_deg[neighbor] += 1
    
    backtrack([], in_degree)
    return result

# Example
vertices = [0, 1, 2, 3]
edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
sorts = all_topological_sorts(vertices, edges)
print(f"Number of topological sorts: {len(sorts)}")
for sort in sorts:
    print(sort)

# Output might include:
# [0, 1, 2, 3]
# [0, 2, 1, 3]

📝 Lexicographical Order

🎯 Smallest/Largest Lexicographical Topological Sort

Sometimes we need the lexicographically smallest or largest topological sort. This is useful for problems requiring a specific ordering.

Smallest: Use a min-heap (priority queue) instead of regular queue
Largest: Use a max-heap (or min-heap with negatives)
Time: O(V log V + E)

# Lexicographically Smallest Topological Sort
import heapq

def lexicographical_topological_sort(vertices, edges):
    adj = defaultdict(list)
    in_degree = {v: 0 for v in vertices}
    
    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 1
    
    # Min-heap for smallest lexicographical order
    heap = [v for v in vertices if in_degree[v] == 0]
    heapq.heapify(heap)
    result = []
    
    while heap:
        u = heapq.heappop(heap)
        result.append(u)
        
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                heapq.heappush(heap, v)
    
    if len(result) != len(vertices):
        return None  # Cycle detected
    
    return result

# Largest lexicographical order (use max-heap)
def largest_lexicographical_topological_sort(vertices, edges):
    adj = defaultdict(list)
    in_degree = {v: 0 for v in vertices}
    
    for u, v in edges:
        adj[u].append(v)
        in_degree[v] += 1
    
    # Max-heap (using negatives)
    heap = [-v for v in vertices if in_degree[v] == 0]
    heapq.heapify(heap)
    result = []
    
    while heap:
        u = -heapq.heappop(heap)
        result.append(u)
        
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                heapq.heappush(heap, -v)
    
    if len(result) != len(vertices):
        return None
    
    return result

# Example
vertices = [0, 1, 2, 3, 4]
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (4, 0)]
print(lexicographical_topological_sort(vertices, edges))
# Output: [4, 0, 1, 2, 3] (smallest lexicographical)

⏱️ Time & Space Complexities

Algorithm	Time Complexity	Space Complexity	Notes
Kahn's Algorithm	O(V + E)	O(V)	BFS, queue
DFS-Based	O(V + E)	O(V)	Recursive
Kahn's (Cycle Detection)	O(V + E)	O(V)	Same as Kahn's
DFS (Cycle Detection)	O(V + E)	O(V)	With visiting set
All Topological Sorts	O(V! )	O(V²)	Exponential
Lexicographical (Heap)	O((V + E) log V)	O(V)	Priority queue

🌀 Variations & Extensions

Topological Sort with Constraints: Additional ordering constraints
Kahn's with Multiple Queues: For priority-based ordering
Topological Sort in DAG with Weights: Weighted edge ordering
Topological Sort for Disconnected Graphs: Process each component
Topological Sort with Deadlines: Scheduling with time constraints
Random Topological Sort: Random valid ordering

⚖️ Kahn vs DFS Comparison

Feature	Kahn's Algorithm	DFS Algorithm
Approach	BFS / Iterative	DFS / Recursive
Data Structure	Queue	Recursion Stack
Cycle Detection	Count vertices processed	Back edge detection
Memory	O(V)	O(V) (recursion)
Lexicographical Order	Easy (use heap)	More complex
Implementation	Straightforward	Moderate
Streaming	Natural (in-degree based)	Not natural

🌍 Real-World Applications

Build Systems: Make, Maven, Gradle dependency resolution
Course Scheduling: Determining course prerequisites
Task Scheduling: Project management, task dependencies
Compiler Design: Instruction scheduling, code generation
Database Queries: Query optimization, join ordering
Circuit Design: Signal flow analysis
Data Pipelines: ETL workflow ordering
Git Operations: Resolving merge conflicts (dependency resolution)

🧠 Advanced Concepts

Topological Sort for DAG with Negative Weights: Still works (no cycles)
Topological Sort for DAG with Multiple Connected Components: Process separately
Dynamic Topological Sort: Maintain order when edges are added/removed
Parallel Topological Sort: Process independent vertices concurrently
Topological Sort with Lazy Evaluation: On-demand ordering
Level-Based Topological Sort: Group vertices by depth

📝 Interview Patterns & Problems

🎯 Key Interview Questions

Classic: "Implement topological sort for a DAG"
Course Schedule: "Can you finish all courses?"
Course Schedule II: "Return the order to finish courses"
Alien Dictionary: "Find the order of letters in an alien language"
Task Scheduler: "Schedule tasks with dependencies"
Longest Path in DAG: "Find longest path in a DAG"
Minimum Height Trees: "Find roots that minimize tree height"
Eventual Safe Nodes: "Find nodes that lead to terminal nodes"

# Interview Problem: Course Schedule
def can_finish(num_courses, prerequisites):
    # prerequisites: list of [course, prerequisite]
    adj = defaultdict(list)
    in_degree = {i: 0 for i in range(num_courses)}
    
    for course, prereq in prerequisites:
        adj[prereq].append(course)
        in_degree[course] += 1
    
    queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
    count = 0
    
    while queue:
        u = queue.popleft()
        count += 1
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    return count == num_courses

# Interview Problem: Course Schedule II (Return Order)
def find_order(num_courses, prerequisites):
    adj = defaultdict(list)
    in_degree = {i: 0 for i in range(num_courses)}
    
    for course, prereq in prerequisites:
        adj[prereq].append(course)
        in_degree[course] += 1
    
    queue = deque([i for i in range(num_courses) if in_degree[i] == 0])
    result = []
    
    while queue:
        u = queue.popleft()
        result.append(u)
        for v in adj[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)
    
    return result if len(result) == num_courses else []

# Interview Problem: Alien Dictionary
def alien_order(words):
    # Build graph from adjacent word pairs
    # Find character ordering using topological sort
    # This is a classic application of topological sort
    pass

# Interview Problem: Longest Path in DAG
def longest_path_in_dag(vertices, edges, start):
    # Topological sort first, then DP
    topo = dfs_topological_sort(vertices, edges)
    dist = {v: float('-inf') for v in vertices}
    dist[start] = 0
    
    for u in topo:
        if dist[u] != float('-inf'):
            for v, weight in edges:  # edges with weights
                dist[v] = max(dist[v], dist[u] + weight)
    
    return max(dist.values())

📊 Visualization

🎯 Understanding Topological Sort Visually

Visual representation helps understand how topological sort works on different DAG structures.

# DAG Visualization Examples

# Example 1: Simple DAG
#     A
#    / \
#   B   C
#   |   |
#   D   E
#    \ /
#     F
# Topological sorts: [A, B, C, D, E, F] or [A, C, B, E, D, F]

# Example 2: Star DAG
#     A
#    /|\
#   B C D
#    \|/
#     E
# Topological sorts: [A, B, C, D, E] or [A, D, C, B, E] etc.

# Example 3: Chain DAG
# 1 → 2 → 3 → 4 → 5
# Only one topological sort: [1, 2, 3, 4, 5]

# Example 4: DAG with Multiple Roots
#     A   B
#     |   |
#     C   D
#      \ /
#       E
# Topological sorts: [A, B, C, D, E] or [B, A, D, C, E] etc.

# Kahn's Algorithm Visualization:
# Step 1: Find vertices with in-degree 0 (roots)
# Step 2: Add roots to queue
# Step 3: Process queue, remove vertices, update in-degrees
# Step 4: Repeat until all vertices processed