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

DAG Detection and Prerequisites

Understand why cycles prevent topological ordering and how to verify a graph is a DAG.

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:

  1. Run DFS on your graph
  2. Track vertex states: unvisited, visiting (in current path), or visited (fully explored)
  3. Detect back edges: If you encounter a vertex marked "visiting" during DFS, you've found a cycle
  4. 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.