Topological Sort

1. Definition

• Topological Sort arranges nodes in a directed acyclic graph (DAG) such that for every directed edge u → v, node u appears before v in the ordering.
• Key Properties:
  • Multiple valid orderings may exist.
  • Only applicable to directed acyclic graphs (DAGs).
  • Ensures dependencies are resolved in sequence.

Example

• Graph: Nodes: A → B → D → F, A → C → E → F, G → HValid Orderings:
  • A, B, C, D, E, F, G, H
  • A, C, B, D, E, G, H, F

2. Requirements for Topological Sort

1. Directed Edges: All edges must have a direction.
2. Acyclic Graph: No cycles allowed (cycles make topological ordering impossible).
3. Not Necessarily Connected: The graph can have multiple disconnected components.

Why Cycles Break Topological Sort

• In a cyclic graph (e.g., A → C → E → A), dependencies create contradictions (e.g., A must come before C, but C must come before E, and E must come before A).

3. Algorithm: DFS Approach

Steps

1. Post-Order DFS Traversal:
   • Traverse the graph using DFS.
   • Add nodes to the result list after visiting all their descendants (post-order).
2. Reverse the Result: The final topological order is the reverse of the post-order DFS result.

Pseudocode

def topological_sort(n, edges):
    # Build adjacency list
    adj = {i: [] for i in range(n)}
    for u, v in edges:
        adj[u].append(v)

    visited = set()
    result = []

    def dfs(node):
        if node in visited:
            return
        visited.add(node)
        for neighbor in adj[node]:
            dfs(neighbor)
        result.append(node)  # Post-order addition

    for node in range(n):
        if node not in visited:
            dfs(node)

    return result[::-1]  # Reverse to get topological order