Cycle Detection in Undirected Graph in DSA Javascript - Deep Dive

Overview - Cycle Detection in Undirected Graph

What is it?

Cycle detection in an undirected graph is the process of finding if there is a path that starts and ends at the same vertex without repeating edges. In simple terms, it checks if you can walk around the graph and come back to where you started by following connections. This helps understand the structure of the graph and whether it contains loops. Detecting cycles is important for many applications like network design and deadlock detection.

Why it matters

Without cycle detection, systems might unknowingly have loops that cause problems like infinite loops or deadlocks. For example, in a network, cycles can cause data to circulate endlessly, wasting resources. Detecting cycles helps prevent these issues and ensures the graph behaves as expected. It also helps in understanding if a graph is a tree (which has no cycles) or not, which is important in many algorithms.

Where it fits

Before learning cycle detection, you should understand what graphs are, including vertices and edges, and basic graph traversal methods like Depth-First Search (DFS) or Breadth-First Search (BFS). After mastering cycle detection, you can explore more complex graph algorithms like detecting cycles in directed graphs, finding connected components, or working with weighted graphs.

Mental Model

Core Idea

A cycle exists if during traversal you find a vertex that you have already visited and is not the immediate parent in the path.

Think of it like...

Imagine walking through a neighborhood where streets connect houses. If you can start at one house, walk through streets, and return to the same house without retracing your last step, you found a loop or cycle.

Graph traversal flow:

Start at a node
  ↓
Visit neighbors one by one
  ↓
If neighbor is unvisited -> continue traversal
If neighbor is visited and not parent -> cycle detected
Else -> continue

Example:

  1
 / \
2 - 3

Edges: 1-2, 2-3, 3-1 form a cycle because 3 connects back to 1 which is not its parent.

Build-Up - 6 Steps

1

Foundation

Understanding Undirected Graphs

Concept: Learn what an undirected graph is and how it is represented.

An undirected graph is a set of points called vertices connected by lines called edges. The edges have no direction, meaning you can travel both ways. We can represent it using an adjacency list, where each vertex stores a list of connected vertices. Example adjacency list: { 1: ["2", "3"], 2: ["1", "3"], 3: ["1", "2"] } This means vertex 1 connects to 2 and 3, and so on.

Result

You can visualize and store undirected graphs efficiently for traversal.

Understanding the graph structure and representation is essential before detecting cycles because traversal depends on how connections are stored.

2

Foundation

Basics of Depth-First Search (DFS)

Concept: Learn how DFS explores a graph by going deep before backtracking.

DFS starts at a vertex and explores as far as possible along each branch before backtracking. It uses recursion or a stack to remember where to return. Example DFS from vertex 1: Visit 1 -> Visit 2 -> Visit 3 -> Backtrack This helps visit all vertices connected to the start.

Result

You can traverse all connected vertices in a graph systematically.

DFS is the main tool for cycle detection because it tracks the path and helps identify revisits to vertices.

3

Intermediate

Detecting Cycles Using DFS and Parent Tracking

🤔Before reading on: Do you think revisiting any visited vertex always means a cycle? Commit to yes or no.

Concept: Introduce the idea of tracking the parent vertex to avoid false cycle detection.

