Detect Cycle in an Undirected Graph
Using DFS

⬅ Previous Topic

Next Topic ⮕

Detect Cycle in an Undirected Graph using BFS

Topic Contents

Problem Examples Solution Algorithm Code Time Space

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 Topic

Flood Fill Algorithm - Graph Based

Next Topic ⮕

Detect Cycle in an Undirected Graph using BFS

Overview of Techniques14
❯

Sorting6
❯

Arrays32
❯

Arrays - Binary Search28
❯

Strings18
❯

Matrix3
❯

Matrix - Binary Search5
❯

Binary Trees36
❯

Binary Search Trees14
❯

Graphs46
❯

Tries1
❯

Detect Cycle in an Undirected Graph
Using DFS

Problem Statement

Examples❯

Solution❯

Case 1: Graph with no cycles

Case 2: Graph with a simple cycle

Case 3: Graph with disconnected components

Case 4: Self-loop or parallel edges

Conclusion

Algorithm Steps

Code

Time Complexity

Space Complexity

Support ProgramGuru.org❯

Detect Cycle in an Undirected GraphUsing DFS

Problem Statement

Examples❯

Solution❯

Case 1: Graph with no cycles

Case 2: Graph with a simple cycle

Case 3: Graph with disconnected components

Case 4: Self-loop or parallel edges

Conclusion

Algorithm Steps

Code

Time Complexity

Space Complexity

Welcome to ProgramGuru

Support ProgramGuru.org❯

Detect Cycle in an Undirected Graph
Using DFS