Cycle Detection in Undirected Graph in DSA C# - 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 on neighbor

↓

Check cycle in recursion

↓

If cycle found anywhere

↓

Return True

↓

No cycle found

↓

Return False

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

Execution Sample

DSA C#

bool DFS(int node, int parent) {
  visited[node] = true;
  foreach (int neighbor in graph[node]) {
    if (!visited[neighbor]) {
      if (DFS(neighbor, node)) return true;
    } else if (neighbor != parent) {
      return true;
    }
  }
  return false;
}

DFS explores nodes, marks visited, and detects cycle if a visited neighbor is not the parent.

Execution Table

Step	Operation	Current Node	Visited Set	Parent Node	Cycle Detected	Visual State
1	Start DFS at node 0	0	[0]	-1	No	0(visited)
2	Explore neighbor 1 of node 0	1	[0,1]	0	No	0(visited) -> 1(visited)
3	Explore neighbor 2 of node 1	2	[0,1,2]	1	No	0 -> 1 -> 2(visited)
4	Explore neighbor 1 of node 2	2	[0,1,2]	1	No	Cycle check: neighbor 1 is parent of 2? Yes, no cycle
5	Explore neighbor 3 of node 2	3	[0,1,2,3]	2	No	0 -> 1 -> 2 -> 3(visited)
6	Explore neighbor 1 of node 3	3	[0,1,2,3]	2	Yes	Cycle check: neighbor 1 visited and not parent(2)? Yes, cycle detected
7	Return True due to cycle	3	[0,1,2,3]	2	Yes	Cycle found
8	Return True up recursion	2	[0,1,2,3]	1	Yes	Cycle found
9	Return True up recursion	1	[0,1,2,3]	0	Yes	Cycle found
10	Return True up recursion	0	[0,1,2,3]	-1	Yes	Cycle found

💡 Cycle detected at step 6 when visiting neighbor 1 from node 3 which is visited and not parent

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
visited	[]	[0]	[0,1]	[0,1,2]	[0,1,2]	[0,1,2,3]	[0,1,2,3]	[0,1,2,3]
current_node	-	0	1	2	2	3	3	-
parent_node	-	-1	0	1	1	2	2	-
cycle_detected	No	No	No	No	No	No	Yes	Yes

Key Moments - 3 Insights

Why do we check if the visited neighbor is not the parent node to detect a cycle?

Because in an undirected graph, the parent node is the node we came from, so visiting it again is normal and not a cycle. The cycle is detected only if a visited neighbor is not the parent (see step 6 in execution_table).

What happens if the graph is disconnected?

We run DFS from every unvisited node to cover all components. Cycle detection applies to each component separately.

Why do we mark nodes as visited before exploring neighbors?

Marking visited early prevents revisiting the same node and infinite loops during DFS (see visited set updates in execution_table steps).

Visual Quiz - 3 Questions

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

A [0,1,2,3]

B [0,1]

C [0,1,2]

D [0]

💡 Hint

Check the 'Visited Set' column in row with Step 3.

At which step does the cycle get detected?

A Step 4

B Step 6

C Step 2

D Step 10

💡 Hint

Look for 'Cycle Detected' column showing 'Yes' in execution_table.

If we start DFS from node 1 instead of node 0, how would the visited set after first step change?

A [1]

B [0,1]

C [0]

D []

💡 Hint

Starting DFS at node 1 marks node 1 visited first (see variable_tracker for visited sets).

Concept Snapshot

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

Full Transcript

Cycle detection in an undirected graph uses depth-first search (DFS). We start DFS from any node, marking it visited. For each neighbor, if it is not visited, we recurse DFS on it. If the neighbor is visited and is not the parent node, we detect a cycle. The parent node check is important because in undirected graphs, edges go both ways, so revisiting the parent is normal and not a cycle. The visited set grows as we explore nodes. If a cycle is found, we return true up the recursion stack. If no cycle is found after exploring all nodes, we return false. For disconnected graphs, DFS is started from every unvisited node to cover all components. This method ensures we detect cycles efficiently by tracking visited nodes and parent relationships.

Practice

1. What is the main idea behind detecting a cycle in an undirected graph using DFS?

easy

A. If we visit a node that is already visited and is not the parent, a cycle exists.

B. If all nodes are visited exactly once, there is a cycle.

C. If the graph has more edges than nodes, it must have a cycle.

D. If the graph is disconnected, it contains a cycle.

Solution

1. Step 1: Understand DFS traversal in undirected graph

   DFS visits nodes and keeps track of the parent node to avoid false cycle detection.

2. Step 2: Detect cycle condition

   If during DFS, a visited node is found that is not the parent of the current node, it means a cycle exists.

3. Final Answer:

   If we visit a node that is already visited and is not the parent, a cycle exists. -> Option A

4. Quick Check:

   Cycle detection in undirected graph = check visited node not parent [OK]