When DFS visits a neighbor, if it is already visited and is not the parent vertex (the one we came from), it means a cycle exists. Example code snippet: function dfs(node, parent) { visited[node] = true; for (const neighbor of graph[node]) { if (!visited[neighbor]) { if (dfs(neighbor, node)) return true; } else if (neighbor !== parent) { return true; // cycle found } } return false; } This prevents counting the edge back to the parent as a cycle.

Result

You can correctly detect cycles without false positives caused by back edges to parents.

Knowing to track the parent vertex is crucial to distinguish real cycles from normal backtracking in undirected graphs.

4

Intermediate

Implementing Full Cycle Detection in JavaScript

🤔Before reading on: Should cycle detection check all vertices or just one? Commit to your answer.

Concept: Cycle detection must check all disconnected parts of the graph to be complete.

Graphs can have multiple disconnected parts. We must run DFS from every unvisited vertex to detect cycles anywhere. Complete code: const graph = { 1: ["2", "3"], 2: ["1", "3"], 3: ["1", "2"], 4: ["5"], 5: ["4"] }; const visited = {}; function dfs(node, parent) { visited[node] = true; for (const neighbor of graph[node]) { if (!visited[neighbor]) { if (dfs(neighbor, node)) return true; } else if (neighbor !== parent) { return true; } } return false; } function hasCycle(graph) { for (const node in graph) { if (!visited[node]) { if (dfs(node, null)) return true; } } return false; } console.log(hasCycle(graph)); // true

Result

The function returns true if any cycle exists in any part of the graph.

Checking all components ensures no cycle is missed in disconnected graphs.

5

Advanced

Time and Space Complexity Analysis

🤔Before reading on: Do you think cycle detection runs faster or slower than visiting all nodes once? Commit to your answer.

Concept: Analyze how efficient the cycle detection algorithm is in terms of time and memory.

The DFS-based cycle detection visits each vertex and edge once. For a graph with V vertices and E edges: - Time complexity: O(V + E) - Space complexity: O(V) for the visited map and recursion stack This means the algorithm is efficient even for large graphs. Understanding complexity helps predict performance and optimize code.

Result

Cycle detection runs in linear time relative to graph size, making it practical for large graphs.

Knowing complexity prevents overestimating the cost and helps choose cycle detection for real applications.

6

Expert

Subtlety: Handling Parallel Edges and Self-Loops

🤔Before reading on: Do parallel edges or self-loops always cause cycle detection to fail? Commit to yes or no.

Concept: Understand how special cases like multiple edges between same vertices or edges from a vertex to itself affect detection.

Parallel edges (multiple edges between same two vertices) and self-loops (edge from a vertex to itself) are special cases: - Self-loop is always a cycle. - Parallel edges can cause false positives if not handled carefully. To handle these: - Check if neighbor equals current node (self-loop) -> cycle. - For parallel edges, treat each edge separately but parent check still applies. Example: function dfs(node, parent) { visited[node] = true; for (const neighbor of graph[node]) { if (neighbor === node) return true; // self-loop if (!visited[neighbor]) { if (dfs(neighbor, node)) return true; } else if (neighbor !== parent) { return true; // cycle } } return false; }

Result

Cycle detection correctly identifies cycles even with self-loops and parallel edges.

Recognizing these edge cases prevents subtle bugs in cycle detection implementations.

Under the Hood

Cycle detection uses DFS to explore the graph deeply, marking nodes as visited. When it encounters a visited node that is not the immediate parent, it means there is an alternate path back to that node, forming a cycle. The parent tracking prevents mistaking the bidirectional edge back to the previous node as a cycle. Internally, the recursion stack keeps track of the current path, and the visited set prevents infinite loops.

Why designed this way?

This method was chosen because DFS naturally explores paths deeply, making it easy to detect revisits. Parent tracking solves the problem of undirected edges being two-way, which could falsely indicate cycles. Alternatives like BFS are possible but less intuitive for cycle detection in undirected graphs. The design balances simplicity, efficiency, and correctness.

DFS Cycle Detection Flow:

┌─────────────┐
│ Start Node  │
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ Mark Visited│
└──────┬──────┘
       │
       ▼
┌─────────────┐
│ For each    │
│ neighbor:   │
└──────┬──────┘
       │
       ▼
┌─────────────┐       ┌───────────────┐
│ If neighbor │──────▶│ Not visited?  │
│ is visited  │       └──────┬────────┘
│ and not     │              │
│ parent?     │              ▼
└──────┬──────┘       ┌─────────────┐
       │              │ DFS(neighbor│
       │              │ , current) │
       │              └──────┬──────┘
       │                     │
       │                     ▼
       │              ┌─────────────┐
       │              │ Cycle found │
       │              └─────────────┘
       ▼
┌─────────────┐
│ Continue or │
│ Backtrack   │
└─────────────┘

Myth Busters - 3 Common Misconceptions

Quick: Does revisiting any visited node always mean a cycle? Commit to yes or no.

Common Belief: If DFS visits a node that is already visited, it means there is a cycle.

Reality: In undirected graphs, revisiting the immediate parent node is normal and does not indicate a cycle. Only revisiting a visited node that is not the parent means a cycle.

Why it matters: Without this understanding, many false cycles are reported, causing confusion and incorrect results.

Quick: Should cycle detection run from just one node or all nodes? Commit to your answer.

Common Belief: Running cycle detection from any one node is enough to find all cycles in the graph.

Reality: If the graph has disconnected parts, cycles in other parts will be missed unless DFS runs from every unvisited node.

Why it matters: Missing cycles in disconnected components can lead to wrong assumptions about graph structure.

Quick: Do self-loops and parallel edges always cause cycle detection to fail? Commit to yes or no.

Common Belief: Cycle detection algorithms ignore self-loops and parallel edges as they are rare and unimportant.

Reality: Self-loops are cycles by definition and must be detected. Parallel edges can cause cycles and must be handled carefully.

Why it matters: Ignoring these cases can cause bugs in networks or graphs where such edges exist.

Expert Zone

1

Cycle detection in undirected graphs relies heavily on parent tracking to avoid false positives due to bidirectional edges.

2

The recursion stack in DFS implicitly tracks the current path, which is why revisiting a non-parent node indicates a cycle.

3

Handling special edges like self-loops requires explicit checks, as they break the usual parent-child assumptions.

When NOT to use

This approach is not suitable for directed graphs, where cycle detection requires different algorithms like Tarjan's or using recursion stack tracking. For very large graphs, iterative DFS or Union-Find methods may be preferred for performance or memory reasons.

Production Patterns

In real systems, cycle detection is used in network topology validation, deadlock detection in operating systems, and verifying data structure integrity. Union-Find (Disjoint Set) is often used for dynamic graphs where edges are added over time, while DFS is preferred for static graphs.

Connections

Union-Find Data Structure

Alternative method for cycle detection in undirected graphs using sets.

Understanding Union-Find helps detect cycles efficiently when edges are added dynamically, complementing DFS-based detection.

Deadlock Detection in Operating Systems

Cycle detection in resource allocation graphs to find deadlocks.

Knowing cycle detection in graphs helps understand how operating systems detect processes stuck waiting for each other.

Electrical Circuit Loops

Cycles in graphs correspond to loops in circuits where current can flow in a closed path.

Recognizing cycles in graphs is analogous to identifying loops in circuits, which is crucial for analyzing circuit behavior.

Common Pitfalls

#1 Mistaking the edge back to the parent as a cycle.

Wrong approach:

if (visited[neighbor]) { return true; } // no parent check

Correct approach:

if (visited[neighbor] && neighbor !== parent) { return true; }

Root cause:

Not tracking the parent node causes false cycle detection on bidirectional edges.

#2 Running DFS cycle detection from only one node in a disconnected graph.

Wrong approach:

function hasCycle(graph) {
return dfs(startNode, null);
}

Correct approach:

function hasCycle(graph) {
for (const node in graph) {
if (!visited[node]) {
if (dfs(node, null)) return true;
}
}
return false;
}

Root cause:

Assuming the graph is connected leads to missing cycles in other components.

#3 Ignoring self-loops and parallel edges in cycle detection.

Wrong approach:

for (const neighbor of graph[node]) {
if (visited[neighbor] && neighbor !== parent) return true;
}

Correct approach:

for (const neighbor of graph[node]) {
if (neighbor === node) return true; // self-loop
if (visited[neighbor] && neighbor !== parent) return true;
}

Root cause:

Not explicitly checking for self-loops causes missed cycles.

Key Takeaways

Cycle detection in undirected graphs uses DFS with parent tracking to identify loops accurately.

Revisiting a visited node that is not the parent indicates a cycle; revisiting the parent does not.

Cycle detection must run on all disconnected parts of the graph to be complete.

Special cases like self-loops and parallel edges require explicit handling to avoid bugs.

Understanding cycle detection is foundational for many real-world problems like network design and deadlock detection.

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