Course contentsShow
← Computer Science
Lesson 728 of 2,87217. Graph Traversal AlgorithmsFree lesson

Multiple Valid Orderings

Understand that DAGs may have many topological sorts and how to enumerate them.

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.