Cycle Detection in Undirected Graph in DSA Javascript

Mental Model

We want to find if there is a loop in the graph where you can start at one node and come back to it by following edges without repeating the same edge twice.

Analogy: Imagine walking in a park with paths connecting benches. If you can walk along the paths and return to the same bench without retracing your steps, there is a cycle.

Graph nodes connected by edges:
  1
 / \
2 - 3

Here, 1 connects to 2 and 3, and 2 connects to 3 forming a cycle.

Dry Run Walkthrough

Input: Graph with edges: 1-2, 2-3, 3-1 (triangle cycle)

Goal: Detect if the graph contains a cycle

Step 1: Start DFS from node 1, mark node 1 as visited

Visited: {1}
Stack: [1]

Why: We begin exploring from node 1 to find cycles

Step 2: From node 1, visit neighbor node 2, mark node 2 as visited

Visited: {1, 2}
Stack: [1, 2]

Why: Explore neighbors to find back edges indicating cycles

Step 3: From node 2, visit neighbor node 3, mark node 3 as visited

Visited: {1, 2, 3}
Stack: [1, 2, 3]

Why: Continue exploring deeper neighbors

Step 4: From node 3, check neighbors: node 1 is visited and not parent, cycle detected

Visited: {1, 2, 3}
Stack: [1, 2, 3]
Cycle found

Why: Finding a visited neighbor that is not the parent means a cycle exists

Result:

Cycle detected in the graph

Annotated Code

DSA Javascript

class Graph {
  constructor(vertices) {
    this.V = vertices;
    this.adj = new Array(vertices + 1).fill(null).map(() => []);
  }

  addEdge(u, v) {
    this.adj[u].push(v);
    this.adj[v].push(u);
  }

  isCyclicUtil(v, visited, parent) {
    visited[v] = true; // mark current node visited

    for (const neighbor of this.adj[v]) {
      if (!visited[neighbor]) {
        if (this.isCyclicUtil(neighbor, visited, v)) {
          return true; // cycle found in deeper call
        }
      } else if (neighbor !== parent) {
        return true; // visited neighbor not parent means cycle
      }
    }
    return false; // no cycle found from this node
  }

  isCyclic() {
    const visited = new Array(this.V + 1).fill(false);

    for (let i = 1; i <= this.V; i++) {
      if (!visited[i]) {
        if (this.isCyclicUtil(i, visited, -1)) {
          return true; // cycle detected
        }
      }
    }
    return false; // no cycle in any component
  }
}

// Driver code
const graph = new Graph(3);
graph.addEdge(1, 2);
graph.addEdge(2, 3);
graph.addEdge(3, 1);

if (graph.isCyclic()) {
  console.log("Cycle detected in the graph");
} else {
  console.log("No cycle detected in the graph");
}

visited[v] = true; // mark current node visited

mark current node as visited to avoid revisiting

for (const neighbor of this.adj[v]) {

iterate over all neighbors of current node

if (!visited[neighbor]) {

if neighbor not visited, explore it recursively

if (this.isCyclicUtil(neighbor, visited, v)) {

recursive call to detect cycle deeper in graph

} else if (neighbor !== parent) {

if neighbor visited and not parent, cycle detected

const visited = new Array(this.V + 1).fill(false);

initialize visited array for all nodes

if (!visited[i]) {

start DFS from unvisited nodes to cover disconnected graph

if (this.isCyclicUtil(i, visited, -1)) {

check for cycle starting from node i

Output

Cycle detected in the graph

Complexity Analysis

Time: O(V + E) because we visit each vertex and edge once during DFS

Space: O(V) for the visited array and recursion stack in worst case

vs Alternative: Compared to using union-find which also runs in near O(V + E), DFS is simpler to implement and understand for cycle detection in undirected graphs

Edge Cases

Graph with no edges

No cycle detected because no connections exist

DSA Javascript

if (!visited[i]) {

Graph with a single node and no edges

No cycle detected because no edges to form a cycle

DSA Javascript

if (!visited[i]) {

Disconnected graph with one component having a cycle

Cycle detected because DFS covers all components

DSA Javascript

if (!visited[i]) {

When to Use This Pattern

When you see a problem asking if an undirected graph has loops, use DFS with parent tracking to detect cycles efficiently.

Common Mistakes

Mistake: Not checking if the visited neighbor is the parent node, causing false cycle detection
Fix: Add condition to ignore the parent node when checking visited neighbors

Summary

Detects if an undirected graph contains any cycle by DFS traversal.

Use when you need to know if a graph has loops that can cause repeated paths.

The key insight is that a visited neighbor that is not the parent means a cycle exists.

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