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

↓

Detect cycle

↓

End

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

Execution Sample

DSA Javascript

function dfs(node, parent) {
  visited[node] = true;
  for (let neighbor of graph[node]) {
    if (!visited[neighbor]) {
      if (dfs(neighbor, node)) return true;
    } else if (neighbor !== parent) {
      return true;
    }
  }
  return false;
}

This code runs DFS to detect a cycle by checking visited neighbors that are not the parent.

Execution Table

Step	Operation	Current Node	Visited Set	Parent Node	Action	Cycle Detected	Graph State
1	Start DFS	0	[0]	null	Mark 0 visited	No	0: [1,2], 1: [0,3], 2: [0,3], 3: [1,2]
2	Explore neighbor	0	[0]	null	Go to neighbor 1	No	Same
3	Start DFS	1	[0,1]	0	Mark 1 visited	No	Same
4	Explore neighbor	1	[0,1]	0	Go to neighbor 3	No	Same
5	Start DFS	3	[0,1,3]	1	Mark 3 visited	No	Same
6	Explore neighbor	3	[0,1,3]	1	Neighbor 1 visited but parent, continue	No	Same
7	Explore neighbor	3	[0,1,3]	1	Go to neighbor 2	No	Same
8	Start DFS	2	[0,1,3,2]	3	Mark 2 visited	No	Same
9	Explore neighbor	2	[0,1,3,2]	3	Neighbor 0 visited and not parent, cycle found	Yes	Same
10	Return	2	[0,1,3,2]	3	Return true up call stack	Yes	Same
11	Return	3	[0,1,3,2]	1	Return true up call stack	Yes	Same
12	Return	1	[0,1,3,2]	0	Return true up call stack	Yes	Same
13	Return	0	[0,1,3,2]	null	Cycle detected, stop	Yes	Same

💡 Cycle detected at step 9 when visiting node 2's neighbor 0 which is visited and not parent

Variable Tracker

Variable	Start	After Step 1	After Step 3	After Step 5	After Step 8	Final
visited	[]	[0]	[0,1]	[0,1,3]	[0,1,3,2]	[0,1,3,2]
current node	null	0	1	3	2	0 (return)
parent	null	null	0	1	3	null

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 does not mean a cycle. See step 6 where neighbor 1 is visited but is parent, so no cycle.

What happens if the graph is disconnected?

We run DFS from each unvisited node to cover all components. This example shows one component only.

Why does the cycle detection stop immediately after finding a cycle?

Because once a cycle is found (step 9), the function returns true up the call stack to stop further exploration.

Visual Quiz - 3 Questions

Look at the execution table, what is the visited set after step 5?

A [0,1]

B [0,1,3]

C [0,1,3,2]

D [0]

💡 Hint

Check the Visited Set column at step 5 in the execution_table

At which step does the cycle get detected?

A Step 9

B Step 3

C Step 6

D Step 12

💡 Hint

Look at the Cycle Detected column in the execution_table

If the graph had no edge between nodes 2 and 0, what would happen at step 9?

A Error occurs

B Cycle detected anyway

C No cycle detected, DFS continues

D DFS stops immediately

💡 Hint

Step 9 detects cycle because neighbor 0 is visited and not parent; without that edge, no cycle

Concept Snapshot

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

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. The search stops immediately when a cycle is found. The visited set tracks nodes already explored to avoid revisiting. This method works for connected and disconnected graphs by running DFS from each unvisited node.

Practice

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

easy

A. If we find a node with no neighbors, a cycle exists.

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

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

D. If all nodes are visited exactly once, 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 cycle exists.

3. Final Answer:

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

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 more edges than nodes always means cycle
• Confusing cycle detection logic with directed graphs

2. Which of the following is the correct way to represent an undirected graph adjacency list in JavaScript?

easy

A. const graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]};

B. const graph = [[0,1], [1,2], [2,3]];

C. const graph = {0: 1, 1: 2, 2: 3};

D. const graph = [[1, 2], [0], [0], [1]];

Solution

1. Step 1: Understand adjacency list format

   An adjacency list maps each node to an array of its neighbors.

