Cycle Detection in Directed Graph in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of cycle detection using DFS

What is the output of the following JavaScript code that detects a cycle in a directed graph using DFS?

DSA Javascript

function hasCycle(graph) {
  const visited = new Set();
  const recStack = new Set();

  function dfs(node) {
    if (recStack.has(node)) return true;
    if (visited.has(node)) return false;

    visited.add(node);
    recStack.add(node);

    for (const neighbor of graph[node] || []) {
      if (dfs(neighbor)) return true;
    }

    recStack.delete(node);
    return false;
  }

  for (const node in graph) {
    if (dfs(node)) return true;
  }
  return false;
}

const graph = {
  '0': ['1'],
  '1': ['2'],
  '2': ['0'],
  '3': ['4'],
  '4': []
};

console.log(hasCycle(graph));

A TypeError

B false

C true

D undefined

💡 Hint

Think about whether the graph contains a cycle involving nodes 0, 1, and 2.

The graph has a cycle 0 -> 1 -> 2 -> 0, so the function returns true.

❓ Predict Output

intermediate

Output of cycle detection on acyclic graph

What does the following code print when detecting a cycle in this directed graph?

DSA Javascript

function detectCycle(graph) {
  const visited = new Set();
  const recStack = new Set();

  function dfs(node) {
    if (recStack.has(node)) return true;
    if (visited.has(node)) return false;

    visited.add(node);
    recStack.add(node);

    for (const neighbor of graph[node] || []) {
      if (dfs(neighbor)) return true;
    }

    recStack.delete(node);
    return false;
  }

  for (const node in graph) {
    if (dfs(node)) return true;
  }
  return false;
}

const graph = {
  '0': ['1'],
  '1': ['2'],
  '2': ['3'],
  '3': []
};

console.log(detectCycle(graph));

A ReferenceError

B true

C null

D false

💡 Hint

Check if any node leads back to itself through recursion stack.

The graph is a straight chain with no cycles, so the function returns false.

🔧 Debug

advanced

Identify the error in cycle detection code

What error does the following code produce when run on a graph with a cycle?

DSA Javascript

function checkCycle(graph) {
  const visited = new Set();
  const recStack = new Set();

  function dfs(node) {
    if (recStack.has(node)) return true;
    if (visited.has(node)) return false;

    visited.add(node);
    recStack.add(node);

    for (const neighbor of graph[node] || []) {
      if (dfs(neighbor)) return true;
    }

    recStack.delete(node);
    return false;
  }

  for (const node in graph) {
    if (dfs(node)) return true;
  }
  return false;
}

const graph = {
  '0': ['1'],
  '1': ['2'],
  '2': ['5', '0'],
  '3': []
};

console.log(checkCycle(graph));

A TypeError: Cannot read property 'Symbol.iterator' of undefined

B true

C SyntaxError

D false

💡 Hint

Look at how neighbors are accessed in the for loop.

The code does not handle cases where graph[node] is undefined for a neighbor node. During DFS from '2' to neighbor '5', graph['5'] is undefined, causing TypeError: Cannot read property 'Symbol.iterator' of undefined.

❓ Predict Output

advanced

Output of cycle detection using colors method

What is the output of this code that uses colors (0=unvisited,1=visiting,2=visited) to detect cycles in a directed graph?

DSA Javascript

function detectCycleColors(graph) {
  const colors = {};

  function dfs(node) {
    if (colors[node] === 1) return true;
    if (colors[node] === 2) return false;

    colors[node] = 1;
    for (const neighbor of graph[node] || []) {
      if (dfs(neighbor)) return true;
    }
    colors[node] = 2;
    return false;
  }

  for (const node in graph) {
    if (!colors[node]) {
      if (dfs(node)) return true;
    }
  }
  return false;
}

const graph = {
  '0': ['1'],
  '1': ['2'],
  '2': ['3'],
  '3': ['1']
};

console.log(detectCycleColors(graph));

A false

B true

C undefined

D RangeError

💡 Hint

Check if the colors method detects the cycle 1 -> 2 -> 3 -> 1.

The cycle exists between nodes 1, 2, and 3, so the function returns true.

🧠 Conceptual

expert

Why is recursion stack needed in DFS cycle detection?

In cycle detection for directed graphs using DFS, why do we need to track nodes in the recursion stack separately from visited nodes?

A To detect back edges indicating a cycle by checking if a node is currently in the recursion path

B To avoid visiting nodes multiple times and improve performance

C To store the order of nodes for topological sorting

D To count the total number of nodes in the graph

💡 Hint

Think about what a back edge means in DFS traversal.

The recursion stack tracks nodes currently being explored. If we revisit a node in this stack, it means a cycle exists (back edge).

Practice

1. What is the main purpose of cycle detection in a directed graph?

easy

A. To find if there is a path that starts and ends at the same node following the direction of edges

B. To count the total number of edges in the graph

C. To find the shortest path between two nodes

D. To check if the graph is connected

Solution

1. Step 1: Understand cycle in directed graph

   A cycle means a path that starts and ends at the same node following edge directions.

2. Step 2: Purpose of cycle detection

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

3. Final Answer:

   To find if there is a path that starts and ends at the same node following the direction of edges -> Option A

4. Quick Check:

   Cycle detection = find directed loops [OK]

