Detect Cycle in an Undirected Graph Using DFS

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

Visualization Player

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:

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❯

Initialize a visited set to keep track of visited nodes.
For each unvisited node in the graph, perform DFS or BFS:

Use a helper function that takes the current node and its parent.
Mark the current node as visited.
For each neighbor of the current node:

If the neighbor is not visited, recurse with the neighbor and current node as parent.
If the neighbor is visited and not the parent, a cycle is detected.

If all components are checked and no cycles found, return false.

Code

JavaScript

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]
};

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

console.log("Cycle in graph1:", hasCycle(graph1)); // true
console.log("Cycle in graph2:", hasCycle(graph2)); // false

Time Complexity❯

Case	Time Complexity	Explanation
Best Case	O(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 Case	O(V + E)	DFS visits each node and edge once across all components, regardless of where the cycle is found.
Worst Case	O(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.

⬅ Previous TopicFlood Fill Algorithm - Graph Based

Next Topic ⮕Detect Cycle in an Undirected Graph using BFS

Comments

Loading comments...