Cycle Detection in Undirected Graph in DSA Typescript - Execution Trace

Concept Flow - Cycle Detection in Undirected Graph

Start at any node

↓

Mark node as visited

↓

For each neighbor

↓

If neighbor not visited

↓

Recurse DFS

↓

Cycle found

↓

Return result

Start DFS from any node, mark nodes visited, check neighbors. If a visited neighbor is not the parent, cycle exists.

Execution Sample

DSA Typescript

const graph = {
  0: [1, 2],
  1: [0, 2],
  2: [0, 1, 3],
  3: [2]
};
// Detect cycle using DFS

Detects cycle in an undirected graph using DFS and parent tracking.

Execution Table

Step	Operation	Current Node	Visited Set	Parent	Neighbor Checked	Cycle Detected	Visual State
1	Start DFS	0	{}	null	None	No	Nodes: 0 Edges: 0
2	Visit node 0	0	{0}	null	1	No	0 -> visited
3	Check neighbor 1 of 0	0	{0}	null	1	No	0 connected to 1
4	Neighbor 1 not visited, DFS to 1	1	{0}	0	None	No	Traverse 0->1
5	Visit node 1	1	{0,1}	0	0	No	1 -> visited
6	Check neighbor 0 of 1	1	{0,1}	0	0	No	Neighbor is parent, ignore
7	Check neighbor 2 of 1	1	{0,1}	0	2	No	Check 2 from 1
8	Neighbor 2 not visited, DFS to 2	2	{0,1}	1	None	No	Traverse 1->2
9	Visit node 2	2	{0,1,2}	1	0	No	2 -> visited
10	Check neighbor 0 of 2	2	{0,1,2}	1	0	Yes	0 visited and not parent, cycle found
11	Cycle detected, stop DFS	2	{0,1,2}	1	0	Yes	Cycle confirmed
12	Return True	N/A	{0,1,2}	N/A	N/A	Yes	Cycle exists in graph

💡 Cycle detected at step 10 when neighbor 0 of node 2 is visited and not parent

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 9	Final
Current Node	null	0	1	2	N/A
Visited Set	{}	{0}	{0,1}	{0,1,2}	{0,1,2}
Parent	null	null	0	1	N/A
Cycle Detected	No	No	No	No	Yes

Key Moments - 3 Insights

Why do we ignore the neighbor if it is the parent node during DFS?

Because the parent node is where we came from, so visiting it again does not mean a cycle. See step 6 where neighbor 0 is parent of 1 and no cycle is detected.

How do we know a cycle exists when we find a visited neighbor that is not the parent?

If a neighbor is visited and not the parent, it means we found a back edge forming a loop. This happens at step 10 where neighbor 0 of node 2 is visited but not parent, so cycle is detected.

What happens if the graph has no edges or is empty?

DFS will visit nodes but never find a visited neighbor that is not parent, so no cycle is detected and DFS ends normally.

Visual Quiz - 3 Questions

Look at the execution table, what is the visited set after visiting node 1?

A {0}

B {0,1}

C {1}

D {}

💡 Hint

Check step 5 in the execution table under Visited Set column

At which step does the cycle get detected in the graph?

A Step 10

B Step 8

C Step 6

D Step 12

💡 Hint

Look at Cycle Detected column in execution table rows

If the graph had no edges, how would the cycle detection result change?

A Algorithm would crash

B Cycle detected immediately

C No cycle detected

D Cycle detected at last step

💡 Hint

Refer to key moment about empty graph and no edges

Concept Snapshot

Cycle Detection in Undirected Graph using DFS:
- Start DFS from any node
- Mark node visited
- For each neighbor:
  - If not visited, DFS recursively
  - If visited and not parent, cycle found
- Return true if cycle detected, else false

Full Transcript

Cycle detection in an undirected graph uses depth-first search (DFS). We start from any node and mark it visited. For each neighbor, if it is not visited, we recursively DFS into it. If a neighbor is visited and is not the parent node, it means a cycle exists. We track the parent to avoid false positives from the edge we came from. The process stops when a cycle is found or all nodes are visited without finding a cycle. This method works because a back edge to a visited node other than the parent indicates a loop in the graph.