Connected Components Using BFS in DSA Typescript - Time & Space Complexity

Time Complexity: Connected Components Using BFS

O(n + e)

Understanding Time Complexity

We want to understand how long it takes to find all connected parts in a graph using BFS.

How does the time grow as the graph gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function connectedComponents(graph: Map): number {
  const visited = new Set();
  let count = 0;

  for (const node of graph.keys()) {
    if (!visited.has(node)) {
      bfs(node, graph, visited);
      count++;
    }
  }
  return count;
}

function bfs(start: number, graph: Map, visited: Set) {
  const queue: number[] = [start];
  visited.add(start);

  while (queue.length > 0) {
    const node = queue.shift()!;
    for (const neighbor of graph.get(node) || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}
    

This code counts how many connected groups are in a graph by visiting nodes using BFS.

Identify Repeating Operations

• Primary operation: Visiting each node and its neighbors once using BFS.
• How many times: Each node and edge is checked once during the BFS traversals.

How Execution Grows With Input

As the graph grows, the BFS visits every node and edge 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 work grows roughly with the number of nodes plus edges.

Final Time Complexity

Time Complexity: O(n + e)

This means the time grows linearly with the total nodes and edges in the graph.

Common Mistake

[X] Wrong: "The BFS runs in O(n²) because it has nested loops."

[OK] Correct: Each edge and node is visited only once, so the total work is linear, not quadratic.

Interview Connect

Understanding BFS time complexity helps you explain graph traversal efficiency clearly and confidently.

Self-Check

"What if the graph was represented as an adjacency matrix instead of adjacency lists? How would the time complexity change?"