Cycle Detection in Undirected Graph in DSA Go - 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 by the edge we came from.

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 checking if two vertices belong to the same set before union; if yes, adding an edge creates a cycle.

What indicates a cycle during DFS traversal in an undirected graph?

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

B Visiting a vertex for the first time

C Reaching a vertex with no neighbors

D Visiting the parent vertex again

A cycle is detected if a visited vertex is found again during DFS and it is not the parent of the current vertex.

Which of these is NOT a valid method to detect cycles in an undirected graph?

A Breadth-First Search with parent tracking

B Sorting vertices by degree

C Union-Find (Disjoint Set) data structure

D Depth-First Search with parent tracking

Sorting vertices by degree does not help detect cycles in an undirected graph.

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

A To avoid counting the edge back to the immediate predecessor as a cycle

B To mark the starting vertex

C To store the depth of the vertex

D To count the number of cycles

The parent parameter helps avoid false positives by ignoring the edge back to the immediate predecessor.

What is the initial step in Union-Find cycle detection when adding an edge?

A Sort the vertices

B Add the edge without checks

C Check if both vertices belong to the same set

D Remove one vertex

Before adding an edge, Union-Find checks if both vertices are in the same set to detect a cycle.

What is the output after detecting a cycle in an undirected graph?

A Number of edges

B List of all vertices

C Graph with no edges

D True or indication that a cycle exists

Cycle detection returns a boolean or indication that a cycle exists in the graph.

Explain how Depth-First Search can be used to detect a cycle in an undirected graph.

Think about revisiting nodes and how parent helps.

Describe how the Union-Find data structure detects cycles when edges are added.

Focus on sets and merging.

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 all nodes are visited exactly once, there is a cycle.

C. If the graph has more edges than nodes, it always has 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 keeps track of the parent node to avoid false cycle detection.

2. Step 2: Detect cycle condition

   If a visited node is found again and it is not the parent, it means a cycle exists.

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 in undirected graph = visit visited node not parent [OK]

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

Common Mistakes:

• Ignoring parent node when checking visited nodes
• Assuming disconnected graph always has cycles
• Confusing cycle detection with number of edges

2. Which of the following Go code snippets correctly initializes an adjacency list for an undirected graph with 3 nodes?

easy

A. graph := make([][]int, 3)
graph[0] = []int{1, 2}
graph[1] = []int{0}
graph[2] = []int{0}

B. graph := make(map[int]int)
graph[0] = 1
graph[1] = 2
graph[2] = 0

C. graph := [][]int{{1, 2}, 0, {0}}

D. graph := make([]int, 3)
graph[0] = 1
graph[1] = 2
graph[2] = 0

Solution

1. Step 1: Understand adjacency list representation

   An adjacency list for an undirected graph is a slice of slices where each index holds neighbors.

2. Step 2: Check code correctness

   graph := make([][]int, 3) graph[0] = []int{1, 2} graph[1] = []int{0} graph[2] = []int{0} correctly creates a slice of slices and assigns neighbors for each node.

3. Final Answer:

   graph := make([][]int, 3) graph[0] = []int{1, 2} graph[1] = []int{0} graph[2] = []int{0} -> Option A

4. Quick Check:

   Adjacency list = slice of slices with neighbors [OK]

Hint: Use [][]int for adjacency list, not map or []int [OK]

Common Mistakes:

• Using map[int]int instead of map[int][]int or [][]int
• Using []int instead of [][]int for adjacency list
• Not initializing slices before assignment

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

package main
import "fmt"

func dfs(node, parent int, graph [][]int, visited []bool) bool {
    visited[node] = true
    for _, neighbor := range graph[node] {
        if !visited[neighbor] {
            if dfs(neighbor, node, graph, visited) {
                return true
            }
        } else if neighbor != parent {
            return true
        }
    }
    return false
}

func main() {
    graph := [][]int{{1, 2}, {0, 2}, {0, 1}}
    visited := make([]bool, 3)
    if dfs(0, -1, graph, visited) {
        fmt.Println("Cycle detected")
    } else {
        fmt.Println("No cycle")
    }
}

medium

A. Compilation error

B. No cycle

C. Runtime panic

D. Cycle detected

Solution

1. Step 1: Analyze graph structure

   The graph has edges: 0-1, 0-2, and 1-2 forming a triangle, which is a cycle.

2. Step 2: Trace DFS cycle detection

   DFS from node 0 visits 1 and 2; when visiting 2 from 1, it finds 0 already visited and not parent, detecting a cycle.

3. Final Answer:

   Cycle detected -> Option D

4. Quick Check:

   Triangle graph = cycle detected [OK]

Hint: Triangle edges always form a cycle [OK]

Common Mistakes:

• Ignoring the neighbor != parent condition
• Assuming no cycle if start node has no parent
• Misreading graph edges

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

func dfs(node int, graph [][]int, visited []bool) bool {
    visited[node] = true
    for _, neighbor := range graph[node] {
        if !visited[neighbor] {
            if dfs(neighbor, graph, visited) {
                return true
            }
        } else {
            return true
        }
    }
    return false
}

medium

A. Visited array is not initialized

B. Missing parent parameter to avoid false cycle detection

C. Graph adjacency list is incorrectly defined

D. DFS function should return void, not bool

Solution

1. Step 1: Understand DFS cycle detection logic

   In undirected graphs, revisiting a visited node is not always a cycle if it is the parent node.

2. Step 2: Identify missing parent parameter

   The code lacks a parent parameter to exclude the immediate parent from cycle detection, causing false positives.

3. Final Answer:

   Missing parent parameter to avoid false cycle detection -> Option B

4. Quick Check:

   Parent parameter needed to avoid false cycle [OK]

Hint: Always pass parent node in DFS for undirected graphs [OK]

Common Mistakes:

• Not passing parent node in DFS
• Returning true on any visited neighbor
• Confusing directed and undirected cycle detection

5. Given an undirected graph represented as adjacency list:

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

How many connected components does the graph have and does it contain a cycle?

hard

A. 2 connected components, no cycle

B. 1 connected component, no cycle

C. 1 connected component, contains a cycle

D. 2 connected components, contains a cycle

Solution

1. Step 1: Count connected components

   All nodes 0 to 4 are reachable from each other, so only 1 connected component exists.

2. Step 2: Detect cycle in the graph

   Edges form a cycle among nodes 1, 2, 3 (triangle), so the graph contains a cycle.

3. Final Answer:

   1 connected component, contains a cycle -> Option C

4. Quick Check:

   Single connected graph with triangle cycle [OK]

Hint: Check connectivity then look for triangle cycles [OK]

Common Mistakes:

• Counting connected components incorrectly
• Missing cycle formed by nodes 1, 2, 3
• Assuming no cycle if graph is connected