Cycle Detection in Undirected Graph in DSA Go - Build from Scratch

Cycle Detection in Undirected Graph

📖 Scenario: Imagine you are working with a network of roads connecting cities. You want to check if there is any circular route that starts and ends at the same city without repeating roads. This is called cycle detection in an undirected graph.

🎯 Goal: You will build a program in Go to detect if an undirected graph has any cycle. The graph will be represented using an adjacency list.

📋 What You'll Learn

Create an adjacency list to represent the graph

Add a helper variable to track visited cities

Implement a depth-first search (DFS) function to detect cycles

Print whether the graph contains a cycle or not

💡 Why This Matters

🌍 Real World

Cycle detection helps in network design, detecting deadlocks, and ensuring no circular dependencies in systems.

💼 Career

Understanding graph traversal and cycle detection is important for software engineers working with networks, databases, and complex data relationships.

1

Create the graph adjacency list

Create a variable called graph as a map[int][]int with these exact edges: 0 connected to 1 and 2, 1 connected to 0 and 2, 2 connected to 0 and 1, 3 connected to 4, and 4 connected to 3.

DSA Go

graph := map[int][]int{
    // Your code here
}

Hint

Use a map where keys are city numbers and values are slices of connected cities.

2

Add a visited map to track visited cities

Add a variable called visited as a map[int]bool initialized as empty to keep track of visited cities.

DSA Go

package main

import "fmt"

func main() {
    graph := map[int][]int{
        0: {1, 2},
        1: {0, 2},
        2: {0, 1},
        3: {4},
        4: {3},
    }
    visited := map[int]bool{}
    // Your code here
}

Hint

Use a map[int]bool to mark cities as visited or not.

3

Implement DFS function to detect cycles

Write a function called dfs with parameters node int, parent int, graph map[int][]int, and visited map[int]bool. It returns a bool. Use DFS to check if a cycle exists starting from node. Return true if a cycle is found, otherwise false. Mark node as visited. For each neighbor, if not visited, recursively call dfs with neighbor and current node as parent. If neighbor is visited and not parent, return true for cycle.

DSA Go

package main

import "fmt"

func main() {
    graph := map[int][]int{
        0: {1, 2},
        1: {0, 2},
        2: {0, 1},
        3: {4},
        4: {3},
    }
    visited := map[int]bool{}
}

// Write dfs function below
// Your code here

Hint

Use recursion to explore neighbors. If you find a visited neighbor that is not the parent, a cycle exists.

4

Check all nodes and print if cycle exists

In main, use a for loop with variable node over graph keys. If node is not visited, call dfs(node, -1, graph, visited). If it returns true, print "Cycle detected" and return. After the loop, print "No cycle detected".

DSA Go

package main

import "fmt"

func dfs(node int, parent int, graph map[int][]int, visited map[int]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 := map[int][]int{
        0: {1, 2},
        1: {0, 2},
        2: {0, 1},
        3: {4},
        4: {3},
    }
    visited := map[int]bool{}

    for node := range graph {
        // Your code here
    }
}

Hint

Check each city. If DFS finds a cycle, print and stop. Otherwise, print no 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