Shortest Path in Unweighted Graph Using BFS in DSA Javascript - 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 of current

↓

If neighbor not visited

↓

Mark visited, set parent

↓

Enqueue neighbor

↓

Repeat until queue empty

↓

Build shortest path using parent pointers

↓

Return shortest path

Start BFS from source node, visit neighbors level by level, track parents to reconstruct shortest path.

Execution Sample

DSA Javascript

const bfsShortestPath = (graph, start, end) => {
  const queue = [start];
  const visited = new Set([start]);
  const parent = {};
  while (queue.length) {
    const node = queue.shift();
    if (node === end) break;
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        parent[neighbor] = node;
        queue.push(neighbor);
      }
    }
  }
  if (!visited.has(end)) {
    return [];
  }
  const path = [];
  let current = end;
  while (current !== undefined) {
    path.push(current);
    current = parent[current];
  }
  return path.reverse();
};

This code finds the shortest path between two nodes in an unweighted graph using BFS.

Execution Table

Step	Operation	Current Node	Queue	Visited Set	Parent Map	Visual State
1	Initialize	-	[A]	{A}	{}	Graph: A-B-C-D-E-F Queue: [A] Visited: {A}
2	Dequeue	A	[]	{A}	{}	Visit A Queue empty
3	Explore neighbors of A	A	[B, D]	{A,B,D}	{B:A, D:A}	Enqueue B and D Queue: [B, D]
4	Dequeue	B	[D]	{A,B,D}	{B:A, D:A}	Visit B Queue: [D]
5	Explore neighbors of B	B	[D, C]	{A,B,C,D}	{B:A, D:A, C:B}	Enqueue C Queue: [D, C]
6	Dequeue	D	[C]	{A,B,C,D}	{B:A, D:A, C:B}	Visit D Queue: [C]
7	Explore neighbors of D	D	[C, E]	{A,B,C,D,E}	{B:A, D:A, C:B, E:D}	Enqueue E Queue: [C, E]
8	Dequeue	C	[E]	{A,B,C,D,E}	{B:A, D:A, C:B, E:D}	Visit C Queue: [E]
9	Explore neighbors of C	C	[E, F]	{A,B,C,D,E,F}	{B:A, D:A, C:B, E:D, F:C}	Enqueue F Queue: [E, F]
10	Dequeue	E	[F]	{A,B,C,D,E,F}	{B:A, D:A, C:B, E:D, F:C}	Visit E Queue: [F]
11	Explore neighbors of E	E	[F]	{A,B,C,D,E,F}	{B:A, D:A, C:B, E:D, F:C}	Neighbors visited Queue unchanged
12	Dequeue	F	[]	{A,B,C,D,E,F}	{B:A, D:A, C:B, E:D, F:C}	Visit F Queue empty Reached target
13	Build path	-	-	-	{B:A, D:A, C:B, E:D, F:C}	Path: F -> C -> B -> A Reverse to A -> B -> C -> F

💡 Queue empty or target node F reached, BFS ends

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	After Step 12	Final
queue	[A]	[B, D]	[D, C]	[C, E]	[E, F]	[]	[]
visited	{A}	{A,B,D}	{A,B,C,D}	{A,B,C,D,E}	{A,B,C,D,E,F}	{A,B,C,D,E,F}	{A,B,C,D,E,F}
parent	{}	{B:A, D:A}	{B:A, D:A, C:B}	{B:A, D:A, C:B, E:D}	{B:A, D:A, C:B, E:D, F:C}	{B:A, D:A, C:B, E:D, F:C}	{B:A, D:A, C:B, E:D, F:C}
current	-	A	B	D	C	F	-

Key Moments - 3 Insights

Why do we mark a neighbor as visited before enqueueing it?

Marking neighbors as visited before enqueueing (see Step 3, 5, 7, 9) prevents adding the same node multiple times to the queue, avoiding repeated visits and infinite loops.

How do we reconstruct the shortest path after BFS ends?

We use the parent map built during BFS (see Step 13) to trace back from the target node to the start node, then reverse the collected path to get the shortest path.

Why does BFS guarantee the shortest path in an unweighted graph?

Because BFS explores nodes level by level, the first time we reach the target node (Step 12), we have found the shortest path in terms of number of edges.

Visual Quiz - 3 Questions

Look at the execution table at Step 7. What nodes are in the queue after exploring neighbors of D?

A [D, E]

B [E]

C [C, E]

D [B, C]

💡 Hint

Check the 'Queue' column at Step 7 in the execution_table.

At which step does the BFS reach the target node F?

A Step 9

B Step 12

C Step 10

D Step 13

💡 Hint

Look for 'Reached target' note in the 'Visual State' column.

If we did not mark nodes as visited before enqueueing, what would happen to the queue size?

A Queue size could grow with duplicates

B Queue size would stay the same

