Topological Sort

What you'll learn

• The Golden Rule

  Use topological sort when you need to: - Determine an ordering with dependencies (prerequisites, build order) - Schedule tasks where some must complete before others - Detect if a valid ordering exists (cycle detection in directed graphs…

• What Is Topological Ordering?

  A linear ordering of vertices such that for every directed edge u -> v, vertex u appears before v in the ordering. A graph can have multiple valid topological orderings. ---

• Approach 1: Kahn's Algorithm (BFS-based)

• Concept

  1. Compute in-degree for every node (number of incoming edges) 2. Start with all nodes that have in-degree 0 (no prerequisites) 3. Process each such node: for every neighbor, decrement its in-degree 4. When a neighbor's in-degree reaches…

• ASCII Walkthrough

• Implementation

  ---

• Approach 2: DFS-based Topological Sort

• Concept

  Use post-order DFS: push a node onto the result stack only after all its descendants have been processed.

• Implementation

  ---

• Course Schedule (Can You Finish All Courses?)

  Problem: There are n courses labeled 0 to n-1. Some courses have prerequisites. Determine if you can finish all courses. This is simply: does a valid topological ordering exist? (i.e., is the prerequisite graph a DAG?) ---

• All Topological Orderings

  Problem: Find ALL valid topological orderings (useful for understanding flexibility in scheduling). Use backtracking: at each step, choose any available node with in-degree 0, recurse, then undo the choice. ---

• Alien Dictionary

  Problem: Given a list of words sorted in an alien language's alphabetical order, derive the ordering of characters.

• Approach

  1. Compare adjacent words to extract ordering rules (edges) 2. Build a directed graph of character precedences 3. Topological sort the graph ---

• Minimum Semesters (Parallel Scheduling)

  Problem: Given courses with prerequisites, find the minimum number of semesters needed to complete all courses (you can take multiple courses per semester if prerequisites are met). This is the longest path in the DAG (or equivalently, p…

• Kahn's vs DFS — When to Use Which

  | Aspect | Kahn's (BFS) | DFS-based | |--------|-------------|-----------| | Cycle detection | Result size < n | Encountering VISITING state | | Level-by-level | Natural (for parallel scheduling) | Requires extra work | | Implementation…

• Complexity Summary

  | Operation | Time | Space | |-----------|------|-------| | Topological sort (Kahn's or DFS) | O(V + E) | O(V + E) | | Course schedule | O(V + E) | O(V + E) | | All topological orderings | O(V! V) worst case | O(V + E) | | Alien diction…

• Pattern Recognition Checklist

  Ask yourself: 1. Are there directed dependencies between items? 2. Do I need to find a valid processing order? 3. Do I need to detect if an ordering is possible (cycle detection)? 4. Am I scheduling tasks in minimum time with parallelism…