Cycle Detection in Directed Graph in DSA Typescript - Execution Trace

Concept Flow - Cycle Detection in Directed Graph

Start at each unvisited node

↓

Mark node as visited and in recursion stack

↓

For each neighbor

↓

If neighbor not visited

→Recurse DFS on neighbor

↓

If neighbor in recursion stack

→Cycle detected

↓

After all neighbors checked

↓

Remove node from recursion stack

↓

Continue with next node or end

Start DFS from each node, track visited and recursion stack to detect back edges indicating cycles.

Execution Sample

DSA Typescript

function dfs(node) {
  visited[node] = true;
  recStack[node] = true;
  for (let neighbor of graph[node]) {
    if (!visited[neighbor] && dfs(neighbor)) return true;
    else if (recStack[neighbor]) return true;
  }
  recStack[node] = false;
  return false;
}

DFS visits nodes, marks recursion stack, detects cycle if neighbor is in recursion stack.

Execution Table

Step	Operation	Current Node	Visited Set	Recursion Stack	Action	Cycle Detected	Graph State
1	Start DFS	A	{}	{}	Mark A visited and in stack	No	A->B, B->C, C->A
2	Visit neighbor B	B	{A}	{A}	Mark B visited and in stack	No	A->B, B->C, C->A
3	Visit neighbor C	C	{A,B}	{A,B}	Mark C visited and in stack	No	A->B, B->C, C->A
4	Visit neighbor A	A	{A,B,C}	{A,B,C}	A is in recursion stack	Yes	Cycle detected: A->B->C->A
5	Return true up call stack	C	{A,B,C}	{A,B,C}	Cycle found, stop DFS	Yes	Cycle detected
6	Return true up call stack	B	{A,B,C}	{A,B,C}	Cycle found, stop DFS	Yes	Cycle detected
7	Return true up call stack	A	{A,B,C}	{A,B,C}	Cycle found, stop DFS	Yes	Cycle detected

💡 Cycle detected when visiting node A again while it is in recursion stack

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
visited	{}	{A}	{A,B}	{A,B,C}	{A,B,C}	{A,B,C}
recStack	{}	{A}	{A,B}	{A,B,C}	{A,B,C}	{A,B,C}
currentNode	null	A	B	C	A	A
cycleDetected	false	false	false	false	true	true

Key Moments - 3 Insights

Why do we check if a neighbor is in the recursion stack to detect a cycle?

Because a neighbor in the recursion stack means we found a back edge to an ancestor node in the current DFS path, indicating a cycle (see step 4 in execution_table).

Why do we remove a node from the recursion stack after visiting all neighbors?

Removing the node means we finished exploring all paths from it, so it is no longer in the current DFS path. This prevents false cycle detection later (implied after step 4).

What happens if a node is already visited but not in recursion stack?

It means the node was fully explored in a previous DFS call and no cycle was found through it, so we skip it safely (seen in step 3 when checking neighbors).

Visual Quiz - 3 Questions

Look at the execution_table, what is the recursion stack after step 3?

A {A}

B {A,B,C}

C {A,B}

D {}

💡 Hint

Check the 'Recursion Stack' column at step 3 in execution_table

At which step does the cycle get detected?

A Step 2

B Step 4

C Step 6

D Step 7

💡 Hint

Look for 'Cycle Detected' column showing 'Yes' in execution_table

If the graph had no cycle, what would happen to the recursion stack after DFS finishes on a node?

A It becomes empty for that node's DFS call

B It contains only the last visited node

C It remains with all nodes visited

D It contains nodes not visited yet

💡 Hint

Recall key moment about removing node from recursion stack after visiting neighbors

Concept Snapshot

Cycle Detection in Directed Graph using DFS:
- Use two sets: visited and recursion stack
- Start DFS from each unvisited node
- Mark node visited and add to recursion stack
- For each neighbor:
  - If not visited, recurse DFS
  - If in recursion stack, cycle found
- Remove node from recursion stack after all neighbors
- If cycle found anywhere, graph has a cycle

Full Transcript

Cycle detection in a directed graph uses depth-first search (DFS). We keep track of nodes visited and nodes currently in the recursion stack (the current path). Starting from each unvisited node, we mark it visited and add it to the recursion stack. For each neighbor, if it is not visited, we recurse DFS on it. If the neighbor is already in the recursion stack, it means we found a cycle. After exploring all neighbors, we remove the node from the recursion stack. The process repeats until all nodes are checked or a cycle is found. The execution table shows step-by-step how nodes are visited, recursion stack updated, and cycle detected when a back edge is found.

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