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.

Practice

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

easy

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

B. If all nodes are visited exactly once, the graph has a cycle.

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

D. If the graph has more edges than nodes, it always has a cycle.

Solution

1. Step 1: Understand DFS traversal in undirected graph

   DFS visits nodes and tracks the parent node to avoid false cycle detection.

2. Step 2: Detect cycle condition

   If a visited node is found that is not the parent, it means a back edge exists, indicating a cycle.

3. Final Answer:

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

4. Quick Check:

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

Hint: Check visited neighbors excluding parent to find cycles [OK]

Common Mistakes:

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

2. Which of the following is the correct function signature in C for DFS used in cycle detection in an undirected graph?

easy

A. bool dfs(int node, int parent, int visited[], int graph[][100], int n)

B. int dfs(int node, int visited[], int graph[][100])

C. void dfs(int node, int graph[][100], int visited[])

D. int dfs(int node, int parent, int graph[][100])

Solution

1. Step 1: Identify parameters needed for DFS cycle detection

   We need current node, parent node, visited array, adjacency matrix, and number of nodes.

2. Step 2: Match function signature with parameters

   bool dfs(int node, int parent, int visited[], int graph[][100], int n) includes all required parameters with correct types and order.

3. Final Answer:

   bool dfs(int node, int parent, int visited[], int graph[][100], int n) -> Option A

4. Quick Check:

   DFS signature includes node, parent, visited, graph, size [OK]

Hint: Include parent parameter to avoid false cycle detection [OK]

Common Mistakes:

• Omitting parent parameter
• Wrong return type for DFS
• Missing graph size parameter

3. Consider the following adjacency matrix for an undirected graph with 4 nodes:

int graph[4][4] = {
  {0, 1, 0, 0},
  {1, 0, 1, 1},
  {0, 1, 0, 0},
  {0, 1, 0, 0}
};

If we run cycle detection using DFS starting from node 0, what will be the output?

medium

A. Cycle detected

B. No cycle detected

C. Runtime error due to invalid indexing

D. Infinite loop

Solution

1. Step 1: Analyze graph edges from adjacency matrix

   Edges: 0-1, 1-2, 1-3. Node 1 connects to nodes 0, 2, 3.

2. Step 2: Check for cycle using DFS

   Starting at 0, DFS visits 1, then 2 and 3. Node 1 connects back to 0 (parent), no cycle there. No back edge to visited non-parent node is found, so no cycle.

3. Final Answer:

   No cycle detected -> Option B

4. Quick Check:

   Graph edges form a tree structure = No cycle [OK]

Hint: Trace DFS and check visited nodes excluding parent [OK]

Common Mistakes:

• Assuming any connected graph has cycle
• Ignoring parent node in cycle check
• Confusing adjacency matrix indexing

4. The following C code snippet is intended to detect a cycle in an undirected graph using DFS. What is the bug?

bool dfs(int node, int parent, int visited[], int graph[][100], int n) {
  visited[node] = 1;
  for (int i = 0; i < n; i++) {
    if (graph[node][i] == 1) {
      if (!visited[i]) {
        if (dfs(i, node, visited, graph, n))
          return true;
      } else if (i != parent) {
        return true;
      }
    }
  }
  return false;
}

medium

A. The visited array is not initialized before calling dfs.

B. The parent parameter is not passed correctly in recursive calls.

C. The graph adjacency matrix is accessed out of bounds.

D. The function should return void, not bool.

Solution

1. Step 1: Check initialization of visited array

   The code snippet does not show visited array initialization, which is required to mark nodes unvisited before DFS.

2. Step 2: Verify other parameters and logic

   Parent is passed correctly, adjacency matrix access is within bounds, and return type bool is appropriate for cycle detection.

3. Final Answer:

   The visited array is not initialized before calling dfs. -> Option A

4. Quick Check:

   Initialize visited[] before DFS to avoid incorrect results [OK]

Hint: Always initialize visited array to zero before DFS [OK]

Common Mistakes:

• Forgetting to initialize visited array
• Passing wrong parent in recursion
• Misusing return type for DFS

5. You have an undirected graph represented by adjacency lists:

0: 1, 2
1: 0, 3
2: 0, 3
3: 1, 2

Using cycle detection with DFS, which nodes form the cycle and why?

hard

A. Nodes 0, 1, 3 form a cycle because 0 connects to 1 and 1 connects to 3.

B. Nodes 0, 2, 3 form a cycle because 0 connects to 2 and 2 connects to 3 which connects back to 0.

C. Nodes 1, 2, 3 form a cycle because 1 connects to 3 and 2 connects to 3.

D. Nodes 0, 1, 2, 3 form a cycle because they form a closed loop through all edges.

Solution

1. Step 1: Analyze adjacency lists for cycles

   Edges: 0-1, 0-2, 1-3, 2-3. These edges connect nodes forming a square shape.

2. Step 2: Identify cycle involving all nodes

   Starting at 0, path 0->1->3->2->0 forms a closed loop including all four nodes, indicating a cycle involving nodes 0,1,2,3.

3. Final Answer:

   Nodes 0, 1, 2, 3 form a cycle because they form a closed loop through all edges. -> Option D

4. Quick Check:

   Cycle includes all nodes forming closed loop [OK]

Hint: Look for closed loops connecting all nodes [OK]

Common Mistakes:

• Identifying partial cycles ignoring full loop
• Confusing connected nodes with cycle nodes
• Missing edges that complete the cycle