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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of cycle detection on a simple graph

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

DSA Go

package main

import "fmt"

type Graph struct {
	adj map[int][]int
}

func (g *Graph) addEdge(u, v int) {
	g.adj[u] = append(g.adj[u], v)
	g.adj[v] = append(g.adj[v], u)
}

func (g *Graph) dfs(v, parent int, visited map[int]bool) bool {
	visited[v] = true
	for _, neighbor := range g.adj[v] {
		if !visited[neighbor] {
			if g.dfs(neighbor, v, visited) {
				return true
			}
		} else if neighbor != parent {
			return true
		}
	}
	return false
}

func (g *Graph) hasCycle() bool {
	visited := make(map[int]bool)
	for vertex := range g.adj {
		if !visited[vertex] {
			if g.dfs(vertex, -1, visited) {
				return true
			}
		}
	}
	return false
}

func main() {
	g := Graph{adj: make(map[int][]int)}
	g.addEdge(1, 2)
	g.addEdge(2, 3)
	g.addEdge(3, 4)
	g.addEdge(4, 2)
	fmt.Println(g.hasCycle())
}

A Compilation error

B false

C true

D Runtime panic

💡 Hint

Look for back edges in DFS that are not the parent node.

The graph contains a cycle formed by edges 2-3-4-2. The DFS detects this cycle and returns true.

❓ Predict Output

intermediate

Cycle detection output on a tree graph

What will the output be when running this Go code that checks for cycles in an undirected graph structured as a tree?

DSA Go

package main

import "fmt"

type Graph struct {
	adj map[int][]int
}

func (g *Graph) addEdge(u, v int) {
	g.adj[u] = append(g.adj[u], v)
	g.adj[v] = append(g.adj[v], u)
}

func (g *Graph) dfs(v, parent int, visited map[int]bool) bool {
	visited[v] = true
	for _, neighbor := range g.adj[v] {
		if !visited[neighbor] {
			if g.dfs(neighbor, v, visited) {
				return true
			}
		} else if neighbor != parent {
			return true
		}
	}
	return false
}

func (g *Graph) hasCycle() bool {
	visited := make(map[int]bool)
	for vertex := range g.adj {
		if !visited[vertex] {
			if g.dfs(vertex, -1, visited) {
				return true
			}
		}
	}
	return false
}

func main() {
	g := Graph{adj: make(map[int][]int)}
	g.addEdge(1, 2)
	g.addEdge(1, 3)
	g.addEdge(3, 4)
	g.addEdge(3, 5)
	fmt.Println(g.hasCycle())
}

A false

B true

C Compilation error

D Runtime panic

💡 Hint

A tree has no cycles.

The graph is a tree structure with no cycles, so the function returns false.

🔧 Debug

advanced

Identify the error causing incorrect cycle detection

The following Go code is intended to detect cycles in an undirected graph but incorrectly returns true even when no cycle exists. What is the bug?

DSA Go

package main

import "fmt"

type Graph struct {
	adj map[int][]int
}

func (g *Graph) addEdge(u, v int) {
	g.adj[u] = append(g.adj[u], v)
	g.adj[v] = append(g.adj[v], u)
}

func (g *Graph) dfs(v int, visited map[int]bool) bool {
	visited[v] = true
	for _, neighbor := range g.adj[v] {
		if !visited[neighbor] {
			if g.dfs(neighbor, visited) {
				return true
			}
		} else {
			return true
		}
	}
	return false
}

func (g *Graph) hasCycle() bool {
	visited := make(map[int]bool)
	for vertex := range g.adj {
		if !visited[vertex] {
			if g.dfs(vertex, visited) {
				return true
			}
		}
	}
	return false
}

func main() {
	g := Graph{adj: make(map[int][]int)}
	g.addEdge(1, 2)
	g.addEdge(2, 3)
	g.addEdge(3, 4)
	fmt.Println(g.hasCycle())
}

A The dfs function lacks a parent parameter to avoid false cycle detection.

B The addEdge function does not add edges correctly.

C The visited map is not initialized properly.

D The main function does not call hasCycle correctly.

💡 Hint

In undirected graphs, you must ignore the edge back to the parent node during DFS.

The DFS function does not track the parent node, so it treats the immediate parent as a cycle, causing incorrect results.

🧠 Conceptual

advanced

Understanding cycle detection logic

In cycle detection for an undirected graph using DFS, why do we need to check if a visited neighbor is not the parent node?

A Because the parent node is the node with the highest degree.

B Because the parent node is always unvisited during DFS.

C Because the parent node is the root of the graph.

D Because the parent node is the node we came from, and revisiting it does not indicate a cycle.

💡 Hint

Think about the edge you just traveled to reach the current node.

When DFS visits neighbors, the edge back to the parent is not a cycle but a normal traversal edge, so it must be ignored.

❓ Predict Output

expert

Output of cycle detection on disconnected graph with multiple components

What is the output of the following Go code that detects cycles in an undirected graph with two disconnected components, one with a cycle and one without?

DSA Go

package main

import "fmt"

type Graph struct {
	adj map[int][]int
}

func (g *Graph) addEdge(u, v int) {
	g.adj[u] = append(g.adj[u], v)
	g.adj[v] = append(g.adj[v], u)
}

func (g *Graph) dfs(v, parent int, visited map[int]bool) bool {
	visited[v] = true
	for _, neighbor := range g.adj[v] {
		if !visited[neighbor] {
			if g.dfs(neighbor, v, visited) {
				return true
			}
		} else if neighbor != parent {
			return true
		}
	}
	return false
}

func (g *Graph) hasCycle() bool {
	visited := make(map[int]bool)
	for vertex := range g.adj {
		if !visited[vertex] {
			if g.dfs(vertex, -1, visited) {
				return true
			}
		}
	}
	return false
}

func main() {
	g := Graph{adj: make(map[int][]int)}
	// Component 1 with cycle
	g.addEdge(1, 2)
	g.addEdge(2, 3)
	g.addEdge(3, 1)
	// Component 2 without cycle
	g.addEdge(4, 5)
	g.addEdge(5, 6)
	fmt.Println(g.hasCycle())
}

A false

B true

C Compilation error

D Runtime panic

💡 Hint

The function checks all components for cycles.

The first component has a cycle, so the function returns true even though the second component does not have one.

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