Shortest Path in Unweighted Graph Using BFS in DSA Typescript - Execution Trace

Concept Flow - Shortest Path in Unweighted Graph Using BFS

Start at source node

↓

Initialize queue with source

↓

While queue not empty

↓

Dequeue current node

↓

For each neighbor

↓

If neighbor not visited

↓

Mark visited, set distance, enqueue

↓

Repeat until all reachable nodes processed

↓

Shortest distances from source ready

Start from the source node, explore neighbors level by level using a queue, marking distances as you go until all reachable nodes are processed.

Execution Sample

DSA Typescript

const graph: Record<string, string[]> = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A', 'D'],
  D: ['B', 'C', 'E'],
  E: ['D']
};

function bfsShortestPath(graph: Record<string, string[]>, source: string): Record<string, number> {
  const queue: string[] = [source];
  const visited: Set<string> = new Set([source]);
  const distance: Record<string, number> = {};
  distance[source] = 0;
  while (queue.length > 0) {
    const current = queue.shift()!;
    for (const neighbor of graph[current] || []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        distance[neighbor] = distance[current] + 1;
        queue.push(neighbor);
      }
    }
  }
  return distance;
}

const distances = bfsShortestPath(graph, 'A');
console.log(distances); // { A: 0, B: 1, C: 1, D: 2, E: 3 }

This code finds shortest distances from node A to all others in an unweighted graph using BFS.

Execution Table

Step	Operation	Current Node	Queue State	Visited Set	Distance Map	Visual State
1	Initialize	-	['A']	{A}	{A: 0}	A(0)
2	Dequeue	A	[]	{A}	{A: 0}	A(0)
3	Visit neighbor B	A	['B']	{A, B}	{A: 0, B: 1}	A(0) -> B(1)
4	Visit neighbor C	A	['B', 'C']	{A, B, C}	{A: 0, B: 1, C: 1}	A(0) -> B(1), C(1)
5	Dequeue	B	['C']	{A, B, C}	{A: 0, B: 1, C: 1}	A(0) -> B(1), C(1)
6	Visit neighbor D	B	['C', 'D']	{A, B, C, D}	{A: 0, B: 1, C: 1, D: 2}	A(0) -> B(1) -> D(2), C(1)
7	Dequeue	C	['D']	{A, B, C, D}	{A: 0, B: 1, C: 1, D: 2}	A(0) -> B(1) -> D(2), C(1)
8	Visit neighbor D (already visited)	C	['D']	{A, B, C, D}	{A: 0, B: 1, C: 1, D: 2}	No change
9	Dequeue	D	[]	{A, B, C, D}	{A: 0, B: 1, C: 1, D: 2}	A(0) -> B(1) -> D(2), C(1)
10	Visit neighbor E	D	['E']	{A, B, C, D, E}	{A: 0, B: 1, C: 1, D: 2, E: 3}	A(0) -> B(1) -> D(2) -> E(3), C(1)
11	Dequeue	E	[]	{A, B, C, D, E}	{A: 0, B: 1, C: 1, D: 2, E: 3}	All nodes visited
12	No neighbors to visit	E	[]	{A, B, C, D, E}	{A: 0, B: 1, C: 1, D: 2, E: 3}	Done

💡 Queue empty, all reachable nodes visited, shortest distances computed

Variable Tracker

Variable	Start	After 1	After 2	After 3	After 4	After 5	After 6	After 7	After 8	After 9	After 10	Final
Queue	['A']	[]	['B']	['B', 'C']	['C']	['C', 'D']	['D']	['D']	[]	['E']	[]	[]
Visited Set	{}	{A}	{A, B}	{A, B, C}	{A, B, C}	{A, B, C, D}	{A, B, C, D}	{A, B, C, D}	{A, B, C, D}	{A, B, C, D, E}	{A, B, C, D, E}	{A, B, C, D, E}
Distance Map	{}	{A:0}	{A:0, B:1}	{A:0, B:1, C:1}	{A:0, B:1, C:1}	{A:0, B:1, C:1, D:2}	{A:0, B:1, C:1, D:2}	{A:0, B:1, C:1, D:2}	{A:0, B:1, C:1, D:2}	{A:0, B:1, C:1, D:2, E:3}	{A:0, B:1, C:1, D:2, E:3}	{A:0, B:1, C:1, D:2, E:3}

Key Moments - 3 Insights

Why do we mark a neighbor as visited and set its distance only when we first see it?

Because BFS explores nodes level by level, the first time we visit a neighbor is the shortest path to it. Later visits are longer paths and ignored. See rows 3,4,6 in execution_table.

Why do we use a queue instead of a stack for BFS?

A queue ensures nodes are explored in order of their distance from the source, guaranteeing shortest paths. A stack would explore depth first, not shortest paths. See queue changes in variable_tracker.

What happens if the graph has disconnected nodes?

Nodes not reachable from the source remain unvisited and have no distance set. BFS only finds shortest paths to reachable nodes. In this example, all nodes are connected.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the distance assigned to node D?

A 1

B 3

C 2

D 0

💡 Hint

Check the Distance Map column at step 6 in execution_table

At which step does the queue become empty for the first time?

A Step 9

B Step 2

C Step 11

D Step 12

💡 Hint

Look at the Queue State column in execution_table to find when it is []

If node E had an additional neighbor F not connected to others, what would happen to the visited set?

A F would be visited if reachable from E

B F would never be visited

C F would be visited immediately

D Visited set would not change

💡 Hint

BFS visits all reachable nodes from source, so if F is neighbor of E, it will be visited after E

Concept Snapshot

Shortest Path in Unweighted Graph Using BFS:
- Use a queue to explore nodes level by level
- Mark nodes visited when first seen
- Distance = distance to current + 1
- Stops when queue empty
- Guarantees shortest path in unweighted graphs

Full Transcript

This visualization shows how BFS finds shortest paths in an unweighted graph. We start from the source node, add it to a queue, and mark its distance as zero. Then we repeatedly dequeue a node, visit its neighbors, and if a neighbor is not visited, we mark it visited, set its distance as current node distance plus one, and enqueue it. This process continues until the queue is empty, meaning all reachable nodes have their shortest distances computed. The queue ensures nodes are explored in order of increasing distance, guaranteeing shortest paths. The visited set prevents revisiting nodes and infinite loops. The distance map tracks shortest distance from source to each node. This method works only for unweighted graphs or graphs where all edges have equal weight.

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