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.