Cycle Detection in Undirected Graph in DSA C# - Build from Scratch

Cycle Detection in Undirected Graph

📖 Scenario: Imagine you are working with a network of friends where each friendship is a connection between two people. You want to find out if there is any circle of friends where you can start from one person and come back to the same person by following friendships without repeating any connection.

🎯 Goal: You will build a program that detects if there is a cycle (a circle) in an undirected graph representing friendships.

📋 What You'll Learn

Create a graph using an adjacency list representation with exact edges

Add a helper variable to track visited nodes

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 is important in network design, social networks, and detecting deadlocks in operating systems.

💼 Career

Understanding graph traversal and cycle detection is essential for software engineers working with complex data structures, network analysis, and algorithm optimization.

1

Create the graph as an adjacency list

Create a dictionary called graph representing an undirected graph with these exact edges: 1 connected to 2 and 3, 2 connected to 1 and 3, 3 connected to 1, 2, and 4, 4 connected to 3.

DSA C#

# Your code here

Hint

Use a Dictionary<int, List<int>> to represent the graph. Each key is a node, and the value is a list of connected nodes.

2

Create a visited set to track visited nodes

Create a HashSet<int> called visited to keep track of nodes that have been visited during traversal.

DSA C#

using System.Collections.Generic;

Dictionary> graph = new Dictionary>
{
    {1, new List{2, 3}},
    {2, new List{1, 3}},
    {3, new List{1, 2, 4}},
    {4, new List{3}}
};

// Create visited set
# Your code here

Hint

Use HashSet<int> to store visited nodes for quick lookup.

3

Implement DFS function to detect cycles

Write a function called HasCycle that takes parameters int node, int parent, and uses graph and visited to detect if there is a cycle starting from node. Use depth-first search and return true if a cycle is found, otherwise false.

DSA C#

using System.Collections.Generic;

Dictionary> graph = new Dictionary>
{
    {1, new List{2, 3}},
    {2, new List{1, 3}},
    {3, new List{1, 2, 4}},
    {4, new List{3}}
};

HashSet visited = new HashSet();

// Write HasCycle function
# Your code here

Hint

Use recursion to visit neighbors. If a neighbor is visited and is not the parent, a cycle exists.

4

Check all nodes and print if cycle exists

Use a foreach loop to check each node in graph.Keys. If a node is not in visited, call HasCycle with parent as -1. Print "Cycle detected" if any call returns true, otherwise print "No cycle detected".

DSA C#

using System.Collections.Generic;

Dictionary> graph = new Dictionary>
{
    {1, new List{2, 3}},
    {2, new List{1, 3}},
    {3, new List{1, 2, 4}},
    {4, new List{3}}
};

HashSet visited = new HashSet();

bool HasCycle(int node, int parent)
{
    visited.Add(node);
    foreach (int neighbor in graph[node])
    {
        if (!visited.Contains(neighbor))
        {
            if (HasCycle(neighbor, node))
                return true;
        }
        else if (neighbor != parent)
        {
            return true;
        }
    }
    return false;
}

// Check all nodes and print result
# Your code here

Hint

Loop through all nodes to ensure disconnected parts are checked. Print the result based on cycle detection.

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 must have 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 during DFS, a visited node is found that is not the parent of the current node, 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 = check visited node not parent [OK]

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

Common Mistakes:

• Ignoring parent node in cycle check
• Assuming disconnected graph always has cycle
• Confusing cycle detection with edge count

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

easy

A. var graph = new List<int>[3]; for(int i=0; i<3; i++) graph[i] = new List<int>();

B. var graph = new List<int>[3]; graph = new List<int>();

C. List<int> graph = new List<int>[3];

D. var graph = new List(); graph.Add(new List<int>());

Solution

1. Step 1: Understand adjacency list initialization

   We need an array of lists, each list initialized separately to hold neighbors.

2. Step 2: Check code correctness

   var graph = new List<int>[3]; for(int i=0; i<3; i++) graph[i] = new List<int>(); creates an array of List<int> and initializes each element with a new List<int>, which is correct.

