Cycle Detection in Undirected Graph in DSA C - Execution Trace

Concept Flow - Cycle Detection in Undirected Graph

Start at any unvisited node

↓

Mark node as visited

↓

For each adjacent node

↓

If adjacent not visited

↓

Recurse DFS on adjacent

↓

If adjacent visited and not parent

↓

Cycle detected! Stop

↓

No cycle found in this path

↓

Repeat for all nodes

↓

End: Cycle exists or not

Start DFS from each unvisited node, mark visited, check neighbors. If a visited neighbor is not parent, cycle exists.

Execution Sample

DSA C

void dfs(int node, int parent) {
  visited[node] = 1;
  for (int neighbor : graph[node]) {
    if (!visited[neighbor]) dfs(neighbor, node);
    else if (neighbor != parent) cycle_found = 1;
  }
}

DFS visits nodes, marks visited, detects cycle if visited neighbor is not parent.

Execution Table

Step	Operation	Current Node	Neighbor	Visited Set	Parent	Cycle Detected	Graph State
1	Start DFS	0	-	{}	-	No	0: [1,2], 1: [0,3], 2: [0,3], 3: [1,2]
2	Visit node 0	0	-	{0}	-	No	0: [1,2], 1: [0,3], 2: [0,3], 3: [1,2]
3	Check neighbor 1	0	1	{0}	0	No	Same
4	Visit node 1	1	-	{0,1}	0	No	Same
5	Check neighbor 0	1	0	{0,1}	1	No	Same
6	Neighbor 0 is parent, continue	1	0	{0,1}	1	No	Same
7	Check neighbor 3	1	3	{0,1}	1	No	Same
8	Visit node 3	3	-	{0,1,3}	1	No	Same
9	Check neighbor 1	3	1	{0,1,3}	3	No	Same
10	Neighbor 1 is parent, continue	3	1	{0,1,3}	3	No	Same
11	Check neighbor 2	3	2	{0,1,3}	3	No	Same
12	Visit node 2	2	-	{0,1,2,3}	3	No	Same
13	Check neighbor 0	2	0	{0,1,2,3}	3	No	Same
14	Neighbor 0 visited and not parent (3), cycle detected	2	0	{0,1,2,3}	3	Yes	Same
15	Stop DFS due to cycle	-	-	{0,1,2,3}	-	Yes	Same

💡 Cycle detected at step 14 when visiting neighbor 0 from node 2 which is visited and not parent

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 8	After Step 12	After Step 14	Final
visited	{}	{0}	{0,1}	{0,1,3}	{0,1,2,3}	{0,1,2,3}	{0,1,2,3}
current_node	-	0	1	3	2	2	-
parent	-	-	0	1	3	3	-
cycle_found	No	No	No	No	No	Yes	Yes

Key Moments - 3 Insights

Why do we check if the visited neighbor is not the parent?

Because the parent is the node we came from, so visiting it again is normal and not a cycle. See step 6 and 10 in execution_table where neighbor is parent and no cycle is detected.

What happens when we find a visited neighbor that is not the parent?

It means we found a back edge, indicating a cycle. This is shown at step 14 where neighbor 0 is visited and not parent, so cycle_found is set to Yes.

Why do we stop DFS immediately after detecting a cycle?

Because once a cycle is found, continuing is unnecessary. Step 15 shows DFS stops after cycle detection at step 14.

Visual Quiz - 3 Questions

Look at the execution_table, what is the visited set after step 8?

A {0,1,2,3}

B {0,1}

C {0,1,3}

D {}

💡 Hint

Check the Visited Set column at step 8 in execution_table

At which step does the cycle get detected?

A Step 10

B Step 14

C Step 6

D Step 12

💡 Hint

Look for 'cycle detected' in the Cycle Detected column in execution_table

If the graph had no edge between node 2 and node 0, what would happen?

A No cycle would be detected

B Cycle would be detected earlier

C Cycle would still be detected at step 14

D DFS would not start

💡 Hint

Refer to the Graph State and cycle detection condition in execution_table step 14

Concept Snapshot

Cycle Detection in Undirected Graph using DFS
- Start DFS from unvisited nodes
- Mark nodes visited
- For each neighbor:
  - If not visited, DFS recursively
  - If visited and not parent, cycle found
- Stop when cycle detected or all nodes visited

Full Transcript

Cycle detection in an undirected graph uses depth-first search (DFS). We start DFS from any unvisited node and mark it visited. For each neighbor, if it is not visited, we recursively DFS on it. If the neighbor is visited and is not the parent node, it means a cycle exists. We track visited nodes and parent to avoid false positives. Once a cycle is detected, we stop the search. This method ensures we find cycles by detecting back edges in the DFS tree.