Cycle Detection in Undirected Graph in DSA Go - Execution Trace

Concept Flow - Cycle Detection in Undirected Graph

Start at any node

↓

Mark node as visited

↓

For each neighbor

↓

If neighbor not visited

↓

Recurse DFS on neighbor

↓

If cycle found, return True

↓

If neighbor visited and not parent

↓

Cycle detected! Return True

↓

All neighbors checked, no cycle

↓

Return False

Start DFS from any node, mark visited, explore neighbors. If a visited neighbor is not parent, cycle exists.

Execution Sample

DSA Go

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

DFS checks neighbors; if visited neighbor is not parent, cycle detected.

Execution Table

Step	Operation	Current Node	Visited Nodes	Parent Node	Cycle Detected	Visual State
1	Start DFS at node 0	0	[0]	-1	No	0 | - 1, 2
2	Visit neighbor 1 of node 0	1	[0,1]	0	No	0 - 1 | 2
3	Visit neighbor 3 of node 1	3	[0,1,3]	1	No	0 - 1 - 3 | 2
4	Neighbor 1 of node 3 visited and is parent, continue	3	[0,1,3]	1	No	0 - 1 - 3 | 2
5	All neighbors of 3 checked, backtrack to 1	1	[0,1,3]	0	No	0 - 1 - 3 | 2
6	Visit neighbor 2 of node 0	2	[0,1,3,2]	0	No	0 - 1 - 3 | 2
7	Neighbor 3 of node 2 visited and != parent	2	[0,1,3,2]	0	Yes	Cycle found: 0-1-3-2-0
8	Return True up the call stack	-	[0,1,3,2]	-	Yes	Cycle found: 0-1-3-2-0

💡 Cycle detected at step 7 when visiting neighbor 3 from node 2 which is visited and not parent.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 6	After Step 7	Final
visited	[false,false,false,false]	[true,false,false,false]	[true,true,false,false]	[true,true,false,true]	[true,true,true,true]	[true,true,true,true]	[true,true,true,true]
current_node	-	0	1	3	2	2	-
parent_node	-	-1	0	1	0	0	-
cycle_detected	No	No	No	No	No	Yes	Yes

Key Moments - 3 Insights

Why do we check if the visited neighbor is not the parent node?

Because the parent node is the node we came from, so visiting it again does not mean a cycle. See execution_table step 4 where neighbor 1 is visited but is parent, so no cycle.

What happens if the graph is disconnected?

We start DFS from each unvisited node until all nodes are visited. The example assumes starting at node 0. If disconnected, cycle detection runs on each component.

Why do we return true immediately when a cycle is found?

Because once a cycle is detected, no need to continue searching. See execution_table step 7 where cycle is found and returned up the call stack.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, which nodes are visited?

A [0,1,2]

B [0,1,3]

C [0,1]

D [0]

💡 Hint

Check the 'Visited Nodes' column at step 3 in execution_table.

At which step does the cycle get detected?

A Step 4

B Step 5

C Step 7

D Step 2

💡 Hint

Look at the 'Cycle Detected' column in execution_table.

If we remove the edge between nodes 2 and 3, what happens to cycle detection?

A No cycle detected, DFS finishes without cycle

B Cycle detected at step 7

C Cycle detected earlier at step 4

D DFS will not start

💡 Hint

Without edge 2-3, no back edge to visited node other than parent; see variable_tracker for cycle detection logic.

Concept Snapshot

Cycle Detection in Undirected Graph using DFS:
- Start DFS from any node, mark visited.
- For each neighbor:
  - If not visited, recurse DFS.
  - If visited and not parent, cycle found.
- Return true if cycle detected, else false.
- Parent check avoids false cycle from bidirectional edges.

Full Transcript

Cycle detection in an undirected graph uses depth-first search (DFS). We start from any node, mark it visited, and explore neighbors. If a neighbor is not visited, we recurse DFS on it. If a neighbor is visited and is not the parent node, it means a cycle exists. The parent node check is important because in undirected graphs edges go both ways, so revisiting the parent is normal and not a cycle. The process continues until all nodes are visited or a cycle is found. When a cycle is detected, the function returns true immediately to stop further search. This method works even if the graph is disconnected by running DFS from each unvisited node. The example traced shows a graph with nodes 0,1,2,3 and edges forming a cycle 0-1-3-2-0. The cycle is detected when visiting node 3 from node 2, which is already visited and not the parent. This approach efficiently detects cycles in undirected graphs.

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