Cycle Detection in Undirected Graph in DSA Java - 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?

Yes→Return True

No↓

Continue

↓

All neighbors checked

↓

Return False (no cycle)

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

Execution Sample

DSA Java

boolean dfs(int node, int parent) {
  visited[node] = true;
  for (int nbr : graph[node]) {
    if (!visited[nbr]) {
      if (dfs(nbr, node)) return true;
    } else if (nbr != parent) {
      return true;
    }
  }
  return false;
}

DFS checks neighbors; if a visited neighbor is not parent, cycle detected.

Execution Table

Step	Operation	Current Node	Visited Set	Parent	Action	Visual State
1	Start DFS	0	[0]	-1	Mark 0 visited	0(visited)
2	Explore neighbor	0	[0]	-1	Neighbor 1 not visited, recurse	0(visited) -> 1
3	Start DFS	1	[0,1]	0	Mark 1 visited	0(visited) -> 1(visited)
4	Explore neighbor	1	[0,1]	0	Neighbor 0 visited but parent, continue	0(visited) -> 1(visited)
5	Explore neighbor	1	[0,1]	0	Neighbor 2 not visited, recurse	0(visited) -> 1(visited) -> 2
6	Start DFS	2	[0,1,2]	1	Mark 2 visited	0(visited) -> 1(visited) -> 2(visited)
7	Explore neighbor	2	[0,1,2]	1	Neighbor 1 visited but parent, continue	0(visited) -> 1(visited) -> 2(visited)
8	Explore neighbor	2	[0,1,2]	1	Neighbor 3 not visited, recurse	0(visited) -> 1(visited) -> 2(visited) -> 3
9	Start DFS	3	[0,1,2,3]	2	Mark 3 visited	0(visited) -> 1(visited) -> 2(visited) -> 3(visited)
10	Explore neighbor	3	[0,1,2,3]	2	Neighbor 2 visited but parent, continue	0(visited) -> 1(visited) -> 2(visited) -> 3(visited)
11	Explore neighbor	3	[0,1,2,3]	2	Neighbor 4 not visited, recurse	0(visited) -> 1(visited) -> 2(visited) -> 3(visited) -> 4
12	Start DFS	4	[0,1,2,3,4]	3	Mark 4 visited	0(visited) -> 1(visited) -> 2(visited) -> 3(visited) -> 4(visited)
13	Explore neighbor	4	[0,1,2,3,4]	3	Neighbor 3 visited but parent, continue	0(visited) -> 1(visited) -> 2(visited) -> 3(visited) -> 4(visited)
14	Explore neighbor	4	[0,1,2,3,4]	3	Neighbor 1 visited and not parent → Cycle found	Cycle detected at node 4 via neighbor 1
15	Return True	4	[0,1,2,3,4]	3	Propagate cycle detection up	Cycle detected
16	Return True	3	[0,1,2,3,4]	2	Propagate cycle detection up	Cycle detected
17	Return True	2	[0,1,2,3,4]	1	Propagate cycle detection up	Cycle detected
18	Return True	1	[0,1,2,3,4]	0	Propagate cycle detection up	Cycle detected
19	Return True	0	[0,1,2,3,4]	-1	Cycle detected in graph	Cycle detected

💡 Cycle detected at step 14 when visiting neighbor 1 from node 4 which is already visited and not parent

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	Final
current_node	-	0	1	2	3	4	4	4	-
visited	[]	[0]	[0,1]	[0,1,2]	[0,1,2,3]	[0,1,2,3,4]	[0,1,2,3,4]	[0,1,2,3,4]	[0,1,2,3,4]
parent	-	-1	0	1	2	3	3	3	-
cycle_found	false	false	false	false	false	false	true	true	true

Key Moments - 3 Insights

Why do we check if the visited neighbor is not the parent before declaring a cycle?

Because the parent 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 different from the parent (see step 14 in execution_table).

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

The DFS will mark the starting node visited and find no neighbors to recurse into, so no cycle is detected and the function returns false (not shown in this example but implied by exit conditions).

Why do we propagate the 'true' cycle detection back up the recursion?

Because once a cycle is found deep in recursion (step 14), all previous calls return true to indicate cycle presence in the graph (steps 15-19).

Visual Quiz - 3 Questions

Look at the execution_table at step 14, what causes the cycle detection?

A Visiting a neighbor that is the parent

B Visiting a neighbor that is not visited

C Visiting a neighbor that is already visited and not the parent

D No neighbors left to visit

💡 Hint

Check the 'Action' column at step 14 in execution_table

At which step does the visited set first contain node 3?

A Step 7

B Step 9

C Step 11

D Step 5

💡 Hint

Look at the 'Visited Set' column in execution_table rows

If the graph had no cycle, what would be the final value of 'cycle_found' in variable_tracker?

A false

B null

C true

D undefined

💡 Hint

Refer to the 'cycle_found' row in variable_tracker for the final value

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, else false
- Parent check avoids false cycle from bidirectional edges

Full Transcript

Cycle detection in an undirected graph uses depth-first search (DFS). We start from any node, mark it visited, and explore neighbors. If a neighbor is not visited, we recurse DFS on it. If a neighbor is visited and is not the parent node, it means a cycle exists. We propagate this detection back up the recursion. The parent check is important to avoid mistaking the bidirectional edge back to the parent as a cycle. The visited set tracks nodes already explored. If no cycle is found after exploring all nodes, the graph is acyclic.

