Cycle detection in graphs in Data Structures Theory - Step-by-Step Execution

Concept Flow - Cycle detection in graphs

Start at a node

↓

Mark node as visited

↓

Explore neighbors

↓

Is neighbor unvisited?

Yes→Recurse on neighbor

↓

Detect cycle if neighbor is in recursion stack

↓

Backtrack

↓

Repeat for all nodes

↓

Cycle found?

Yes→Report cycle

No↓

No cycle in graph

Start from each node, mark it visited, explore neighbors recursively, detect cycle if a neighbor is already in the current recursion path.

Execution Sample

Data Structures Theory

Graph: A-B-C-D with edge D->B
Start DFS at A
Visit A, mark visited
Visit B, mark visited
Visit C, mark visited
Visit D, mark visited
From D, neighbor B is in recursion stack -> cycle detected

This example shows DFS traversal detecting a cycle when revisiting a node in the current recursion path.

Analysis Table

Step	Operation	Current Node	Visited Set	Recursion Stack	Action	Cycle Detected
1	Start DFS	-	{}	{}	Start at node A	No
2	Visit node	A	{A}	{A}	Mark A visited and add to recursion stack	No
3	Visit neighbor	B	{A}	{A}	B unvisited, recurse	No
4	Visit node	B	{A,B}	{A,B}	Mark B visited and add to recursion stack	No
5	Visit neighbor	C	{A,B}	{A,B}	C unvisited, recurse	No
6	Visit node	C	{A,B,C}	{A,B,C}	Mark C visited and add to recursion stack	No
7	Visit neighbor	D	{A,B,C}	{A,B,C}	D unvisited, recurse	No
8	Visit node	D	{A,B,C,D}	{A,B,C,D}	Mark D visited and add to recursion stack	No
9	Visit neighbor	B	{A,B,C,D}	{A,B,C,D}	B already in recursion stack	Yes
10	Backtrack	D	{A,B,C,D}	{A,B,C}	Cycle detected, stop	Yes

💡 Cycle detected at step 9 because neighbor B is already in recursion stack

State Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10
Visited Set	{}	{A}	{A,B}	{A,B,C}	{A,B,C,D}	{A,B,C,D}
Recursion Stack	{}	{A}	{A,B}	{A,B,C}	{A,B,C,D}	{A,B,C}

Key Insights - 3 Insights

Why do we check if a neighbor is in the recursion stack instead of just the visited set?

Because a node in the recursion stack means it's part of the current path, so revisiting it indicates a cycle. The visited set alone includes all visited nodes, not just the current path (see execution_table step 9).

What happens when we backtrack from a node?

We remove the node from the recursion stack but keep it in the visited set to avoid revisiting it again (see execution_table step 10).

Can a cycle be detected if the graph is disconnected?

Yes, cycle detection runs DFS from every unvisited node to cover disconnected parts (concept_flow shows starting from each node).

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the recursion stack?

A {A,B,C}

B {A,B}

C {A,B,C,D}

D {}

💡 Hint

Check the 'Recursion Stack' column at step 6 in the execution_table

At which step does the cycle get detected?

A Step 7

B Step 9

C Step 10

D Step 5

💡 Hint

Look for 'Cycle Detected' column marked 'Yes' in the execution_table

If node B was unvisited at step 9, what would happen next?

A Algorithm would stop immediately

B Cycle would still be detected

C DFS would recurse into B again

D Visited set would be cleared

💡 Hint

Refer to the 'Action' column at step 9 and the concept_flow about recursion on unvisited neighbors

Concept Snapshot

Cycle detection in graphs uses DFS.
Track visited nodes and recursion stack.
If a neighbor is in recursion stack, cycle exists.
Backtrack removes nodes from recursion stack.
Check all nodes for disconnected graphs.

Full Transcript

Cycle detection in graphs is done by starting a depth-first search (DFS) from each node. We keep track of nodes visited and nodes currently in the recursion stack (the current path). When exploring neighbors, if we find a neighbor already in the recursion stack, it means a cycle exists. We backtrack by removing nodes from the recursion stack but keep them in the visited set to avoid repeated work. This process repeats for all nodes to cover disconnected graphs. The example graph with nodes A, B, C, D and an edge from D to B shows cycle detection when revisiting B in the recursion stack during DFS from A.