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.