Cycle Detection in Directed Graph in DSA Typescript

Mental Model

We want to find if there is a path that starts and ends at the same node following the direction of edges.

Analogy: Imagine a one-way street map where you want to check if you can start driving from a place and come back to it by following the one-way roads without reversing.

A -> B -> C
↑         ↓
└─────────

Dry Run Walkthrough

Input: Graph with edges: A->B, B->C, C->A (cycle exists)

Goal: Detect if the graph contains a cycle

Step 1: Start DFS from node A, mark A as visiting

visiting: {A}, visited: {}

Why: We begin exploring from A to find cycles

Step 2: From A, move to B, mark B as visiting

visiting: {A, B}, visited: {}

Why: Continue exploring neighbors to find cycle

Step 3: From B, move to C, mark C as visiting

visiting: {A, B, C}, visited: {}

Why: Keep going deeper to check for cycle

Step 4: From C, move to A which is already visiting

visiting: {A, B, C}, visited: {}

Why: Finding a node already in visiting means a cycle

Step 5: Cycle detected, stop search

Cycle found

Why: Cycle exists because we returned to a node still being explored

Result:

Cycle found

Annotated Code

DSA Typescript

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

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

  addEdge(src: string, dest: string) {
    if (!this.adjacencyList.has(src)) {
      this.adjacencyList.set(src, []);
    }
    this.adjacencyList.get(src)!.push(dest);
  }

  hasCycle(): boolean {
    const visiting = new Set<string>();
    const visited = new Set<string>();

    const dfs = (node: string): boolean => {
      if (visiting.has(node)) return true; // cycle found
      if (visited.has(node)) return false; // already checked

      visiting.add(node); // mark node as visiting

      for (const neighbor of this.adjacencyList.get(node) || []) {
        if (dfs(neighbor)) return true; // cycle detected in recursion
      }

      visiting.delete(node); // done exploring node
      visited.add(node); // mark node as visited
      return false;
    };

    for (const node of this.adjacencyList.keys()) {
      if (dfs(node)) return true; // cycle found
    }
    return false; // no cycle
  }
}

// Driver code
const graph = new Graph();
graph.addEdge('A', 'B');
graph.addEdge('B', 'C');
graph.addEdge('C', 'A');

console.log(graph.hasCycle() ? 'Cycle found' : 'No cycle');

if (visiting.has(node)) return true; // cycle found

Detect if current node is already in the visiting set, indicating a cycle

if (visited.has(node)) return false; // already checked

Skip nodes already fully explored to avoid repeated work

visiting.add(node); // mark node as visiting

Mark node as currently exploring to track recursion stack

for (const neighbor of this.adjacencyList.get(node) || []) { if (dfs(neighbor)) return true; }

Recursively visit all neighbors to detect cycles

visiting.delete(node); visited.add(node);

Mark node as fully explored after all neighbors checked

for (const node of this.adjacencyList.keys()) { if (dfs(node)) return true; }

Start DFS from each node to cover disconnected parts

Output

Cycle found

Complexity Analysis

Time: O(V + E) because each node and edge is visited once during DFS

Space: O(V) for recursion stack and sets tracking node states

vs Alternative: Compared to naive repeated path checking which can be exponential, DFS with visiting sets is efficient and linear

Edge Cases

Empty graph

Returns no cycle since no nodes exist

DSA Typescript

for (const node of this.adjacencyList.keys()) { if (dfs(node)) return true; }

Graph with no edges

Returns no cycle because no paths to form cycles

DSA Typescript

for (const neighbor of this.adjacencyList.get(node) || []) { if (dfs(neighbor)) return true; }

Graph with self-loop (node points to itself)

Detects cycle immediately when visiting the node again

DSA Typescript

if (visiting.has(node)) return true; // cycle found

When to Use This Pattern

When you see a problem asking if a directed graph has a cycle, use DFS with visiting and visited sets to detect back edges indicating cycles.

Common Mistakes

Mistake: Not distinguishing between visiting and visited sets, causing false cycle detection
Fix: Use separate sets to track nodes currently in recursion (visiting) and fully explored (visited)

Summary

Detects if a directed graph contains a cycle by DFS tracking nodes in recursion stack.

Use when you need to know if a directed graph has cycles to avoid infinite loops or invalid states.

The key insight is that revisiting a node currently being explored means a cycle exists.

Practice

1. What does cycle detection in a directed graph help us find?

easy

A. Whether there is a path that starts and ends at the same node following edge directions

B. The shortest path between two nodes

C. The total number of nodes in the graph

D. The maximum degree of any node

Solution

