Multiple Valid Orderings
What you'll learn: You'll understand why a single DAG can have many valid topological sorts and how to recognize when multiple orderings exist.
The Core Idea
When you perform a topological sort on a Directed Acyclic Graph (DAG), the result isn't always unique. Multiple valid orderings can exist because there's often no strict ordering between vertices that don't depend on each other.
Think of it like getting dressed: you must put on socks before shoes, but whether you put on your shirt before or after your socks doesn't matter. Both orderings satisfy the prerequisites.
Why Multiple Orderings Exist
Consider a simple DAG where vertex A points to C, and vertex B points to C. Both A and B must come before C, but A and B have no dependency between themselves. This means both [A, B, C] and [B, A, C] are valid topological sorts.
The more "independent branches" your DAG has (vertices with no edges connecting them), the more valid orderings exist. If vertices have many parallel paths with no cross-dependencies, you'll have many choices at each step of the sort.
Recognizing Multiple Orderings
During Kahn's Algorithm, whenever your queue contains more than one vertex with in-degree zero, you have a choice about which to process next. Each choice can lead to a different valid ordering.
With DFS-based sorting, vertices finishing at similar times with no dependencies between them can be ordered in multiple ways.
Enumerating All Valid Orderings
To find all possible topological sorts, you'd use backtracking: at each step, try processing each available zero-in-degree vertex, recursively explore that branch, then backtrack and try another. This grows exponentially with the number of independent vertices.
Key Takeaway: DAGs typically have multiple valid topological orderings because vertices without dependencies between them can be ordered arbitrarily—the more parallel structure, the more valid sorts exist.