Detect a Cycle in an Undirected Graph using DFS

Cycle detection in an undirected graph using Depth First Search (DFS) is a fundamental graph traversal problem. Building directly upon BFS cycle-detection concepts, this chapter explores how recursion stacks, parent-tracking parameters, and visited arrays synergize to identify closed loops in both single-component and disconnected graphs.

1. Why Do We Need This? (Problem Statement & Status Quo)

In graph theory, detecting whether an undirected graph contains a cycle is essential for modeling networks, detecting deadlocks, and validating structural integrity (e.g., ensuring a network topology is a valid tree).

• What is a cycle? A cycle exists if you can start at a specific node, traverse along a valid sequence of edges without breaking or retracing any edge directly back immediately, and eventually return to the exact same starting node.
• The Limitation of Status Quo: While Breadth First Search (BFS) utilizes a queue to inspect neighbor layers iteratively, Depth First Search (DFS) plunges down deep pathways recursively. When performing DFS, simply encountering a visited node does not automatically mean a cycle exists—it might just be the immediate parent node you came from. Distinguishing between a legitimate back-edge (cycle) and a parent-edge requires disciplined state tracking.

2. Core Mental Model & Real-Life Analogy

Real-Life Analogy: Exploring a Cave Network with a Ball of String

Imagine exploring a dark cave system where tunnels branch out in various directions. You hold a spool of string anchored to your starting point (the parent tracker).

• As you crawl deeper down a tunnel (DFS recursion), you mark the walls of each chamber as Visited.
• If you encounter a chamber you have already visited, you check your string. If the string leads directly back to the chamber you just came out of (the Parent), it's just a dead-end corridor looping back—not a cycle.
• However, if the visited chamber connects to a different path in your network that is not your direct parent string, you have discovered a closed loop—a cycle exists.

3. The Intuition: Tracking Parents in DFS

When executing DFS from a source node, every recursive call must carry two critical pieces of information:

1. node: The current vertex you are examining.
2. parent: The exact vertex you came from immediately prior to reaching node.

If DFS reaches an adjacent node that is already visited, but is NOT the current node's parent, that means the node was reached via another independent path. This confirms a cycle.

4. Step-by-Step Algorithm & Pseudocode Evolution

The algorithm proceeds by iterating through all graph vertices, initiating a DFS traversal from any unvisited node, and recursively inspecting unvisited neighbors while keeping track of parents.

Comprehensive Pseudocode

boolean dfs(node, parent, visited, adj) {
    visited[node] = true;
    
    for (int neighbor : adj[node]) {
        if (!visited[neighbor]) {
            // Recurse deeper into unvisited neighbors
            if (dfs(neighbor, node, visited, adj) == true) {
                return true;
            }
        } 
        else if (neighbor != parent) {
            // Visited node is NOT the parent -> Cycle detected!
            return true;
        }
    }
    return false;
}

5. Handling Disconnected Components

Real-world graphs are frequently disconnected (split across multiple isolated components). Relying solely on dfs(1, -1) will inspect only the component containing node 1, missing cycles in separate components.

Solution: The Component Guard Loop

To guarantee full graph coverage, wrap the DFS initiation in a loop checking every node from 0 (or 1) up to N:

bool isCycle(int V, vector<int> adj[]) {
    vector<int> visited(V, 0);
    
    for (int i = 0; i < V; i++) {
        if (!visited[i]) {
            if (dfs(i, -1, visited, adj) == true) {
                return true;
            }
        }
    }
    return false;
}

6. Complete Implementation (C++ & Java)

Below are the complete, production-ready implementations for both C++ and Java.

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    bool detect(int node, int parent, vector<int> &visited, vector<int> adj[]) {
        visited[node] = 1;
        
        // Traverse all adjacent nodes
        for (auto adjacentNode : adj[node]) {
            if (!visited[adjacentNode]) {
                if (detect(adjacentNode, node, visited, adj)) {
                    return true;
                }
            }
            else if (adjacentNode != parent) {
                return true; // Visited and not parent -> Cycle found
            }
        }
        return false;
    }

public:
    bool isCycle(int V, vector<int> adj[]) {
        vector<int> visited(V, 0);
        for (int i = 0; i < V; i++) {
            if (!visited[i]) {
                if (detect(i, -1, visited, adj)) return true;
            }
        }
        return false;
    }
};

Java Implementation

import java.util.ArrayList;
import java.util.Arrays;

class Solution {
    private boolean detect(int node, int parent, int[] visited, ArrayList<ArrayList<Integer>> adj) {
        visited[node] = 1;
        
        for (int adjacentNode : adj.get(node)) {
            if (visited[adjacentNode] == 0) {
                if (detect(adjacentNode, node, visited, adj)) {
                    return true;
                }
            } else if (adjacentNode != parent) {
                return true; // Visited and not parent -> Cycle found
            }
        }
        return false;
    }

    public boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj) {
        int[] visited = new int[V];
        Arrays.fill(visited, 0);
        
        for (int i = 0; i < V; i++) {
            if (visited[i] == 0) {
                if (detect(i, -1, visited, adj)) return true;
            }
        }
        return false;
    }
}

7. Complexity Analysis

Summary and Key Takeaways

• Definition of Cycle: A cycle is detected when a traversal encounters a previously visited node that is not the immediate parent of the current node.
• Role of the Parent Parameter: Carrying the parent reference in recursive DFS calls prevents false positives caused by immediately backtracking along the edge you arrived from.
• Recursive State: The DFS approach leverages the system call stack naturally, marking nodes visited upon entry and bubbling boolean results (true / false) back up the call chain.
• Disconnected Graphs Support: Always incorporate an outer loop spanning all vertices to catch cycles hidden in isolated or multi-component graph structures.
• Time Complexity Balance: Running in $O(N + E)$ time and $O(N)$ auxiliary space, DFS provides an optimal, elegant solution for undirected graph cycle detection.