Cycle Detection (Directed Graph)
Algorithm for detecting cycles in a directed graph using DFS with two sets: visited and in_path.
โณ Cycle Detective
What is a Cycle?
Before we learn to detect cycles, let's understand what they are.
Directed Graph (No Cycle)
A directed graph is a set of nodes connected by edges that have a direction (arrows). When you can follow the arrows from any starting node without ever returning to a node you've already been on, the graph has no cycle. We call this a DAG (Directed Acyclic Graph).
A โ B โ C โ no way to loop back. This is a DAG.
Directed Graph (With Cycle)
A cycle exists when you can follow the arrows from a node and eventually return back to that same node. Think of it like getting stuck in an infinite loop โ you keep going around and around.
A โ B โ C โ D โ A โ following the arrows leads back to where we started!
Why Does It Matter?
Cycle detection is crucial in many real-world problems: detecting deadlocks in operating systems, finding circular dependencies in build systems and package managers, validating prerequisite chains in course scheduling, and ensuring correctness in data pipelines.
In this game, you'll learn the classic DFS (Depth-First Search) algorithm for cycle detection using two boolean arrays: visited[] and in_path[].