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?"

Practice

1. What does BFS (Breadth-First Search) help find in an unweighted graph?

easy

A. The shortest path from a start node to all other nodes

B. The heaviest edge in the graph

C. The longest path between two nodes

D. The total number of edges in the graph

Solution

1. Step 1: Understand BFS traversal

   BFS explores nodes level by level starting from the source node.

2. Step 2: BFS finds shortest paths in unweighted graphs

   Because BFS visits nodes in order of increasing distance, it finds shortest paths.

3. Final Answer:

   The shortest path from a start node to all other nodes -> Option A

4. Quick Check:

   BFS = shortest path in unweighted graph [OK]

Hint: BFS explores neighbors level-wise to find shortest paths [OK]

Common Mistakes:

• Confusing BFS with DFS for shortest path
• Thinking BFS finds longest path
• Assuming BFS works for weighted graphs without modification

2. Which TypeScript data structure is best to use as a queue for BFS implementation?

easy

A. Array with push() and pop()

B. Array with push() and shift()

C. Set with add() and delete()

D. Map with set() and get()

Solution

1. Step 1: Identify queue operations needed for BFS

   BFS requires FIFO order: enqueue at end, dequeue from front.

2. Step 2: Choose Array methods matching FIFO

   push() adds to end, shift() removes from front, so Array with push() and shift() works as a queue.

3. Final Answer:

   Array with push() and shift() -> Option B

4. Quick Check:

   Queue = push + shift [OK]

Hint: Use push() to enqueue and shift() to dequeue in Array [OK]

Common Mistakes:

• Using pop() instead of shift() causes LIFO behavior
• Using Set or Map which don't maintain order
• Using Array methods incorrectly for queue

3. What is the output distance array after running BFS from node 0 on this graph?

const graph = [[1,2],[0,3],[0,3],[1,2]];
// Nodes: 0,1,2,3
// Edges: 0-1, 0-2, 1-3, 2-3

medium

A. [0, 1, 1, 2]

B. [0, 2, 2, 3]

C. [1, 0, 1, 2]

D. [0, 1, 2, 1]

Solution

1. Step 1: Initialize distances and start BFS from node 0

   Distance to 0 is 0, others infinity initially.

2. Step 2: Visit neighbors level-wise

   Neighbors of 0 are 1 and 2, set distance 1 for both. Then neighbors of 1 and 2 include 3, set distance 2 for 3.

3. Final Answer:

   [0, 1, 1, 2] -> Option A

4. Quick Check:

   Distances from 0 = [0,1,1,2] [OK]

Hint: Distance increments by 1 per BFS level [OK]

Common Mistakes:

• Mixing up node indices and distances
• Assigning wrong distances to neighbors
• Confusing BFS with DFS order

4. Identify the bug in this BFS shortest path code snippet:

function bfs(graph: number[][], start: number) {
  const queue = [];
  const distances = Array(graph.length).fill(-1);
  distances[start] = 0;
  queue.push(start);
  while (queue.length > 0) {
    const node = queue.pop();
    for (const neighbor of graph[node]) {
      if (distances[neighbor] === -1) {
        distances[neighbor] = distances[node] + 1;
        queue.push(neighbor);
      }
    }
  }
  return distances;
}

medium

A. Neighbors are not checked for visited status

B. Distances array initialized with -1 instead of 0

C. Start node is not added to queue

D. Using pop() instead of shift() causes wrong BFS order

Solution

1. Step 1: Check queue operations in BFS

   BFS requires FIFO queue, but pop() removes from end (LIFO).

2. Step 2: Identify impact of pop() usage

   Using pop() makes traversal DFS-like, breaking shortest path logic.

3. Final Answer:

   Using pop() instead of shift() causes wrong BFS order -> Option D

4. Quick Check:

   Queue must be FIFO: push + shift [OK]

Hint: Use shift() to dequeue in BFS, not pop() [OK]

Common Mistakes:

• Confusing pop() with shift() for queue
• Ignoring visited check for neighbors
• Incorrect initialization of distances

5. Given a graph with nodes 0 to 4 and edges [[0,1],[0,2],[1,3],[2,3],[3,4]], what is the shortest path from node 0 to node 4 using BFS?

hard

A. [0, 1, 2, 3, 4]

B. [0, 2, 3, 4]

C. [0, 1, 3, 4]

D. [0, 4]

Solution

1. Step 1: Explore neighbors from node 0

   Neighbors are 1 and 2, both distance 1.

2. Step 2: Explore neighbors of 1 and 2

   Both connect to 3 at distance 2.

3. Step 3: From 3, move to 4 at distance 3

   Shortest path is 0 -> 1 -> 3 -> 4 or 0 -> 2 -> 3 -> 4.

4. Step 4: Choose path found first by BFS

   BFS visits 1 before 2, so path is [0,1,3,4].

5. Final Answer:

   [0, 1, 3, 4] -> Option C

6. Quick Check:

   Shortest path BFS = [0,1,3,4] [OK]

Hint: BFS finds shortest path by earliest discovered route [OK]

Common Mistakes:

• Assuming direct edge from 0 to 4 exists
• Choosing longer path ignoring BFS order
• Confusing path with distance array