Hint: Check visited nodes excluding parent during DFS [OK]

Common Mistakes:

• Ignoring parent node in cycle check
• Assuming disconnected graph always has cycle
• Confusing cycle detection with edge count

2. Which of the following C# code snippets correctly initializes an adjacency list for an undirected graph with 3 nodes?

easy

A. var graph = new List<int>[3]; for(int i=0; i<3; i++) graph[i] = new List<int>();

B. var graph = new List<int>[3]; graph = new List<int>();

C. List<int> graph = new List<int>[3];

D. var graph = new List(); graph.Add(new List<int>());

Solution

1. Step 1: Understand adjacency list initialization

   We need an array of lists, each list initialized separately to hold neighbors.

2. Step 2: Check code correctness

   var graph = new List<int>[3]; for(int i=0; i<3; i++) graph[i] = new List<int>(); creates an array of List<int> and initializes each element with a new List<int>, which is correct.

3. Final Answer:

   var graph = new List<int>[3]; for(int i=0; i<3; i++) graph[i] = new List<int>(); -> Option A

4. Quick Check:

   Initialize array of lists with loop [OK]

Hint: Initialize each list in array separately [OK]

Common Mistakes:

• Not initializing each list element
• Using wrong data types for adjacency list
• Assigning list directly to array variable

3. Consider the following C# code snippet for cycle detection in an undirected graph:

bool DFS(int node, int parent, List<int>[] graph, bool[] visited) {
    visited[node] = true;
    foreach(var neighbor in graph[node]) {
        if(!visited[neighbor]) {
            if(DFS(neighbor, node, graph, visited)) return true;
        } else if(neighbor != parent) {
            return true;
        }
    }
    return false;
}

// Graph edges: 0-1, 1-2, 2-0
// Call: DFS(0, -1, graph, visited)

What will be the output of this DFS call?

medium

A. Compilation error

B. false

C. StackOverflowException

D. true

Solution

1. Step 1: Analyze graph structure and DFS call

   The graph has edges 0-1, 1-2, and 2-0 forming a triangle cycle. DFS starts at node 0 with parent -1.

2. Step 2: Trace DFS for cycle detection

   DFS visits 0, then 1, then 2. When 2 checks neighbors, it finds 0 already visited and not parent, so returns true indicating cycle.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Triangle graph cycle detected = true [OK]

Hint: Cycle if visited neighbor not parent found [OK]

Common Mistakes:

• Ignoring parent check causing false cycle
• Assuming no cycle in triangle graph
• Confusing return values in recursion

4. The following C# code attempts to detect a cycle in an undirected graph but has a bug:

bool DFS(int node, int parent, List<int>[] graph, bool[] visited) {
    visited[node] = true;
    foreach(var neighbor in graph[node]) {
        if(!visited[neighbor]) {
            if(DFS(neighbor, node, graph, visited)) return true;
        } else {
            return true;
        }
    }
    return false;
}

What is the bug in this code?

medium

A. It never marks nodes as visited.

B. It returns true even if the visited neighbor is the parent node.

C. It does not traverse all neighbors.

D. It causes infinite recursion.

Solution

1. Step 1: Review cycle detection condition

   The code returns true if a neighbor is visited, but does not check if neighbor is parent.

2. Step 2: Identify why this causes incorrect cycle detection

   In undirected graphs, the parent node is always visited, so returning true here falsely detects a cycle.

3. Final Answer:

   It returns true even if the visited neighbor is the parent node. -> Option B

4. Quick Check:

   Must exclude parent node in cycle check [OK]

Hint: Exclude parent node when checking visited neighbors [OK]

Common Mistakes:

• Missing parent check in visited condition
• Assuming any visited neighbor means cycle
• Not marking nodes visited before recursion

5. You have an undirected graph represented as adjacency list:

0: [1, 2]
1: [0, 3]
2: [0, 3]
3: [1, 2, 4]
4: [3]

Using DFS cycle detection, which node will first detect the cycle and why?

hard

A. Node 4, because it has only one neighbor.

B. Node 0, because it starts the DFS traversal.

C. Node 2, because it connects back to already visited node 0.

D. Node 1, because it has the smallest index among neighbors.

Solution

1. Step 1: Understand graph structure and DFS traversal

   Assuming neighbor lists are processed in listed order, DFS starts at node 0, visits 1 (first neighbor), then 3 (from 1), then 2 (from 3).

2. Step 2: Identify where cycle is detected

   Node 2 has neighbors 0 and 3; 0 is already visited and not parent (parent=3), so cycle is detected at node 2 first.

3. Final Answer:

   Node 2, because it connects back to already visited node 0. -> Option C

4. Quick Check:

   Cycle detected at node with visited neighbors not parent [OK]

Hint: Cycle detected where visited neighbors not parent found first [OK]

Common Mistakes:

• Assuming cycle detected at start node
• Ignoring multiple visited neighbors
• Confusing leaf nodes with cycle detection