Detect Cycle in an Undirected Graph using DFS

In an undirected graph, a cycle is formed when a path starts and ends at the same node, with at least one intermediate edge. The problem of detecting a cycle asks: Given an undirected graph, does it contain at least one cycle?

This is a fundamental graph problem often used in network reliability, dependency checking, and topology analysis.

Understanding the Problem

We are given an undirected graph, and our task is to detect whether this graph contains any cycles. A cycle occurs when you can start from a node and return to the same node by traversing edges—without repeating any edge and visiting a node that isn’t the immediate parent during DFS traversal.

This problem is important in many real-world scenarios like detecting deadlocks in networks, ensuring data consistency in distributed systems, and validating tree-like structures.

Step-by-Step Solution with Example

Step 1: Represent the Graph

We use an adjacency list to represent the graph. For each node, we store a list of its neighbors. For example, consider the following undirected graph:

Graph: 
0 -- 1
|    |
3 -- 2

This graph has a cycle: 0 → 1 → 2 → 3 → 0.

Step 2: Define a Visited Array

We need to track which nodes we’ve already visited. We'll use a visited[] array initialized to false for all nodes.

Step 3: Perform DFS Traversal

We perform a DFS from each unvisited node. While exploring neighbors, we check:

• If the neighbor is unvisited, recursively call DFS.
• If the neighbor is visited and it is not the parent of the current node, a cycle is detected.

Step 4: Handle Disconnected Components

The graph might have more than one component. So, we run DFS from every unvisited node to ensure no cycles exist in any part of the graph.

Step 5: Apply to Example

Let’s apply the logic to our earlier graph:

1. Start from node 0: visit 1 → visit 2 → visit 3 → back to 0 (already visited and not parent). Cycle detected!

Edge Cases

Case 1: Graph with No Cycles

If the graph is a tree or forest, there are no cycles by definition. DFS will visit all nodes without revisiting any node other than the parent.

Case 2: Graph with Simple Cycle

In a graph like 0 - 1 - 2 - 0, DFS will return to node 0 from node 2, which is not the parent of 2. This confirms a cycle.

Case 3: Disconnected Graph

If the graph has multiple disconnected components, we need to perform DFS on each one. If any one of them contains a cycle, we return true.

Case 4: Self-Loops or Parallel Edges

A self-loop (e.g., edge from 0 to 0) is always a cycle. Parallel edges (e.g., multiple edges between 0 and 1) can also form trivial cycles depending on how the graph is built.

Finally

Cycle detection in an undirected graph using DFS is a fundamental technique. By carefully tracking visited nodes and skipping the parent node during neighbor checks, we can robustly detect cycles. It’s crucial to consider disconnected graphs, self-loops, and parallel edges to handle all scenarios correctly. This approach works efficiently for sparse graphs and is a solid tool in any programmer's toolkit.

1. Initialize a visited set to keep track of visited nodes.
2. For each unvisited node in the graph, perform DFS or BFS:
1. Use a helper function that takes the current node and its parent.
2. Mark the current node as visited.
3. For each neighbor of the current node:
1. If the neighbor is not visited, recurse with the neighbor and current node as parent.
2. If the neighbor is visited and not the parent, a cycle is detected.
3. If all components are checked and no cycles found, return false.

#include <stdio.h>
#include <stdbool.h>

#define MAX_NODES 100

int graph[MAX_NODES][MAX_NODES];
bool visited[MAX_NODES];

bool dfs(int node, int parent, int n) {
    visited[node] = true;
    for (int neighbor = 0; neighbor < n; neighbor++) {
        if (graph[node][neighbor]) {
            if (!visited[neighbor]) {
                if (dfs(neighbor, node, n)) return true;
            } else if (neighbor != parent) {
                return true;
            }
        }
    }
    return false;
}

bool hasCycle(int n) {
    for (int i = 0; i < n; i++) {
        visited[i] = false;
    }
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            if (dfs(i, -1, n)) return true;
        }
    }
    return false;
}

int main() {
    int n = 4;
    graph[0][1] = graph[1][0] = 1;
    graph[1][2] = graph[2][1] = 1;
    graph[2][3] = graph[3][2] = 1;
    graph[3][0] = graph[0][3] = 1;

    if (hasCycle(n)) {
        printf("Cycle detected\n");
    } else {
        printf("No cycle\n");
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

bool dfs(int node, int parent, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            if (dfs(neighbor, node, graph, visited)) return true;
        } else if (neighbor != parent) {
            return true;
        }
    }
    return false;
}

bool hasCycle(vector<vector<int>>& graph, int n) {
    vector<bool> visited(n, false);
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            if (dfs(i, -1, graph, visited)) return true;
        }
    }
    return false;
}

int main() {
    int n = 4;
    vector<vector<int>> graph(n);
    graph[0] = {1, 3};
    graph[1] = {0, 2};
    graph[2] = {1, 3};
    graph[3] = {0, 2};

    cout << (hasCycle(graph, n) ? "Cycle detected" : "No cycle") << endl;
    return 0;
}

def has_cycle(graph):
    visited = set()

    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:
                return True
        return False

    for node in graph:
        if node not in visited:
            if dfs(node, -1):
                return True
    return False


graph = {
    0: [1],
    1: [0, 2],
    2: [1, 3],
    3: [2, 0]
}

print("Cycle detected" if has_cycle(graph) else "No cycle")

