Detect Cycle in an Undirected Graph Using DFS - Visualization

Graphs

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

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.

Examples❯

Graph Expected Output Description
{ 0: [1], 1: [0, 2], 2: [1, 3], 3: [2, 0] }
true
Cycle exists: 0 → 1 → 2 → 3 → 0
{ 0: [1], 1: [0, 2], 2: [1] }
false
No cycle, this is a tree
{} false Empty graph has no cycles
{ 0: [] }
false
Single node with no edges
{ 0: [1], 1: [0], 2: [3], 3: [2, 4], 4: [3] }
false
Two disconnected components, both acyclic
{ 0: [1, 2], 1: [0, 2], 2: [0, 1] }
true
Triangle graph, a simple cycle exists

Solution❯

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.

Algorithm Steps❯

  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.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(V + E)Even if a cycle is found early, we must visit each node and edge in the worst connected component to be sure.
Average CaseO(V + E)DFS visits each node and edge once across all components, regardless of where the cycle is found.
Worst CaseO(V + E)Every node and edge in the graph must be visited to ensure there is no cycle.

Space Complexity❯

O(V)

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


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...