C Queue would be empty immediately

D Queue would only contain the start node

💡 Hint

Refer to the 'key_moments' about marking visited nodes before enqueueing.

Concept Snapshot

Shortest Path in Unweighted Graph Using BFS:
- Use a queue to explore nodes level by level
- Track visited nodes to avoid repeats
- Keep parent pointers to reconstruct path
- BFS guarantees shortest path by first reach
- Stop when target node is dequeued
- Rebuild path by backtracking parents

Full Transcript

This visualization shows how BFS finds the shortest path in an unweighted graph. We start from the source node, add it to a queue, and mark it visited. Then we repeatedly dequeue nodes, explore their neighbors, and enqueue unvisited neighbors while marking them visited and recording their parent nodes. This process continues until the target node is reached or the queue is empty. The parent map allows us to reconstruct the shortest path by backtracking from the target to the source. BFS explores nodes in layers, ensuring the first time we reach the target is via the shortest path. The execution table tracks queue contents, visited nodes, parent relationships, and current node at each step, showing how the graph is explored and the path is built.

Practice

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

easy

A. The longest path between two nodes

B. The node with the highest degree

C. The total number of nodes in the graph

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

Solution

1. Step 1: Understand BFS traversal

   BFS explores nodes level by level starting from the source node, visiting all neighbors before moving deeper.

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

   Because BFS visits nodes in order of increasing distance, the first time it reaches a node is via the shortest path.

3. Final Answer:

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

4. Quick Check:

   BFS = shortest path in unweighted graph [OK]

Hint: BFS visits nodes by distance layers to find shortest paths [OK]

Common Mistakes:

• Confusing BFS with DFS for shortest path
• Thinking BFS finds longest path
• Assuming BFS counts total nodes only

2. Which JavaScript data structure is best to implement the BFS queue for shortest path?

easy

A. Map to store node distances

B. Array with push and shift methods

C. Set to store unique nodes

D. Object with key-value pairs

Solution

1. Step 1: Identify BFS queue operations

   BFS requires adding nodes at the end and removing from the front, which is a queue behavior.

2. Step 2: Use Array methods for queue

   JavaScript arrays support push (add end) and shift (remove front), perfect for BFS queue.

3. Final Answer:

   Array with push and shift methods -> Option B

4. Quick Check:

   Queue = Array push/shift [OK]

Hint: Use array push/shift for BFS queue in JavaScript [OK]

Common Mistakes:

• Using Set as queue (no order guaranteed)
• Using Map for queue operations
• Using Object which has no order

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

const graph = {
  0: [1, 2],
  1: [0, 3],
  2: [0, 3],
  3: [1, 2, 4],
  4: [3]
};
// BFS from node 0

medium

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

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

C. [0, 1, 1, 2, 3]

D. [0, 2, 2, 3, 4]

Solution

1. Step 1: Initialize distances and start BFS

   Distance to start node 0 is 0. Neighbors 1 and 2 get distance 1.

2. Step 2: Visit neighbors of 1 and 2

   Node 3 is neighbor of 1 and 2, so distance is 2. Node 4 is neighbor of 3, distance 3.

3. Final Answer:

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

4. Quick Check:

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

Hint: Distance increments by 1 each BFS layer [OK]

Common Mistakes:

• Assigning wrong distances to neighbors
• Mixing up node indices
• Forgetting to update distance only once

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

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

medium

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

B. Distances should be initialized with -1

C. Neighbors should be checked before pushing start node

D. Queue should be a Set to avoid duplicates

Solution

1. Step 1: Check queue operations in BFS

   BFS requires FIFO order, so nodes must be removed from front using shift(), not pop() which removes from end.

2. Step 2: Effect of using pop()

   Using pop() makes it LIFO, turning BFS into DFS order, breaking shortest path logic.

3. Final Answer:

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

4. Quick Check:

   Queue removal must be shift() for BFS [OK]

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

Common Mistakes:

• Using pop() instead of shift() for queue
• Initializing distances incorrectly
• Using Set for queue which loses order

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

hard

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

B. [0, 2, 3, 4, 5]

C. [0, 1, 2, 3, 4, 5]

D. [0, 2, 4, 5]

Solution

1. Step 1: Explore neighbors from node 0

   Neighbors are 1 and 2, both distance 1.

2. Step 2: From neighbors, explore node 3

   Node 3 is neighbor of both 1 and 2, distance 2.

3. Step 3: From node 3, go to 4 then 5

   Node 4 distance 3, node 5 distance 4. The path via 1 is [0,1,3,4,5].

4. Final Answer:

   [0, 1, 3, 4, 5] -> Option A

5. Quick Check:

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

Hint: Trace BFS layers from start to target [OK]

Common Mistakes:

• Choosing longer paths ignoring BFS order
• Skipping nodes in path
• Confusing edges and neighbors