Cycle Detection in Undirected Graph in DSA Go

Mental Model

We want to find if there is a loop in the graph where you can start at one node and come back to it by following edges without repeating the same edge twice.

Analogy: Imagine walking through a neighborhood where streets connect houses. If you can start at one house, walk through streets, and return to the same house without retracing your steps, you found a cycle.

Graph:
  1 --- 2
   \   |
    \  |
      3

Edges:
1 -> 2
1 -> 3
2 -> 3

No arrows because undirected edges connect both ways.

Dry Run Walkthrough

Input: Graph with edges: 1-2, 1-3, 2-3

Goal: Detect if the graph contains a cycle

Step 1: Start DFS from node 1, mark node 1 as visited

Visited: {1}
Stack: [1]

Why: We begin traversal from node 1 to explore connected nodes

Step 2: Visit neighbor node 2 from node 1, mark node 2 as visited

Visited: {1, 2}
Stack: [1, 2]

Why: Explore node 2 connected to node 1

Step 3: From node 2, visit neighbor node 3, mark node 3 as visited

Visited: {1, 2, 3}
Stack: [1, 2, 3]

Why: Explore node 3 connected to node 2

Step 4: From node 3, check neighbors: node 1 and node 2 are visited and not parent, cycle detected

Cycle found via edge 3 -> 1 or 3 -> 2

Why: Visiting an already visited node that is not the parent means a cycle exists

Result:

Cycle detected in the graph

Annotated Code

DSA Go

package main

import "fmt"

// Graph represents an undirected graph using adjacency list
type Graph struct {
	adj map[int][]int
}

// NewGraph creates a new graph
func NewGraph() *Graph {
	return &Graph{adj: make(map[int][]int)}
}

// AddEdge adds an undirected edge between u and v
func (g *Graph) AddEdge(u, v int) {
	g.adj[u] = append(g.adj[u], v)
	g.adj[v] = append(g.adj[v], u)
}

// dfsCycle detects cycle using DFS
func (g *Graph) dfsCycle(node, parent int, visited map[int]bool) bool {
	visited[node] = true // mark current node visited
	for _, neighbor := range g.adj[node] {
		if !visited[neighbor] {
			if g.dfsCycle(neighbor, node, visited) {
				return true // cycle found in deeper call
			}
		} else if neighbor != parent {
			return true // visited neighbor not parent means cycle
		}
	}
	return false // no cycle found from this node
}

// HasCycle checks if the graph contains a cycle
func (g *Graph) HasCycle() bool {
	visited := make(map[int]bool)
	for node := range g.adj {
		if !visited[node] {
			if g.dfsCycle(node, -1, visited) {
				return true
			}
		}
	}
	return false
}

func main() {
	g := NewGraph()
	g.AddEdge(1, 2)
	g.AddEdge(1, 3)
	g.AddEdge(2, 3)
	if g.HasCycle() {
		fmt.Println("Cycle detected in the graph")
	} else {
		fmt.Println("No cycle detected")
	}
}

visited[node] = true // mark current node visited

mark node as visited to avoid revisiting

for _, neighbor := range g.adj[node] {

iterate over all neighbors of current node

if !visited[neighbor] {

if neighbor not visited, recurse deeper

if g.dfsCycle(neighbor, node, visited) { return true }

if cycle found in recursion, propagate true

else if neighbor != parent { return true }

if neighbor visited and not parent, cycle detected

for node := range g.adj { if !visited[node] { if g.dfsCycle(node, -1, visited) { return true } } }

check all disconnected components for cycles

Output

Cycle detected in the graph

Complexity Analysis

Time: O(V + E) because we visit each vertex and edge once during DFS

Space: O(V) for the visited map and recursion stack in worst case

vs Alternative: Compared to BFS cycle detection, DFS uses recursion and parent tracking; both have similar time but DFS is simpler to implement for cycle detection in undirected graphs

Edge Cases

Empty graph with no nodes

No cycle detected because no edges exist

DSA Go

for node := range g.adj { if !visited[node] {

Graph with single node and no edges

No cycle detected because no edges to form a loop

DSA Go

for node := range g.adj { if !visited[node] {

Graph with multiple disconnected components

Cycle detection runs on each component separately

DSA Go

for node := range g.adj { if !visited[node] {

When to Use This Pattern

When you see a problem asking if a loop exists in an undirected graph, use DFS with parent tracking to detect cycles efficiently.

Common Mistakes

Mistake: Not checking if the visited neighbor is the parent node, causing false cycle detection
Fix: Add condition to ignore the parent node when checking visited neighbors

Summary

Detects if an undirected graph contains any cycle by DFS traversal.

Use when you need to know if a graph has loops that can cause repeated paths.

The key insight is that visiting a previously visited node that is not the parent means a cycle.

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