Cycle Detection in Undirected Graph in DSA Typescript - Time & Space Complexity

Time Complexity: Cycle Detection in Undirected Graph

O(n + e)

Understanding Time Complexity

We want to understand how long it takes to check if an undirected graph has a cycle.

The question is: how does the time grow as the graph gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

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

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

This code checks each node and uses depth-first search to find if any cycle exists in the graph.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The depth-first search (DFS) visits each node and its neighbors.
• How many times: Each node and edge is visited once during DFS.

How Execution Grows With Input

As the graph grows, the DFS explores all nodes and edges once.

Input Size (n nodes, e edges)	Approx. Operations
10 nodes, 15 edges	About 25 visits (nodes + edges)
100 nodes, 200 edges	About 300 visits
1000 nodes, 3000 edges	About 4000 visits

Pattern observation: The operations grow roughly in proportion to the number of nodes plus edges.

Final Time Complexity

Time Complexity: O(n + e)

This means the time to detect a cycle grows linearly with the total nodes and edges in the graph.

Common Mistake

[X] Wrong: "Cycle detection takes O(n²) time because of nested loops."

[OK] Correct: The DFS visits each node and edge only once, so it does not repeat work unnecessarily.

Interview Connect

Understanding this time complexity helps you explain how graph traversal algorithms work efficiently in real problems.

Self-Check

"What if the graph was directed instead of undirected? How would the time complexity change?"