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

↓

Mark visited

↓

Update distance & parent

↓

Enqueue neighbor

↓

Repeat loop

↓

End: shortest distances & paths ready

This flow shows how BFS explores nodes level by level from the source, updating shortest distances and parents to reconstruct paths.

Execution Sample

DSA Java

Queue<Integer> q = new LinkedList<>();
q.add(source);
distance[source] = 0;
visited[source] = true;
while (!q.isEmpty()) {
  int u = q.poll();
  for (int v : graph[u]) {
    if (!visited[v]) {
      visited[v] = true;
      distance[v] = distance[u] + 1;
      parent[v] = u;
      q.add(v);
    }
  }
}

This code runs BFS from the source node, updating shortest distances and parents for each reachable node.

Execution Table

Step	Operation	Current Node	Queue State	Visited Set	Distance Array	Parent Array	Visual State
1	Initialize	-	[0]	[0]	[0, ∞, ∞, ∞, ∞]	[-1, -1, -1, -1, -1]	Start at node 0, distance=0
2	Dequeue	0	[]	[0]	[0, ∞, ∞, ∞, ∞]	[-1, -1, -1, -1, -1]	Visiting node 0
3	Visit neighbor 1	0	[1]	[0,1]	[0,1, ∞, ∞, ∞]	[-1,0,-1,-1,-1]	Node 1 discovered from 0
4	Visit neighbor 2	0	[1,2]	[0,1,2]	[0,1,1, ∞, ∞]	[-1,0,0,-1,-1]	Node 2 discovered from 0
5	Dequeue	1	[2]	[0,1,2]	[0,1,1, ∞, ∞]	[-1,0,0,-1,-1]	Visiting node 1
6	Visit neighbor 3	1	[2,3]	[0,1,2,3]	[0,1,1,2, ∞]	[-1,0,0,1,-1]	Node 3 discovered from 1
7	Dequeue	2	[3]	[0,1,2,3]	[0,1,1,2, ∞]	[-1,0,0,1,-1]	Visiting node 2
8	Visit neighbor 4	2	[3,4]	[0,1,2,3,4]	[0,1,1,2,2]	[-1,0,0,1,2]	Node 4 discovered from 2
9	Dequeue	3	[4]	[0,1,2,3,4]	[0,1,1,2,2]	[-1,0,0,1,2]	Visiting node 3
10	No new neighbors	3	[4]	[0,1,2,3,4]	[0,1,1,2,2]	[-1,0,0,1,2]	Node 3 neighbors visited
11	Dequeue	4	[]	[0,1,2,3,4]	[0,1,1,2,2]	[-1,0,0,1,2]	Visiting node 4
12	No new neighbors	4	[]	[0,1,2,3,4]	[0,1,1,2,2]	[-1,0,0,1,2]	Node 4 neighbors visited
13	End	-	[]	[0,1,2,3,4]	[0,1,1,2,2]	[-1,0,0,1,2]	Queue empty, BFS complete

💡 Queue is empty, all reachable nodes visited, shortest distances and parents finalized

Variable Tracker

Variable	Start	After Step 3	After Step 4	After Step 6	After Step 8	Final
Queue	[]	[1]	[1,2]	[2,3]	[3,4]	[]
Visited Set	[]	[0,1]	[0,1,2]	[0,1,2,3]	[0,1,2,3,4]	[0,1,2,3,4]
Distance	[∞,∞,∞,∞,∞]	[0,1,∞,∞,∞]	[0,1,1,∞,∞]	[0,1,1,2,∞]	[0,1,1,2,2]	[0,1,1,2,2]
Parent	[-1,-1,-1,-1,-1]	[-1,0,-1,-1,-1]	[-1,0,0,-1,-1]	[-1,0,0,1,-1]	[-1,0,0,1,2]	[-1,0,0,1,2]

Key Moments - 3 Insights

Why do we mark a node as visited immediately when we enqueue it, not when we dequeue it?

Marking visited when enqueuing (see steps 3,4,6,8) prevents adding the same node multiple times to the queue, avoiding repeated processing and infinite loops.

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

Because BFS explores nodes level by level from the source (see queue states in execution_table), the first time we reach a node is via the shortest path.

What does the parent array represent and how is it used?

Parent array stores the node from which we discovered the current node (see parent updates in steps 3,4,6,8). It helps reconstruct the shortest path after BFS completes.

Visual Quiz - 3 Questions

Look at the execution table at step 4. What is the queue state?

A [1, 2]

B [2]

C [1]

D []

💡 Hint

Check the 'Queue State' column in row with Step 4 in execution_table

At which step does node 3 get marked visited?

A Step 3

B Step 6

C Step 8

D Step 10

💡 Hint

Look at 'Visited Set' and 'Operation' columns in execution_table rows

If we did not mark nodes visited when enqueuing, what would happen to the queue?

A Queue would only have the source node

B Queue would be empty immediately

C Queue would contain duplicate nodes

