Cycle Detection in Undirected Graph in DSA Typescript

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 around and return to the same bench without retracing your steps backward, there is a loop in the paths.

Graph:
  1 --- 2
  |     |
  4 --- 3

Edges connect nodes. A cycle means you can start at a node and return to it by following edges without going back on the same edge.

Dry Run Walkthrough

Input: Graph with edges: 1-2, 2-3, 3-4, 4-1 (forming a 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 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

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

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

Why: Keep exploring neighbors

Step 5: From node 4, neighbor node 1 is visited and is not parent of 4, cycle detected

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

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

Result:

Cycle detected because node 4 connects back to node 1 which is already visited and not its parent

Annotated Code

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]>;

  constructor() {
    this.adjacencyList = new Map();
  }

  addEdge(u: number, v: number) {
    if (!this.adjacencyList.has(u)) this.adjacencyList.set(u, []);
    if (!this.adjacencyList.has(v)) this.adjacencyList.set(v, []);
    this.adjacencyList.get(u)!.push(v);
    this.adjacencyList.get(v)!.push(u);
  }

  private dfs(node: number, visited: Set<number>, parent: number | null): boolean {
    visited.add(node); // mark current node visited
    for (const neighbor of this.adjacencyList.get(node) || []) {
      if (!visited.has(neighbor)) {
        if (this.dfs(neighbor, visited, node)) return true; // cycle found deeper
      } else if (neighbor !== parent) {
        return true; // visited neighbor not parent means cycle
      }
    }
    return false; // no cycle found from this path
  }

  hasCycle(): boolean {
    const visited = new Set<number>();
    for (const node of this.adjacencyList.keys()) {
      if (!visited.has(node)) {
        if (this.dfs(node, visited, null)) return true; // cycle detected
      }
    }
    return false; // no cycle in any component
  }
}

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

console.log(graph.hasCycle() ? "Cycle detected" : "No cycle detected");

visited.add(node); // mark current node visited

Mark the current node as visited to avoid revisiting

if (!visited.has(neighbor)) { if (this.dfs(neighbor, visited, node)) return true; }

Explore unvisited neighbors recursively to find cycles

else if (neighbor !== parent) { return true; }

If neighbor is visited and not parent, cycle is found

for (const node of this.adjacencyList.keys()) { if (!visited.has(node)) { if (this.dfs(node, visited, null)) return true; } }

Check all graph components for cycles

Output

Cycle detected

Complexity Analysis

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

Space: O(V) for the visited set 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

Empty graph with no nodes

No cycle detected because there are no edges

DSA Typescript

for (const node of this.adjacencyList.keys()) { if (!visited.has(node)) { if (this.dfs(node, visited, null)) return true; } }

Graph with a single node and no edges

No cycle detected because no edges exist

DSA Typescript

for (const node of this.adjacencyList.keys()) { if (!visited.has(node)) { if (this.dfs(node, visited, null)) return true; } }

Graph with multiple disconnected components, one with a cycle

Cycle detected because DFS explores all components

DSA Typescript

for (const node of this.adjacencyList.keys()) { if (!visited.has(node)) { if (this.dfs(node, visited, null)) return true; } }

When to Use This Pattern

When you see a problem asking if a loop exists in an undirected graph, 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 a condition to ignore the parent node when checking visited neighbors

Summary

Detects if an undirected graph contains any cycle by exploring nodes with DFS.

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

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

Practice

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

easy

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

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

C. If all nodes are visited exactly once, there is a cycle.

D. If the graph is disconnected, it contains 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 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 A

4. Quick Check:

   Cycle detection = visit visited node not parent [OK]

Hint: Check visited nodes excluding parent during DFS for cycle [OK]

Common Mistakes:

• Ignoring the parent node check causes false positives.
• Assuming more edges than nodes always means cycle.
• Confusing disconnected graph with cycle presence.

2. Which of the following TypeScript function signatures correctly represents a DFS function for cycle detection in an undirected graph?

easy

A. function dfs(node: number, parent: number, visited: boolean[], graph: number[][]): boolean

B. function dfs(node: string, graph: number[][]): void

C. function dfs(visited: boolean[], graph: number[][]): number

D. function dfs(node: number, graph: number[][]): boolean

Solution

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

   We need current node, parent node, visited array, and graph adjacency list.

2. Step 2: Match function signature with parameters and return type

   function dfs(node: number, parent: number, visited: boolean[], graph: number[][]): boolean has all parameters and returns boolean indicating cycle presence.

3. Final Answer:

   function dfs(node: number, parent: number, visited: boolean[], graph: number[][]): boolean -> Option A

4. Quick Check:

   DFS needs node, parent, visited, graph, returns boolean [OK]

Hint: DFS cycle detection needs parent node parameter [OK]

Common Mistakes:

• Missing parent parameter causes incorrect cycle detection.
• Wrong return type (void instead of boolean).
• Using wrong node type (string instead of number).

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

const graph = [[1,2],[0,2],[0,1,3],[2]];
const visited = new Array(4).fill(false);
function dfs(node: number, parent: number): boolean {
  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;
}
console.log(dfs(0, -1));

medium

A. undefined

B. true

C. false

D. Runtime Error

Solution

1. Step 1: Analyze graph structure and DFS traversal

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

2. Step 2: Trace DFS calls from node 0

   DFS visits 0, then 1, then 2. At 2, neighbor 0 is visited and not parent, cycle detected, returns true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Triangle cycle detected = true [OK]

Hint: Triangle in graph means cycle detected true [OK]

Common Mistakes:

• Ignoring parent check causes false cycle detection.
• Assuming no cycle in triangle graph.
• Confusing return values of DFS function.

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

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

medium

A. Visited array is not updated correctly.

B. Parent parameter is not used in the function.

C. Missing return statement for recursive dfs call result.

D. Graph adjacency list is not passed correctly.

Solution

1. Step 1: Check recursive DFS call handling

   The recursive call dfs(neighbor, node, visited, graph) is made but its boolean result is ignored.

2. Step 2: Identify missing return for cycle detection

   If recursive call returns true (cycle found), it should be returned immediately to propagate detection.

3. Final Answer:

   Missing return statement for recursive dfs call result. -> Option C

4. Quick Check:

   Return recursive DFS result to detect cycle [OK]

Hint: Always return recursive DFS result for cycle detection [OK]

Common Mistakes:

• Ignoring return value of recursive DFS calls.
• Not updating visited array before recursion.
• Misusing parent parameter in cycle check.

5. Given an undirected graph represented as an adjacency list, how can you modify the cycle detection algorithm to also return the nodes forming the cycle?

hard

A. Mark nodes visited twice to identify cycle nodes.

B. Use BFS instead of DFS to find cycles and record nodes.

C. Count edges and nodes; if edges > nodes, return all nodes as cycle.

D. Track the path stack during DFS and return the cycle path when detected.

Solution

1. Step 1: Understand cycle detection with path tracking

   Maintain a stack or list of nodes visited in current DFS path to track traversal.

2. Step 2: Return cycle nodes when back edge found

   When a visited node (not parent) is found, extract nodes from stack forming the cycle path.

3. Final Answer:

   Track the path stack during DFS and return the cycle path when detected. -> Option D

4. Quick Check:

   Use DFS path stack to get cycle nodes [OK]

Hint: Use DFS path stack to capture cycle nodes [OK]

Common Mistakes:

• Using BFS which is less natural for cycle path retrieval.
• Assuming edge count alone identifies cycle nodes.
• Marking nodes visited twice without path context.