1. Step 1: Understand cycle in directed graph

   A cycle means a path that starts and ends at the same node following the direction of edges.

2. Step 2: Identify what cycle detection finds

   Cycle detection checks if such a path exists in the graph.

3. Final Answer:

   Whether there is a path that starts and ends at the same node following edge directions -> Option A

4. Quick Check:

   Cycle detection = finding directed loops [OK]

Hint: Cycle means path loops back following edge directions [OK]

Common Mistakes:

• Confusing cycle with shortest path
• Ignoring edge directions
• Thinking cycle means any repeated node without direction

2. Which TypeScript data structure is commonly used to track nodes currently in recursion stack during cycle detection?

easy

A. Queue

B. Array

C. Map

D. Set

Solution

1. Step 1: Identify recursion stack tracking

   We need to quickly check if a node is in the current recursion path.

2. Step 2: Choose data structure for fast membership check

   A Set allows O(1) membership check, ideal for tracking nodes in recursion stack.

3. Final Answer:

   Set -> Option D

4. Quick Check:

   Recursion stack tracking uses Set [OK]

Hint: Use Set for fast membership check in recursion stack [OK]

Common Mistakes:

• Using Array and checking membership with loops (slow)
• Using Queue which is FIFO, not suitable here
• Using Map without key-value need

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

const graph = new Map([
  [1, [2]],
  [2, [3]],
  [3, [1]]
]);

function hasCycle(node: number, visited: Set<number>, recStack: Set<number>): boolean {
  if (!visited.has(node)) {
    visited.add(node);
    recStack.add(node);
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor) && hasCycle(neighbor, visited, recStack)) {
        return true;
      } else if (recStack.has(neighbor)) {
        return true;
      }
    }
  }
  recStack.delete(node);
  return false;
}

console.log(hasCycle(1, new Set(), new Set()));

medium

A. false

B. undefined

C. true

D. Error

Solution

1. Step 1: Analyze graph edges

   Graph edges: 1->2, 2->3, 3->1 form a cycle.

2. Step 2: Trace recursion and cycle detection

   Starting at 1, recursion visits 2, then 3, then back to 1 which is in recursion stack, so returns true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Cycle exists in 1->2->3->1 path [OK]

Hint: Cycle if recursion stack revisits a node [OK]

Common Mistakes:

• Ignoring recursion stack check
• Assuming no cycle if visited is true
• Confusing visited and recursion stack sets

4. Identify the bug in this TypeScript cycle detection function for a directed graph:

function detectCycle(node: number, visited: Set<number>, recStack: Set<number>): boolean {
  if (visited.has(node)) {
    return false;
  }
  visited.add(node);
  recStack.add(node);
  for (const neighbor of graph.get(node) || []) {
    if (detectCycle(neighbor, visited, recStack)) {
      return true;
    }
  }
  recStack.delete(node);
  return false;
}

medium

A. Missing check if neighbor is in recursion stack to detect cycle

B. Visited set is not updated correctly

C. recStack is never cleared

D. Function does not return boolean

Solution

1. Step 1: Review cycle detection logic

   Cycle detection requires checking if neighbor is already in recursion stack to detect back edge.

2. Step 2: Identify missing condition

   The code calls recursion but does not check if neighbor is in recStack, so misses cycles.

3. Final Answer:

   Missing check if neighbor is in recursion stack to detect cycle -> Option A

4. Quick Check:

   Check recStack for back edges to detect cycles [OK]

Hint: Always check recursion stack for back edges [OK]

Common Mistakes:

• Skipping recursion stack membership check
• Confusing visited and recursion stack roles
• Not removing node from recursion stack after recursion

5. Given a directed graph represented as adjacency list:

const graph = new Map([
  [1, [2, 3]],
  [2, [4]],
  [3, [4, 5]],
  [4, [6]],
  [5, [3]],
  [6, []]
]);

Which nodes are part of at least one cycle?

hard

A. [1, 2, 4, 6]

B. [3, 5]

C. [2, 4, 6]

D. [1, 3, 5]

Solution

1. Step 1: Analyze edges for cycles

   Edges: 3->5 and 5->3 form a cycle between nodes 3 and 5.

2. Step 2: Check other nodes

   Nodes 1, 2, 4, 6 do not form cycles as no back edges lead to them.

3. Final Answer:

   [3, 5] -> Option B

4. Quick Check:

   Cycle nodes = 3 and 5 only [OK]

Hint: Look for back edges forming loops between nodes [OK]

Common Mistakes:

• Including nodes not in any cycle
• Missing nodes that form cycles
• Confusing path with cycle