Cycle Detection in Undirected Graph in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of DFS-based cycle detection in undirected graph

What is the output of the following TypeScript code that detects a cycle in an undirected graph using DFS?

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]> = 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);
  }

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

    const dfs = (node: number, parent: number): boolean => {
      visited.add(node);
      for (const neighbor of this.adjacencyList.get(node) || []) {
        if (!visited.has(neighbor)) {
          if (dfs(neighbor, node)) return true;
        } else if (neighbor !== parent) {
          return true;
        }
      }
      return false;
    };

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

const g = new Graph();
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.addEdge(4, 2);
console.log(g.hasCycle());

A true

B false

C undefined

D SyntaxError

💡 Hint

Think about whether the graph has a loop formed by edges.

The graph edges form a cycle: 2 → 3 → 4 → 2. The DFS detects this cycle and returns true.

🧠 Conceptual

intermediate

Cycle detection condition in undirected graph DFS

In DFS cycle detection for an undirected graph, which condition correctly identifies a cycle?

A If a neighbor is visited and is the parent of the current node, a cycle exists.

B If a visited neighbor is not the parent of the current node, a cycle exists.

C If a neighbor is unvisited, it means a cycle exists.

D If the current node has no neighbors, a cycle exists.

💡 Hint

Think about how back edges indicate cycles in undirected graphs.

In undirected graphs, a cycle is detected if during DFS we find a neighbor that is already visited and is not the parent node. This means we found a back edge.

🔧 Debug

advanced

Identify the error in cycle detection code

What error will this TypeScript code produce when detecting cycles in an undirected graph?

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]> = 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);
  }

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

    const dfs = (node: number): boolean => {
      visited.add(node);
      for (const neighbor of this.adjacencyList.get(node) || []) {
        if (!visited.has(neighbor)) {
          if (dfs(neighbor)) return true;
        } else {
          return true;
        }
      }
      return false;
    };

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

A The code will incorrectly detect cycles due to missing parent tracking.

B The code will cause a syntax error due to missing return statements.

C The code will never detect any cycle because it returns false always.

D The code will cause a runtime error due to undefined adjacency list.

💡 Hint

Check how the parent node is handled in DFS.

The code does not track the parent node, so it treats the immediate parent as a cycle, causing false positives.

❓ Predict Output

advanced

Output of BFS-based cycle detection in undirected graph

What is the output of this TypeScript code that detects a cycle in an undirected graph using BFS?

DSA Typescript

class Graph {
  adjacencyList: Map<number, number[]> = 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);
  }

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

    for (const start of this.adjacencyList.keys()) {
      if (!visited.has(start)) {
        const queue: Array<[number, number]> = [[start, -1]];
        visited.add(start);

        while (queue.length > 0) {
          const [node, parent] = queue.shift()!;
          for (const neighbor of this.adjacencyList.get(node) || []) {
            if (!visited.has(neighbor)) {
              visited.add(neighbor);
              queue.push([neighbor, node]);
            } else if (neighbor !== parent) {
              return true;
            }
          }
        }
      }
    }
    return false;
  }
}

const g = new Graph();
g.addEdge(1, 2);
g.addEdge(2, 3);
g.addEdge(3, 4);
g.addEdge(4, 5);
console.log(g.hasCycle());

A true

B TypeError

C false

D undefined

💡 Hint

Check if the graph edges form any cycle.

The graph is a simple chain 1-2-3-4-5 with no cycles, so BFS cycle detection returns false.

🧠 Conceptual

expert

Why is parent tracking necessary in undirected graph cycle detection?

Why must we track the parent node when detecting cycles in an undirected graph using DFS or BFS?

A To detect cycles only in directed graphs.

B To improve the runtime complexity from exponential to linear.

C To ensure all nodes are visited exactly once.

D To avoid falsely detecting the immediate parent as a cycle neighbor.

💡 Hint

Think about the bidirectional edges in undirected graphs.

In undirected graphs, edges go both ways. Without parent tracking, the algorithm treats the edge back to the parent as a cycle, causing false positives.