2. Step 2: Check each option

   const graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}; correctly maps nodes to arrays of neighbors. const graph = [[0,1], [1,2], [2,3]]; is edge list, not adjacency list. const graph = {0: 1, 1: 2, 2: 3}; maps nodes to single values, not arrays. const graph = [[1, 2], [0], [0], [1]]; is an array of arrays but connections are not symmetric (node 1 missing neighbor 3).

3. Final Answer:

   const graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]}; -> Option A

4. Quick Check:

   Adjacency list = node keys with neighbor arrays [OK]

Hint: Adjacency list uses node keys with arrays of neighbors [OK]

Common Mistakes:

• Using edge list instead of adjacency list
• Mapping nodes to single values, not arrays
• Using arrays without keys for adjacency list

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

const graph = {0: [1, 2], 1: [0, 3], 2: [0], 3: [1]};

function dfs(node, parent, visited) {
  visited[node] = true;
  for (const neighbor of graph[node]) {
    if (!visited[neighbor]) {
      if (dfs(neighbor, node, visited)) return true;
    } else if (neighbor !== parent) {
      return true;
    }
  }
  return false;
}

const visited = {};
const hasCycle = dfs(0, -1, visited);
console.log(hasCycle);

medium

A. true

B. undefined

C. false

D. TypeError

Solution

1. Step 1: Trace DFS calls and visited nodes

   Start at node 0, mark visited. Visit neighbors 1 and 2. Both lead to nodes without cycles.

2. Step 2: Check for cycle condition

   No neighbor is visited again except parent, so no cycle detected. DFS returns false.

3. Final Answer:

   false -> Option C

4. Quick Check:

   No back edge found = false [OK]

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

Common Mistakes:

• Confusing parent node with cycle neighbor
• Assuming any visited node means cycle
• Not initializing visited properly

4. Find the bug in the following cycle detection code for an undirected graph:

function dfs(node, parent, visited) {
  visited[node] = true;
  for (const neighbor of graph[node]) {
    if (!visited[neighbor]) {
      if (dfs(neighbor, node, visited)) return true;
    } else if (neighbor === parent) {
      return true;
    }
  }
  return false;
}

medium

A. The function should return false inside the for loop.

B. The visited array is not initialized before DFS call.

C. The graph variable is not defined inside the function.

D. The condition 'neighbor === parent' should be 'neighbor !== parent' to detect cycles.

Solution

1. Step 1: Analyze cycle detection condition

   The code returns true if neighbor equals parent, which is incorrect because parent is allowed to be visited.

2. Step 2: Correct condition for cycle detection

   It should return true if neighbor is visited and neighbor is NOT the parent, indicating a cycle.

3. Final Answer:

   The condition 'neighbor === parent' should be 'neighbor !== parent' to detect cycles. -> Option D

4. Quick Check:

   Cycle if visited neighbor not parent [OK]

Hint: Cycle check: visited neighbor must not be parent [OK]

Common Mistakes:

• Returning true when neighbor is parent
• Not initializing visited before DFS
• Returning false too early inside loop

5. Given the undirected graph below, which edges form a cycle?

const graph = {
  0: [1, 2],
  1: [0, 2, 3],
  2: [0, 1, 4],
  3: [1],
  4: [2]
};

Select the correct set of edges that create a cycle.

hard

A. Edges (0-1), (1-2), (2-0)

B. Edges (1-3), (3-4), (4-2)

C. Edges (0-2), (2-4), (4-3)

D. Edges (0-1), (1-3), (3-0)

Solution

1. Step 1: Identify cycles by checking connected edges

   Edges (0-1), (1-2), and (2-0) connect nodes in a triangle, forming a cycle.

2. Step 2: Verify other edges

   Edges involving nodes 3 and 4 do not form cycles as they are connected linearly.

3. Final Answer:

   Edges (0-1), (1-2), (2-0) -> Option A

4. Quick Check:

   Triangle edges form cycle [OK]

Hint: Look for triangle or loop edges to find cycles [OK]

Common Mistakes:

• Assuming linear chains form cycles
• Ignoring the triangle formed by nodes 0,1,2
• Confusing edge directions in undirected graph