DAG Detection and Prerequisites
You'll learn: Why cycles in a graph block topological ordering and how to confirm a graph is a Directed Acyclic Graph (DAG).
Why Cycles Break Topological Ordering
Topological sorting arranges vertices in a linear order where every directed edge points forward. But what if your graph contains a cycle?
Imagine trying to schedule three tasks:
- Task A must come before Task B
- Task B must come before Task C
- Task C must come before Task A
There's no valid order! This circular dependency makes topological sorting impossible. A cycle creates a logical contradiction where something must come both before and after something else.
The DAG Prerequisite
For topological sorting to work, your graph must be a DAG (Directed Acyclic Graph):
- Directed: Edges have a specific direction (prerequisites point one way)
- Acyclic: No cycles exist
If cycles are present, no topological order exists.
How to Verify a Graph is a DAG
You already learned cycle detection with DFS! Apply that same technique:
- Run DFS on your graph
- Track vertex states: unvisited, visiting (in current path), or visited (fully explored)
- Detect back edges: If you encounter a vertex marked "visiting" during DFS, you've found a cycle
- If no back edges exist, the graph is a DAG and topological sorting is possible
Think of it as checking for deadlocks before committing to a schedule. If you find circular dependencies early, you know the requirements are impossible to satisfy in sequence.
Key Takeaway: Topological sorting only works on DAGs—you must detect and reject cycles first, typically using DFS-based cycle detection to verify your graph has no circular dependencies.