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

Solution❯

Case 1: Graph with no cycles

If the graph is a tree or a forest (collection of trees), then by definition, there are no cycles. DFS will visit each node and mark it, and every unvisited neighbor will be explored. Since no node will be revisited except through the parent link, no cycle is detected.

Case 2: Graph with a simple cycle

In a graph like A - B - C - A, starting DFS at any node will eventually lead to visiting a previously visited node that is not the parent. For example, from A → B → C → back to A (not the parent of C), a cycle is detected and the function returns true.

Case 3: Graph with disconnected components

Since the graph may not be fully connected, we need to apply DFS from every unvisited node. If any component contains a cycle, the function will detect it. If all are acyclic, the graph is cycle-free.

Case 4: Self-loop or parallel edges

In undirected graphs, a self-loop (A - A) or parallel edge (A - B appearing twice) may create trivial cycles. These should be detected based on implementation. Normally, a self-loop is a cycle since the neighbor is the same as the current node and not the parent.

Conclusion

By keeping track of visited nodes and ensuring that we don’t count the parent edge as a cycle, we can correctly detect cycles in undirected graphs using DFS. This method ensures that even complex structures or multiple components are properly analyzed.

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