Practice

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

easy

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

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

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

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

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 during DFS, 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 D

4. Quick Check:

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

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

Common Mistakes:

• Confusing parent node with visited node
• Assuming disconnected graph always has cycles
• Thinking more edges than nodes always means cycle

2. Which of the following Java method signatures is correct for a DFS function used in cycle detection in an undirected graph?

easy

A. boolean dfs(int node, boolean[] visited, List graph)

B. void dfs(int node, int parent, boolean[] visited, List<Integer> graph)

C. boolean dfs(int node, int parent, boolean[] visited, List graph)

D. int dfs(int node, int parent, boolean[] visited, List graph)

Solution

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

   DFS needs current node, parent node, visited array, and adjacency list graph.

2. Step 2: Check return type and parameter types

   Return type boolean indicates if cycle found; graph must be List of Lists for adjacency; parent is needed.

3. Final Answer:

   boolean dfs(int node, int parent, boolean[] visited, List<List<Integer>> graph) -> Option C

4. Quick Check:

   DFS signature with parent and boolean return = boolean dfs(int node, int parent, boolean[] visited, List graph) [OK]

Hint: DFS needs parent node and boolean return for cycle detection [OK]

Common Mistakes:

• Using void return type instead of boolean
• Passing graph as List<Integer> instead of List
• Omitting parent parameter

3. What will be the output of the following Java code snippet detecting cycle in an undirected graph?

import java.util.*;
public class GraphCycle {
    static boolean dfs(int node, int parent, boolean[] visited, List graph) {
        visited[node] = true;
        for (int adj : graph.get(node)) {
            if (!visited[adj]) {
                if (dfs(adj, node, visited, graph)) return true;
            } else if (adj != parent) {
                return true;
            }
        }
        return false;
    }
    public static void main(String[] args) {
        int n = 4;
        List graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        graph.get(0).add(1); graph.get(1).add(0);
        graph.get(1).add(2); graph.get(2).add(1);
        graph.get(2).add(3); graph.get(3).add(2);
        graph.get(3).add(1); graph.get(1).add(3);
        boolean[] visited = new boolean[n];
        boolean hasCycle = false;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                if (dfs(i, -1, visited, graph)) {
                    hasCycle = true;
                    break;
                }
            }
        }
        System.out.println(hasCycle);
    }
}

medium

A. true

B. false

C. Compilation error

D. Runtime exception

Solution

1. Step 1: Analyze graph edges and structure

   Graph edges: 0-1, 1-2, 2-3, 3-1 form a cycle (1-2-3-1).

2. Step 2: Trace DFS cycle detection logic

   DFS finds visited node 1 again from 3 (not parent), so returns true indicating cycle.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Cycle detected in graph = true [OK]

Hint: Look for back edge to visited node not parent to confirm cycle [OK]

Common Mistakes:

• Ignoring the edge 3-1 that closes the cycle
• Assuming no cycle because graph is connected
• Misunderstanding parent check in DFS

4. Identify the bug in the following Java code snippet for cycle detection in an undirected graph:

boolean dfs(int node, int parent, boolean[] visited, List graph) {
    visited[node] = true;
    for (int adj : graph.get(node)) {
        if (!visited[adj]) {
            dfs(adj, node, visited, graph);
        } else if (adj != parent) {
            return true;
        }
    }
    return false;
}

medium

A. Incorrect parent check condition

B. Missing return statement for recursive dfs call result

C. Visited array not updated correctly

D. Graph adjacency list type is wrong

Solution

1. Step 1: Review recursive DFS calls

   Recursive call dfs(adj, node, visited, graph) is made but its boolean result is ignored.

2. Step 2: Understand impact of ignoring return value

   If a cycle is detected deeper, it won't propagate true back, causing false negatives.

3. Final Answer:

   Missing return statement for recursive dfs call result -> Option B

4. Quick Check:

   Return recursive call result to detect cycles correctly [OK]

Hint: Always return recursive DFS call result when checking for cycles [OK]

Common Mistakes:

• Not returning true from recursive calls
• Confusing parent check logic
• Not marking nodes visited before recursion

5. Given an undirected graph represented as adjacency list:

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

Which of the following modifications will correctly detect a cycle in this graph using DFS cycle detection method?

hard

A. Start DFS from node 0 and pass -1 as parent; check visited nodes for back edges.

B. Start DFS from node 4 only; ignore parent parameter in DFS calls.

C. Use BFS instead of DFS without parent tracking to detect cycles.

D. Mark nodes visited after all recursive calls complete.

Solution

1. Step 1: Understand graph structure and cycle presence

   Edges form a cycle: 0-1-3-2-0. Starting DFS from 0 covers all nodes.

2. Step 2: Apply correct DFS cycle detection method

   Starting DFS from 0 with parent -1 and checking visited nodes excluding parent detects cycle correctly.

3. Final Answer:

   Start DFS from node 0 and pass -1 as parent; check visited nodes for back edges. -> Option A

4. Quick Check:

   Proper DFS start and parent check detects cycle [OK]

Hint: Start DFS from any node with parent -1 and track visited nodes [OK]

Common Mistakes:

• Ignoring parent parameter causing false positives
• Starting DFS from leaf node only
• Marking visited nodes too late