Cycle Detection in Undirected Graph in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a cycle in an undirected graph?

A cycle is a path that starts and ends at the same vertex, with all edges and vertices distinct except the first and last vertex.

beginner

Which data structure is commonly used to detect cycles in an undirected graph?

Depth-First Search (DFS) is commonly used to detect cycles by checking if a visited vertex is encountered again and is not the parent of the current vertex.

intermediate

In cycle detection using DFS, why do we keep track of the parent node?

To avoid falsely detecting a cycle when revisiting the immediate parent node, since the parent is connected to the current node by an edge.

intermediate

What is the time complexity of cycle detection in an undirected graph using DFS?

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges, because each vertex and edge is visited once.

advanced

How does the Union-Find (Disjoint Set) data structure help in cycle detection?

Union-Find helps detect cycles by grouping connected vertices. If two vertices of an edge belong to the same group, adding that edge creates a cycle.

What indicates a cycle during DFS in an undirected graph?

A Visiting a vertex for the first time

B No edges left to explore

C Visiting the parent vertex again

D Visiting a vertex that is already visited and is not the parent

A cycle is detected if DFS visits a vertex that has already been visited and is not the immediate parent.

What is the role of the 'parent' parameter in DFS cycle detection?

A To avoid counting the edge back to the parent as a cycle

B To mark the starting vertex

C To store the depth of the vertex

D To keep track of visited vertices

The parent parameter helps avoid false cycle detection by ignoring the edge back to the parent.

Which of these is NOT a valid method for cycle detection in undirected graphs?

A Topological Sort

B Breadth-First Search (BFS) with parent tracking

C Union-Find (Disjoint Set)

D Depth-First Search (DFS)

Topological Sort is used for cycle detection in directed graphs, not undirected graphs.

What is the initial state of the 'visited' array in DFS cycle detection?

A All vertices marked visited

B Random vertices visited

C All vertices marked unvisited

D Only the root vertex visited

Initially, all vertices are unvisited before DFS starts.

In Union-Find, what does it mean if two vertices have the same root?

A They belong to different sets

B They belong to the same set, indicating a cycle if connected by an edge

C They are disconnected

D They are isolated vertices

Same root means vertices are in the same set; connecting them again forms a cycle.

Explain how DFS can be used to detect a cycle in an undirected graph.

Think about revisiting nodes and how parent helps avoid false positives.

Describe how the Union-Find data structure detects cycles in an undirected graph.

Focus on grouping vertices and checking if an edge connects vertices in the same group.

Practice

1. What is the main idea behind detecting a cycle in an undirected graph using DFS?

easy

A. If we visit a node that is already visited and is not the parent, a cycle exists.

B. If the graph has more edges than nodes, it always has a cycle.

C. If all nodes are visited exactly once, there is a cycle.

D. If the graph is disconnected, it contains a cycle.

Solution

1. Step 1: Understand DFS traversal in undirected graph

   DFS visits nodes and tracks the parent node to avoid false cycle detection.

2. Step 2: Detect cycle condition

   If during DFS, a visited node is found that is not the parent, it means a back edge exists, indicating a cycle.

3. Final Answer:

   If we visit a node that is already visited and is not the parent, a cycle exists. -> Option A

4. Quick Check:

   Cycle detection = visit visited node not parent [OK]

Hint: Check visited nodes excluding parent during DFS for cycle [OK]

Common Mistakes:

• Ignoring the parent node check causes false positives.
• Assuming more edges than nodes always means cycle.
• Confusing disconnected graph with cycle presence.

2. Which of the following TypeScript function signatures correctly represents a DFS function for cycle detection in an undirected graph?

easy

A. function dfs(node: number, parent: number, visited: boolean[], graph: number[][]): boolean

B. function dfs(node: string, graph: number[][]): void

C. function dfs(visited: boolean[], graph: number[][]): number

D. function dfs(node: number, graph: number[][]): boolean

Solution

1. Step 1: Identify required parameters for DFS cycle detection

   We need current node, parent node, visited array, and graph adjacency list.

