What is a cycle in a graph?

A cycle is a path in a graph that starts and ends at the same node, passing through at least one other node. In a directed graph, the edges must follow the direction; in an undirected graph, any closed path with at least three nodes forms a cycle.

How does DFS detect cycles?

DFS detects cycles using three-color marking. Nodes start as white (unvisited), turn gray (in progress) when first visited, and black (done) when fully processed. If DFS encounters a gray node, it means there's a back edge forming a cycle.

What is the difference between cycle detection in directed and undirected graphs?

In directed graphs, a cycle exists only when a back edge points to an ancestor in the DFS tree (a gray node). In undirected graphs, any edge to a visited node that isn't the direct parent indicates a cycle.

Cycle Detection Visualizer

Visualize how cycle detection identifies loops in a graph. Build your own graph and watch the algorithm trace through nodes to find circular paths.

Visualize Cycle Detection

How It Works

Cycle detection determines whether a graph contains a cycle — a path that starts and ends at the same node. In directed graphs, this uses DFS with node coloring (white/gray/black) to detect back edges. In undirected graphs, a back edge to a visited node (other than the parent) indicates a cycle.

Detecting cycles is fundamental in computer science: it prevents infinite loops in dependency resolution, validates DAG structures, and ensures correctness in scheduling algorithms.

1
Start DFS from an unvisited node and mark it as in-progress (gray)
2
Recursively visit each unvisited neighbor
3
If a neighbor is already in-progress (gray), a cycle is detected via a back edge
4
After processing all neighbors, mark the node as completed (black)
5
If all neighbors are either unvisited or completed, no cycle through this path
6
Repeat from the next unvisited node until all nodes are processed

Key Properties

Time Complexity

O(V + E) where V is the number of vertices and E is the number of edges.

Back Edge Detection

Identifies cycles by finding edges that point back to an ancestor in the DFS tree.

DFS-Based

Uses depth-first traversal with three-color marking to track node states during exploration.

Directed & Undirected

Works on both directed and undirected graphs with slight variations in back edge detection.

Common Use Cases

Deadlock detection — finding circular wait conditions in operating systems
Dependency validation — ensuring package dependencies form a DAG with no circular imports
Workflow validation — verifying that task pipelines have no circular dependencies

Frequently Asked Questions

What is a cycle in a graph?: A cycle is a path in a graph that starts and ends at the same node, passing through at least one other node. In a directed graph, the edges must follow the direction; in an undirected graph, any closed path with at least three nodes forms a cycle.
How does DFS detect cycles?: DFS detects cycles using three-color marking. Nodes start as white (unvisited), turn gray (in progress) when first visited, and black (done) when fully processed. If DFS encounters a gray node, it means there's a back edge forming a cycle.
What is the difference between cycle detection in directed and undirected graphs?: In directed graphs, a cycle exists only when a back edge points to an ancestor in the DFS tree (a gray node). In undirected graphs, any edge to a visited node that isn't the direct parent indicates a cycle.
What is the time complexity of cycle detection?: DFS-based cycle detection runs in O(V + E) time, where V is the number of vertices and E is the number of edges. It visits each vertex and edge at most once.

Ready to see it in action?

Open the Visualizer