Topological Sorting

# CHAPTER 26

Topological Sorting #

1. Introduction #

2. Learning Objectives #

• Define the absolute constraints of a Directed Acyclic Graph (DAG).

• Understand the concept of In-Degree dependencies.

• Execute the DFS-based Topological Sort algorithm using a Stack.

• Execute Kahn’s Algorithm (BFS-based Topological Sort).

3. The DAG Constraint (Directed Acyclic Graph) #

1. 1. Directed: The edges must have arrows ($A \rightarrow B$). If there are no arrows, there is no "Before" and "After".

1. 2. Acyclic: The graph must have ZERO Cycles (Loops).

• *Logic Check:* If Class A requires Class B, and Class B requires Class A... the student is trapped in a paradox and can never graduate. If a cycle exists, Topological Sorting is structurally impossible.

4. Algorithm 1: The DFS Stack Method #

The Strategy: We run a standard DFS (Chapter 22). When a Node hits an absolute dead end (meaning it has zero dependencies pointing outward, or all its downstream children have been fully mapped), we push it onto a global LIFO Stack.

Execution Trace: Graph: A -> C, B -> C, C -> D

1. 1. Start at A. Go to C. Go to D.

1. 2. D has no outward arrows. It is a dead end. Push D to Stack. Stack: [D].

1. 3. Backtrack to C. C's children are done. Push C. Stack: [D, C].

1. 4. Backtrack to A. A's children are done. Push A. Stack: [D, C, A].

1. 5. Start at unvisited B. Go to C (already visited). B's children done. Push B.

1. 6. Final Stack (Top to Bottom): [B, A, C, D].

5. Algorithm 2: Kahn’s Algorithm (In-Degree BFS) #

The Concept of In-Degree: The In-Degree is the number of arrows pointing *at* a node.

• If a node has an In-Degree of 0, it requires absolutely nothing! It is ready to execute immediately.

The Strategy:

1. 1. Calculate the In-Degree for every single node in the graph.

1. 2. Find all nodes with an In-Degree of 0 and throw them into a Queue.

1. 3. While the Queue is not empty:

• Dequeue Node X. Add it to the final sorted output array.

• Look at all neighbors Node X points to.

• Mathematically subtract 1 from the neighbor's In-Degree! (Because Node X just executed, that dependency is satisfied!).

• If a neighbor's In-Degree hits 0, instantly enqueue it!

1. 4. *Cycle Check:* If the final output array doesn't contain all $V$ nodes, the graph has a fatal Cycle!

6. Code Execution (Kahn's Algorithm in Python) #

from collections import deque

def topological_sort(vertices, edges):
    in_degree = {v: 0 for v in vertices}
    graph = {v: [] for v in vertices}
    
    # Build Graph and calculate In-Degrees
    for src, dest in edges:
        graph[src].append(dest)
        in_degree[dest] += 1
        
    # Find all nodes with 0 dependencies
    queue = deque([v for v in vertices if in_degree[v] == 0])
    sorted_order = []
    
    while queue:
        current = queue.popleft()
        sorted_order.append(current) # Execute the task!
        
        # Resolve dependencies for neighbors
        for neighbor in graph[current]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor) # Neighbor is ready to execute!
                
    if len(sorted_order) != len(vertices):
        return "FATAL ERROR: Cycle Detected in Dependencies!"
        
    return sorted_order

# Graph: A->C, B->C, C->D
vertices = ['A', 'B', 'C', 'D']
edges = [('A', 'C'), ('B', 'C'), ('C', 'D')]
print(topological_sort(vertices, edges)) # Output: ['A', 'B', 'C', 'D']

7. Applications of Topological Sorting #

• Compiler Builds: Determining which C++ files to compile first based on #include headers.

• Task Scheduling: Project management software (Gantt Charts) allocating tasks chronologically.

• Data Serialization: Saving heavily relational object structures to a flat database.

8. Complexity Analysis #

• Time Complexity: $O(V + E)$. The engine evaluates every discrete node and slices through every dependency line exactly once.

• Space Complexity: $O(V)$. Storing the In-Degree array, the Queue, and the final output array scales linearly with the Vertices.

9. Common Mistakes #

• Assuming a Unique Output: A Topological Sort rarely has one "correct" answer. If Task A and Task B both have 0 dependencies, they can be executed in any order (A, B or B, A). The output sequence is valid as long as no strict < dependency rules are broken.

10. Exercises #

1. 1. Draw a DAG where A->B, A->C, B->D, C->D. Trace Kahn's Algorithm. What is the initial In-Degree of node D? At what step does it drop to 0?

1. 2. Theoretically explain how Kahn's Algorithm acts as an accidental Cycle Detector. Why does a cycle prevent the output array from reaching length $V$?

11. MCQs with Answers #

12. Interview Preparation #

• *Algorithmic Course Mapping:* "LeetCode Problem 207: 'Course Schedule'. You are given a list of university courses and an array of prerequisite pairs [coursea, courseb]. Write an algorithm to determine if it is mathematically possible to finish all courses." *(Answer: The classic Topological Sort! Calculate the In-Degrees of all courses. Run Kahn's Algorithm. If the length of the sorted output array equals the total number of courses, return True. If it's shorter, a cycle trapped the algorithm. Return False!)*

13. Summary #