2. Step 2: Match function signature with parameters and return type

   function dfs(node: number, parent: number, visited: boolean[], graph: number[][]): boolean has all parameters and returns boolean indicating cycle presence.

3. Final Answer:

   function dfs(node: number, parent: number, visited: boolean[], graph: number[][]): boolean -> Option A

4. Quick Check:

   DFS needs node, parent, visited, graph, returns boolean [OK]

Hint: DFS cycle detection needs parent node parameter [OK]

Common Mistakes:

• Missing parent parameter causes incorrect cycle detection.
• Wrong return type (void instead of boolean).
• Using wrong node type (string instead of number).

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

const graph = [[1,2],[0,2],[0,1,3],[2]];
const visited = new Array(4).fill(false);
function dfs(node: number, parent: number): boolean {
  visited[node] = true;
  for (const neighbor of graph[node]) {
    if (!visited[neighbor]) {
      if (dfs(neighbor, node)) return true;
    } else if (neighbor !== parent) {
      return true;
    }
  }
  return false;
}
console.log(dfs(0, -1));

medium

A. undefined

B. true

C. false

D. Runtime Error

Solution

1. Step 1: Analyze graph structure and DFS traversal

   Graph edges: 0-1, 0-2, 1-2, 2-3. Nodes 0,1,2 form a triangle (cycle).

2. Step 2: Trace DFS calls from node 0

   DFS visits 0, then 1, then 2. At 2, neighbor 0 is visited and not parent, cycle detected, returns true.

3. Final Answer:

   true -> Option B

4. Quick Check:

   Triangle cycle detected = true [OK]

Hint: Triangle in graph means cycle detected true [OK]

Common Mistakes:

• Ignoring parent check causes false cycle detection.
• Assuming no cycle in triangle graph.
• Confusing return values of DFS function.

4. Identify the bug in the following TypeScript code for cycle detection in an undirected graph:

function dfs(node: number, parent: number, visited: boolean[], graph: number[][]): boolean {
  visited[node] = true;
  for (const neighbor of graph[node]) {
    if (!visited[neighbor]) {
      dfs(neighbor, node, visited, graph);
    } else if (neighbor !== parent) {
      return true;
    }
  }
  return false;
}

medium

A. Visited array is not updated correctly.

B. Parent parameter is not used in the function.

C. Missing return statement for recursive dfs call result.

D. Graph adjacency list is not passed correctly.

Solution

1. Step 1: Check recursive DFS call handling

   The recursive call dfs(neighbor, node, visited, graph) is made but its boolean result is ignored.

2. Step 2: Identify missing return for cycle detection

   If recursive call returns true (cycle found), it should be returned immediately to propagate detection.

3. Final Answer:

   Missing return statement for recursive dfs call result. -> Option C

4. Quick Check:

   Return recursive DFS result to detect cycle [OK]

Hint: Always return recursive DFS result for cycle detection [OK]

Common Mistakes:

• Ignoring return value of recursive DFS calls.
• Not updating visited array before recursion.
• Misusing parent parameter in cycle check.

5. Given an undirected graph represented as an adjacency list, how can you modify the cycle detection algorithm to also return the nodes forming the cycle?

hard

A. Mark nodes visited twice to identify cycle nodes.

B. Use BFS instead of DFS to find cycles and record nodes.

C. Count edges and nodes; if edges > nodes, return all nodes as cycle.

D. Track the path stack during DFS and return the cycle path when detected.

Solution

1. Step 1: Understand cycle detection with path tracking

   Maintain a stack or list of nodes visited in current DFS path to track traversal.

2. Step 2: Return cycle nodes when back edge found

   When a visited node (not parent) is found, extract nodes from stack forming the cycle path.

3. Final Answer:

   Track the path stack during DFS and return the cycle path when detected. -> Option D

4. Quick Check:

   Use DFS path stack to get cycle nodes [OK]

Hint: Use DFS path stack to capture cycle nodes [OK]

Common Mistakes:

• Using BFS which is less natural for cycle path retrieval.
• Assuming edge count alone identifies cycle nodes.
• Marking nodes visited twice without path context.