import java.util.*;

public class CycleDetection {
    public static boolean dfs(int node, int parent, Map<Integer, List<Integer>> graph, Set<Integer> visited) {
        visited.add(node);
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited.contains(neighbor)) {
                if (dfs(neighbor, node, graph, visited)) return true;
            } else if (neighbor != parent) {
                return true;
            }
        }
        return false;
    }

    public static boolean hasCycle(Map<Integer, List<Integer>> graph) {
        Set<Integer> visited = new HashSet<>();
        for (int node : graph.keySet()) {
            if (!visited.contains(node)) {
                if (dfs(node, -1, graph, visited)) return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1));
        graph.put(1, Arrays.asList(0, 2));
        graph.put(2, Arrays.asList(1, 3));
        graph.put(3, Arrays.asList(2, 0));

        System.out.println(hasCycle(graph) ? "Cycle detected" : "No cycle");
    }
}

function hasCycle(graph) {
  const visited = new Set();

  function dfs(node, parent) {
    visited.add(node);
    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, node)) return true;
      } else if (neighbor !== parent) {
        return true;
      }
    }
    return false;
  }

  for (const node in graph) {
    if (!visited.has(Number(node))) {
      if (dfs(Number(node), -1)) return true;
    }
  }
  return false;
}

const graph1 = {
  0: [1],
  1: [0, 2],
  2: [1, 3],
  3: [2, 0]
};

console.log("Cycle in graph1:", hasCycle(graph1));

package main

import (
    "fmt"
)

func dfs(node, 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 hasCycle(graph map[int][]int) bool {
    visited := make(map[int]bool)
    for node := range graph {
        if !visited[node] {
            if dfs(node, -1, graph, visited) {
                return true
            }
        }
    }
    return false
}

func main() {
    graph := map[int][]int{
        0: {1},
        1: {0, 2},
        2: {1, 3},
        3: {2, 0},
    }
    fmt.Println("Cycle detected:", hasCycle(graph))
}

use std::collections::{HashMap, HashSet};

fn dfs(node: i32, parent: i32, graph: &HashMap<i32, Vec<i32>>, visited: &mut HashSet<i32>) -> bool {
    visited.insert(node);
    if let Some(neighbors) = graph.get(&node) {
        for &neighbor in neighbors {
            if !visited.contains(&neighbor) {
                if dfs(neighbor, node, graph, visited) {
                    return true;
                }
            } else if neighbor != parent {
                return true;
            }
        }
    }
    false
}

fn has_cycle(graph: &HashMap<i32, Vec<i32>>) -> bool {
    let mut visited = HashSet::new();
    for &node in graph.keys() {
        if !visited.contains(&node) {
            if dfs(node, -1, graph, &mut visited) {
                return true;
            }
        }
    }
    false
}

fn main() {
    let mut graph = HashMap::new();
    graph.insert(0, vec![1]);
    graph.insert(1, vec![0, 2]);
    graph.insert(2, vec![1, 3]);
    graph.insert(3, vec![2, 0]);

    println!("Cycle detected: {}", has_cycle(&graph));
}

fun hasCycle(graph: Map<Int, List<Int>>): Boolean {
    val visited = mutableSetOf<Int>()

    fun dfs(node: Int, parent: Int): Boolean {
        visited.add(node)
        for (neighbor in graph[node] ?: emptyList()) {
            if (neighbor !in visited) {
                if (dfs(neighbor, node)) return true
            } else if (neighbor != parent) {
                return true
            }
        }
        return false
    }

    for (node in graph.keys) {
        if (node !in visited) {
            if (dfs(node, -1)) return true
        }
    }
    return false
}

fun main() {
    val graph = mapOf(
        0 to listOf(1),
        1 to listOf(0, 2),
        2 to listOf(1, 3),
        3 to listOf(2, 0)
    )
    println("Cycle detected: ${hasCycle(graph)}")
}

func hasCycle(_ graph: [Int: [Int]]) -> Bool {
    var visited = Set<Int>()

    func dfs(_ node: Int, _ parent: Int) -> Bool {
        visited.insert(node)
        for neighbor in graph[node] ?? [] {
            if !visited.contains(neighbor) {
                if dfs(neighbor, node) { return true }
            } else if neighbor != parent {
                return true
            }
        }
        return false
    }

    for node in graph.keys {
        if !visited.contains(node) {
            if dfs(node, -1) { return true }
        }
    }
    return false
}

let graph = [
    0: [1],
    1: [0, 2],
    2: [1, 3],
    3: [2, 0]
]

print("Cycle detected: \(hasCycle(graph))")

function hasCycle(graph: Record<number, number[]>): boolean {
  const visited = new Set<number>();

  function dfs(node: number, parent: number): boolean {
    visited.add(node);
    for (const neighbor of graph[node] || []) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, node)) return true;
      } else if (neighbor !== parent) {
        return true;
      }
    }
    return false;
  }

  for (const node in graph) {
    const num = Number(node);
    if (!visited.has(num)) {
      if (dfs(num, -1)) return true;
    }
  }
  return false;
}

const graph = {
  0: [1],
  1: [0, 2],
  2: [1, 3],
  3: [2, 0]
};

console.log("Cycle detected:", hasCycle(graph));

Time complexity

Space complexity

O(V)

The space is used for the visited set and recursive call stack (or explicit stack), which grows up to the number of vertices.