3. Final Answer:

   var graph = new List<int>[3]; for(int i=0; i<3; i++) graph[i] = new List<int>(); -> Option A

4. Quick Check:

   Initialize array of lists with loop [OK]

Hint: Initialize each list in array separately [OK]

Common Mistakes:

• Not initializing each list element
• Using wrong data types for adjacency list
• Assigning list directly to array variable

3. Consider the following C# code snippet for cycle detection in an undirected graph:

bool DFS(int node, int parent, List<int>[] graph, bool[] visited) {
    visited[node] = true;
    foreach(var neighbor in graph[node]) {
        if(!visited[neighbor]) {
            if(DFS(neighbor, node, graph, visited)) return true;
        } else if(neighbor != parent) {
            return true;
        }
    }
    return false;
}

// Graph edges: 0-1, 1-2, 2-0
// Call: DFS(0, -1, graph, visited)

What will be the output of this DFS call?

medium

A. Compilation error

B. false

C. StackOverflowException

D. true

Solution

1. Step 1: Analyze graph structure and DFS call

   The graph has edges 0-1, 1-2, and 2-0 forming a triangle cycle. DFS starts at node 0 with parent -1.

2. Step 2: Trace DFS for cycle detection

   DFS visits 0, then 1, then 2. When 2 checks neighbors, it finds 0 already visited and not parent, so returns true indicating cycle.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Triangle graph cycle detected = true [OK]

Hint: Cycle if visited neighbor not parent found [OK]

Common Mistakes:

• Ignoring parent check causing false cycle
• Assuming no cycle in triangle graph
• Confusing return values in recursion

4. The following C# code attempts to detect a cycle in an undirected graph but has a bug:

bool DFS(int node, int parent, List<int>[] graph, bool[] visited) {
    visited[node] = true;
    foreach(var neighbor in graph[node]) {
        if(!visited[neighbor]) {
            if(DFS(neighbor, node, graph, visited)) return true;
        } else {
            return true;
        }
    }
    return false;
}

What is the bug in this code?

medium

A. It never marks nodes as visited.

B. It returns true even if the visited neighbor is the parent node.

C. It does not traverse all neighbors.

D. It causes infinite recursion.

Solution

1. Step 1: Review cycle detection condition

   The code returns true if a neighbor is visited, but does not check if neighbor is parent.

2. Step 2: Identify why this causes incorrect cycle detection

   In undirected graphs, the parent node is always visited, so returning true here falsely detects a cycle.

3. Final Answer:

   It returns true even if the visited neighbor is the parent node. -> Option B

4. Quick Check:

   Must exclude parent node in cycle check [OK]

Hint: Exclude parent node when checking visited neighbors [OK]

Common Mistakes:

• Missing parent check in visited condition
• Assuming any visited neighbor means cycle
• Not marking nodes visited before recursion

5. You have an undirected graph represented as adjacency list:

0: [1, 2]
1: [0, 3]
2: [0, 3]
3: [1, 2, 4]
4: [3]

Using DFS cycle detection, which node will first detect the cycle and why?

hard

A. Node 4, because it has only one neighbor.

B. Node 0, because it starts the DFS traversal.

C. Node 2, because it connects back to already visited node 0.

D. Node 1, because it has the smallest index among neighbors.

Solution

1. Step 1: Understand graph structure and DFS traversal

   Assuming neighbor lists are processed in listed order, DFS starts at node 0, visits 1 (first neighbor), then 3 (from 1), then 2 (from 3).

2. Step 2: Identify where cycle is detected

   Node 2 has neighbors 0 and 3; 0 is already visited and not parent (parent=3), so cycle is detected at node 2 first.

3. Final Answer:

   Node 2, because it connects back to already visited node 0. -> Option C

4. Quick Check:

   Cycle detected at node with visited neighbors not parent [OK]

Hint: Cycle detected where visited neighbors not parent found first [OK]

Common Mistakes:

• Assuming cycle detected at start node
• Ignoring multiple visited neighbors
• Confusing leaf nodes with cycle detection