D Queue would never enqueue any nodes

💡 Hint

Refer to key_moments explanation about visited marking timing

Concept Snapshot

Shortest Path in Unweighted Graph Using BFS:
- Use a queue to explore nodes level by level
- Mark nodes visited when enqueued to avoid repeats
- Distance array stores shortest distance from source
- Parent array stores path information
- BFS guarantees shortest path in unweighted graphs

Full Transcript

This visualization shows how BFS finds the shortest path in an unweighted graph. We start from the source node, enqueue it, and mark it visited with distance zero. Then, while the queue is not empty, we dequeue a node and explore its neighbors. For each unvisited neighbor, we mark it visited, update its distance as current node distance plus one, set its parent to current node, and enqueue it. This process continues until all reachable nodes are visited. The distance array holds shortest distances, and the parent array helps reconstruct paths. Marking nodes visited when enqueued prevents duplicates and infinite loops. BFS explores nodes in layers, ensuring the first time a node is reached is via the shortest path.

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 node with the highest degree

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, 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 A

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 works only for weighted graphs

2. Which Java data structure is commonly used to implement BFS for shortest path in an unweighted graph?

easy

A. Queue

B. PriorityQueue

C. HashMap

D. Stack

Solution

1. Step 1: Recall BFS traversal order

   BFS explores nodes in a first-in, first-out order to visit neighbors level by level.

2. Step 2: Identify the correct data structure

   A Queue supports FIFO order, making it ideal for BFS traversal.

3. Final Answer:

   Queue -> Option A

4. Quick Check:

   BFS uses Queue for level order traversal [OK]

Hint: Use Queue for FIFO order in BFS traversal [OK]

Common Mistakes:

• Using Stack which is LIFO and suits DFS
• Confusing PriorityQueue with Queue
• Using HashMap which stores key-value pairs, not order

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

Graph edges:
0 - 1
0 - 2
1 - 3
2 - 3
3 - 4

Assume nodes are 0 to 4 and distance to start node is 0.

medium

A. [0, 0, 0, 0, 0]

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

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

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

Solution

1. Step 1: Start BFS from node 0 and set distance 0

   Distance[0] = 0. Neighbors 1 and 2 get distance 1.

2. Step 2: Visit neighbors of 1 and 2

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

3. Step 3: Visit neighbor of 3

   Node 4 is neighbor of 3, distance is 3.

4. Final Answer:

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

5. Quick Check:

   Distances increase by 1 per BFS level [OK]

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

Common Mistakes:

• Assigning wrong distances to node 3
• Confusing BFS with DFS distances
• Setting all distances to zero

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

int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
Queue<Integer> q = new LinkedList<>();
q.add(start);
dist[start] = 0;
while(!q.isEmpty()) {
  int u = q.poll();
  for(int v : graph.get(u)) {
    if(dist[v] == 0) {
      dist[v] = dist[u] + 1;
      q.add(v);
    }
  }
}

medium

A. The queue should be a Stack for BFS

B. Distance array should be initialized with zeros

C. The condition 'dist[v] == 0' should check for Integer.MAX_VALUE instead

D. The start node distance should be Integer.MAX_VALUE

Solution

1. Step 1: Understand distance initialization

   Distances are set to Integer.MAX_VALUE to mark unvisited nodes.

2. Step 2: Check visitation condition

   Condition 'dist[v] == 0' wrongly checks for zero, but unvisited nodes have Integer.MAX_VALUE.

3. Step 3: Correct condition

   Change condition to 'dist[v] == Integer.MAX_VALUE' to detect unvisited nodes properly.

4. Final Answer:

   The condition 'dist[v] == 0' should check for Integer.MAX_VALUE instead -> Option C

5. Quick Check:

   Check unvisited nodes by Integer.MAX_VALUE [OK]

Hint: Check unvisited nodes by initial max distance, not zero [OK]

Common Mistakes:

• Using zero to check unvisited nodes when distances initialized to max
• Using Stack instead of Queue for BFS
• Incorrect distance initialization

5. Given an unweighted graph with nodes 0 to 5 and edges:

0-1, 0-2, 1-3, 2-3, 3-4, 4-5

If BFS starts at node 0, what is the shortest path from node 0 to node 5?

hard

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

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

C. [0, 2, 3, 5]

D. [0, 2, 4, 5]

Solution

1. Step 1: Run BFS to find shortest distances

   Distances: 0->0, 1->1, 2->1, 3->2, 4->3, 5->4.

2. Step 2: Trace shortest path from 5 back to 0

   From 5 to 4, 4 to 3, 3 to 1 or 2, choose 1 for shortest path: 0->1->3->4->5.

3. Final Answer:

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

4. Quick Check:

   Shortest path follows BFS layers [OK]

Hint: Trace path backward from target using distances [OK]

Common Mistakes:

• Choosing longer paths ignoring BFS distances
• Skipping nodes in path
• Confusing BFS with DFS path