Cycle Detection in Undirected Graph in DSA C#

Mental Model

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

Analogy: Imagine walking in a park with paths connecting benches. If you can start at one bench, walk along paths, and return to the same bench without turning back on the path you just came from, there is a cycle.

0 -> 1 -> 2
↑         ↓
4 ← 3 ←---

Dry Run Walkthrough

Input: Graph with edges: 0-1, 1-2, 2-3, 3-4, 4-0 (cycle present)

Goal: Detect if the graph contains any cycle

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

Visited: {0}
Stack: [0]

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

Step 2: From 0, visit neighbor 1, mark 1 as visited

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

Why: Explore next node connected to 0

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

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

Why: Continue deeper to find cycles

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

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

Why: Keep exploring neighbors

Step 5: From 3, visit neighbor 4, mark 4 as visited

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

Why: Reach last node in path

Step 6: From 4, neighbor 0 is visited and not parent, cycle detected

Cycle found at edge 4-0

Why: Back edge to visited node other than parent means cycle

Result:

Cycle detected in the graph

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    private int V;
    private List<int>[] adj;

    public Graph(int vertices) {
        V = vertices;
        adj = new List<int>[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int v, int w) {
        adj[v].Add(w);
        adj[w].Add(v);
    }

    private bool DFS(int v, bool[] visited, int parent) {
        visited[v] = true; // mark current node visited
        foreach (int neighbor in adj[v]) {
            if (!visited[neighbor]) {
                if (DFS(neighbor, visited, v)) {
                    return true; // cycle found in recursion
                }
            } else if (neighbor != parent) {
                return true; // visited neighbor not parent means cycle
            }
        }
        return false; // no cycle found from this node
    }

    public bool HasCycle() {
        bool[] visited = new bool[V];
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (DFS(i, visited, -1)) {
                    return true; // cycle detected
                }
            }
        }
        return false; // no cycle in any component
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(5);
        g.AddEdge(0, 1);
        g.AddEdge(1, 2);
        g.AddEdge(2, 3);
        g.AddEdge(3, 4);
        g.AddEdge(4, 0);

        Console.WriteLine(g.HasCycle() ? "Cycle detected in the graph" : "No cycle in the graph");
    }
}

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

mark node as visited to avoid revisiting

if (!visited[neighbor]) { if (DFS(neighbor, visited, v)) { return true; } }

recursively visit unvisited neighbors to explore deeper

else if (neighbor != parent) { return true; }

detect cycle if neighbor visited and not parent

for (int i = 0; i < V; i++) { if (!visited[i]) { if (DFS(i, visited, -1)) { 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 array and recursion stack in worst case

vs Alternative: Compared to using union-find which also runs in near O(V + E), DFS is simpler to implement but union-find can be more efficient for dynamic graphs

Edge Cases

Empty graph with no vertices

No cycle detected as there are no nodes

DSA C#

for (int i = 0; i < V; i++) { if (!visited[i]) { if (DFS(i, visited, -1)) { return true; } } }

Graph with single vertex and no edges

No cycle detected as no edges exist

DSA C#

for (int i = 0; i < V; i++) { if (!visited[i]) { if (DFS(i, visited, -1)) { return true; } } }

Graph with multiple disconnected components, one with cycle

Cycle detected because DFS checks all components

DSA C#

for (int i = 0; i < V; i++) { if (!visited[i]) { if (DFS(i, visited, -1)) { return true; } } }

When to Use This Pattern

When you see a problem asking if a path loops back 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, causing false cycle detection
Fix: Add condition to ignore the edge back to parent node during DFS

Summary

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

Use when you need to find loops in undirected graphs to avoid infinite traversals or validate graph properties.

The key insight is that a visited neighbor that is not the parent indicates 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 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