Hint: Cycle means a directed loop returning to start [OK]

Common Mistakes:

• Confusing cycle detection with counting edges
• Thinking cycle detection finds shortest paths
• Assuming cycle detection checks connectivity

2. Which of the following JavaScript code snippets correctly initializes a graph as an adjacency list for cycle detection?

easy

A. const graph = {0: [1, 2], 1: [2], 2: [0]};

B. const graph = [[0,1], [1,2], [2,0]];

C. const graph = new Map([0, [1, 2], 1, [2], 2, [0]]);

D. const graph = {0 => [1, 2], 1 => [2], 2 => [0]};

Solution

1. Step 1: Check adjacency list syntax in JavaScript

   An adjacency list is an object with keys as nodes and values as arrays of neighbors.

2. Step 2: Validate each option

   const graph = {0: [1, 2], 1: [2], 2: [0]}; uses correct object syntax with arrays as values. const graph = [[0,1], [1,2], [2,0]]; is an edge list, not adjacency list. const graph = new Map([0, [1, 2], 1, [2], 2, [0]]); uses Map incorrectly (missing array of pairs). const graph = {0 => [1, 2], 1 => [2], 2 => [0]}; uses invalid arrow syntax in object keys.

3. Final Answer:

   const graph = {0: [1, 2], 1: [2], 2: [0]}; -> Option A

4. Quick Check:

   Object with arrays = adjacency list [OK]

Hint: Adjacency list uses object keys with array values [OK]

Common Mistakes:

• Using edge list instead of adjacency list
• Incorrect Map initialization syntax
• Using invalid object key syntax

3. Consider the following JavaScript code for cycle detection in a directed graph using DFS:

const graph = {0: [1], 1: [2], 2: [0]};
const visited = new Set();
const recStack = new Set();

function dfs(node) {
  if (recStack.has(node)) return true;
  if (visited.has(node)) return false;
  visited.add(node);
  recStack.add(node);
  for (const neighbor of graph[node] || []) {
    if (dfs(neighbor)) return true;
  }
  recStack.delete(node);
  return false;
}

console.log(dfs(0));

What will be printed when this code runs?

medium

A. false

B. true

C. undefined

D. TypeError

Solution

1. Step 1: Trace DFS calls starting from node 0

   Start at 0: visited={0}, recStack={0}. Visit neighbor 1: visited={0,1}, recStack={0,1}. Visit neighbor 2: visited={0,1,2}, recStack={0,1,2}. Visit neighbor 0 again: recStack has 0, so return true (cycle found).

2. Step 2: Return true up the call stack

   Since cycle detected, dfs returns true and console.log prints true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Cycle detected = true [OK]

Hint: Cycle if node revisited in recursion stack [OK]

Common Mistakes:

• Ignoring recursion stack and returning false
• Confusing visited set with recursion stack
• Expecting false because all nodes visited

4. The following code attempts to detect a cycle in a directed graph but does not work correctly. What is the main error?

const graph = {0: [1], 1: [2], 2: [0]};
const visited = new Set();

function dfs(node) {
  if (visited.has(node)) return false;
  visited.add(node);
  for (const neighbor of graph[node] || []) {
    if (dfs(neighbor)) return true;
  }
  return false;
}

console.log(dfs(0));

medium

A. Visited set is not cleared after recursion

B. Function does not return any value

C. Graph adjacency list is incorrectly defined

D. Missing recursion stack to detect back edges

Solution

1. Step 1: Analyze cycle detection logic

   The code uses only a visited set but no recursion stack to track nodes in current path.

2. Step 2: Understand why recursion stack is needed

   Without recursion stack, the code cannot detect back edges that form cycles, so it misses cycles.

3. Final Answer:

   Missing recursion stack to detect back edges -> Option D

4. Quick Check:

   Recursion stack needed for cycle detection [OK]

Hint: Use recursion stack to detect cycles in DFS [OK]

Common Mistakes:

• Assuming visited set alone detects cycles
• Not tracking nodes in current recursion path
• Confusing visited set clearing with cycle detection

5. You have a directed graph represented as an adjacency list:

const graph = {
  0: [1],
  1: [2, 3],
  2: [4],
  3: [4],
  4: [1]
};

Which of the following modifications will break the cycle detection algorithm that uses DFS with a recursion stack?

hard

A. Starting DFS from node 0 instead of node 4

B. Adding a visited set to track visited nodes

C. Removing the recursion stack and using only a visited set

D. Using an iterative BFS instead of DFS

Solution

1. Step 1: Understand the role of recursion stack in cycle detection

   The recursion stack tracks nodes in the current path to detect cycles (back edges).

2. Step 2: Effect of removing recursion stack

   Without recursion stack, the algorithm cannot detect cycles correctly, even if visited set is used.

3. Step 3: Other options explained

   Adding visited set helps. Starting DFS from different nodes does not break detection if all nodes are visited. Using BFS does not detect cycles in directed graphs reliably.

4. Final Answer:

   Removing the recursion stack and using only a visited set -> Option C

5. Quick Check:

   Recursion stack needed for cycle detection [OK]

Hint: Recursion stack is essential for detecting cycles in DFS [OK]

Common Mistakes:

• Thinking visited set alone detects cycles
• Believing BFS can replace DFS for cycle detection
• Assuming start node affects cycle detection correctness