Shortest Path in Unweighted Graph Using BFS in DSA Typescript - Time & Space Complexity

Time Complexity: Shortest Path in Unweighted Graph Using BFS

O(V + E)

Understanding Time Complexity

We want to understand how long it takes to find the shortest path in an unweighted graph using BFS.

Specifically, how the time grows as the graph gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function shortestPathBFS(graph: Map<number, number[]>, start: number, end: number): number {
  const queue: number[] = [start];
  const visited = new Set<number>([start]);
  let distance = 0;

  while (queue.length > 0) {
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift()!;
      if (node === end) return distance;
      for (const neighbor of graph.get(node) || []) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }
    distance++;
  }
  return -1;
}
    

This code finds the shortest number of steps from start to end in an unweighted graph using BFS.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each node and checking its neighbors in the graph.
• How many times: Each node is visited once, and each edge is checked once during the BFS traversal.

How Execution Grows With Input

As the graph grows, the BFS visits more nodes and edges.

Input Size (n = nodes)	Approx. Operations (visiting nodes + edges)
10	About 10 nodes + edges checked
100	About 100 nodes + edges checked
1000	About 1000 nodes + edges checked

Pattern observation: The work grows roughly in proportion to the number of nodes and edges.

Final Time Complexity

Time Complexity: O(V + E)

This means the time grows linearly with the number of nodes (V) plus the number of edges (E) in the graph.

Common Mistake

[X] Wrong: "BFS takes O(V²) time because it loops over nodes inside another loop."

[OK] Correct: BFS visits each node and edge only once, so it does not multiply visits. The inner loops run only for neighbors, not all nodes.

Interview Connect

Understanding BFS time complexity helps you explain how graph searches scale and why BFS is efficient for shortest paths in unweighted graphs.

Self-Check

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