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

↓

Set distance = current distance + 1

↓

Enqueue neighbor

↓

Repeat loop

↓

End when all reachable nodes processed

↓

Shortest distances from source ready

Start BFS from source node, explore neighbors level by level, track distances to find shortest path in unweighted graph.

Execution Sample

DSA Go

graph := map[string][]string{
  "A": {"B", "C"},
  "B": {"A", "D"},
  "C": {"A", "D"},
  "D": {"B", "C", "E"},
  "E": {"D"},
}
dist := BFSShortestPath(graph, "A")

This code runs BFS on an unweighted graph from node A to find shortest distances to all nodes.

Execution Table

Step	Operation	Current Node	Queue State	Visited Set	Distance Map	Visual State
1	Initialize	-	[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 A	B	[C]	{"A", "B", "C"}	{"A":0, "B":1, "C":1}	A(0) -> B(1), C(1) (A visited)
7	Visit neighbor D	B	[C, D]	{"A", "B", "C", "D"}	{"A":0, "B":1, "C":1, "D":2}	A(0) -> B(1), C(1), D(2)
8	Dequeue	C	[D]	{"A", "B", "C", "D"}	{"A":0, "B":1, "C":1, "D":2}	A(0) -> B(1), C(1), D(2)
9	Visit neighbor A	C	[D]	{"A", "B", "C", "D"}	{"A":0, "B":1, "C":1, "D":2}	A(0) -> B(1), C(1), D(2) (A visited)
10	Visit neighbor D	C	[D]	{"A", "B", "C", "D"}	{"A":0, "B":1, "C":1, "D":2}	A(0) -> B(1), C(1), D(2) (D visited)
11	Dequeue	D	[]	{"A", "B", "C", "D"}	{"A":0, "B":1, "C":1, "D":2}	A(0) -> B(1), C(1), D(2)
12	Visit neighbor B	D	[]	{"A", "B", "C", "D"}	{"A":0, "B":1, "C":1, "D":2}	A(0) -> B(1), C(1), D(2) (B visited)
13	Visit neighbor C	D	[]	{"A", "B", "C", "D"}	{"A":0, "B":1, "C":1, "D":2}	A(0) -> B(1), C(1), D(2) (C visited)
14	Visit neighbor E	D	[E]	{"A", "B", "C", "D", "E"}	{"A":0, "B":1, "C":1, "D":2, "E":3}	A(0) -> B(1), C(1), D(2), E(3)
15	Dequeue	E	[]	{"A", "B", "C", "D", "E"}	{"A":0, "B":1, "C":1, "D":2, "E":3}	A(0) -> B(1), C(1), D(2), E(3)
16	Visit neighbor D	E	[]	{"A", "B", "C", "D", "E"}	{"A":0, "B":1, "C":1, "D":2, "E":3}	A(0) -> B(1), C(1), D(2), E(3) (D visited)
17	Queue empty	-	[]	{"A", "B", "C", "D", "E"}	{"A":0, "B":1, "C":1, "D":2, "E":3}	Traversal complete
18	End	-	-	-	-	All shortest distances found

💡 Queue is empty, all reachable nodes visited, BFS ends

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 7	After Step 11	After Step 14	Final
Queue	[A]	[]	[B, C]	[C, D]	[]	[E]	[]
Visited Set	{}	{"A"}	{"A", "B", "C"}	{"A", "B", "C", "D"}	{"A", "B", "C", "D"}	{"A", "B", "C", "D", "E"}	{"A", "B", "C", "D", "E"}
Distance Map	{}	{"A":0}	{"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, "E":3}	{"A":0, "B":1, "C":1, "D":2, "E":3}

Key Moments - 3 Insights

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

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

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

Because BFS explores nodes level by level from the source (see visual state after steps 4, 7, 14), the first time we reach a node is via the shortest path.

What happens if the graph has disconnected nodes?

Nodes not reachable from the source won't be visited or in the distance map, as BFS only explores connected components (not shown in this example).

Visual Quiz - 3 Questions

Look at the execution table at step 7. What is the distance assigned to node D?

A 2

B 1

C 3

D 0

💡 Hint

Check the 'Distance Map' column at step 7 in the execution table.

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

A Step 17

B Step 11

C Step 2

D Step 14

💡 Hint

Look at the 'Queue State' column to find when it first shows [].

If we start BFS from node E instead of A, what would be the distance to node A?

A 1

B 3

C 0

D Not reachable

💡 Hint

Consider the shortest path length from E to A in the graph structure.

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 to neighbors = current node distance + 1
- BFS guarantees shortest path in unweighted graphs
- Stops when queue is empty (all reachable nodes visited)

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 with distance zero. Then, we repeatedly dequeue nodes, visit their neighbors, and enqueue unvisited neighbors while marking their distance as current node distance plus one. This process continues until the queue is empty, meaning all reachable nodes have been processed. The distance map at the end shows the shortest distance from the source to each node. Key points include marking nodes visited when enqueued to avoid duplicates and BFS's level-by-level exploration ensuring shortest paths. The execution table tracks the queue, visited set, and distance map at each step, showing how the graph is explored visually.

Practice

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

easy

A. The node with the highest degree

B. The longest path in the graph

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

D. The minimum spanning tree

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 C

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 paths
• Mixing BFS with minimum spanning tree algorithms

2. Which Go data structure is best to implement the queue needed for BFS?

easy

A. map

B. channel

C. struct

D. slice

Solution

1. Step 1: Identify queue requirements in BFS

   BFS requires a FIFO (first-in, first-out) structure to process nodes in order.

2. Step 2: Use slice as queue in Go

   Slices can be used to append at the end and remove from the front, effectively acting as a queue.

3. Final Answer:

   slice -> Option D

4. Quick Check:

   Queue for BFS = slice [OK]

Hint: Use slice with append and slicing for queue in Go [OK]

Common Mistakes:

• Using map which is unordered
• Using struct without queue logic
• Using channel without concurrency context

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

graph := [][]int{
  {1, 2},
  {0, 3},
  {0, 3},
  {1, 2, 4},
  {3},
}

medium

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

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

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

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

Solution

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

   Distance[0] = 0, others = -1 (unvisited). Queue starts with 0.

2. Step 2: Visit neighbors level by level

   From 0: neighbors 1 and 2 get distance 1. From 1 and 2: neighbor 3 gets distance 2. From 3: neighbor 4 gets distance 3.

3. Final Answer:

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

4. Quick Check:

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

Hint: Track BFS layers to assign distances incrementally [OK]

Common Mistakes:

• Assigning wrong distances to neighbors
• Confusing node indices
• Not initializing distances properly

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

func BFS(graph [][]int, start int) []int {
  dist := make([]int, len(graph))
  for i := range dist {
    dist[i] = -1
  }
  dist[start] = 0
  queue := []int{start}
  for len(queue) > 0 {
    node := queue[0]
    queue = queue[1:]
    for _, neighbor := range graph[node] {
      if dist[neighbor] == 0 {
        dist[neighbor] = dist[node] + 1
        queue = append(queue, neighbor)
      }
    }
  }
  return dist
}

medium

A. dist[neighbor] == 0 should be dist[neighbor] == -1

B. queue initialization is wrong

C. dist[start] should be -1

D. for loop over neighbors is incorrect

Solution

1. Step 1: Check distance initialization and visit condition

   Distances start at -1 for unvisited nodes. The condition to visit neighbors should check for -1, not 0.

2. Step 2: Fix condition to correctly detect unvisited neighbors

   Change if dist[neighbor] == 0 to if dist[neighbor] == -1 to avoid skipping nodes.

3. Final Answer:

   dist[neighbor] == 0 should be dist[neighbor] == -1 -> Option A

4. Quick Check:

   Check unvisited with -1, not 0 [OK]

Hint: Use -1 to mark unvisited nodes in BFS distance array [OK]

Common Mistakes:

• Checking visited nodes incorrectly
• Initializing distances with zero
• Modifying queue incorrectly

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, 2, 3, 4, 5]

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

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

D. [0, 2, 4, 5]

Solution

1. Step 1: Explore neighbors from node 0

   From 0, neighbors are 1 and 2. Both at distance 1.

2. Step 2: Explore neighbors from 1 and 2

   From 1: neighbor 3; from 2: neighbor 3. Node 3 is at distance 2.

3. Step 3: Explore neighbors from 3, then 4, then 5

   From 3: neighbor 4 (distance 3). From 4: neighbor 5 (distance 4). Path is 0->1->3->4->5 or 0->2->3->4->5.

4. Step 4: Choose shortest path with earliest discovery

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

5. Final Answer:

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

6. Quick Check:

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

Hint: BFS finds shortest path by earliest node discovery [OK]

Common Mistakes:

• Choosing longer paths ignoring BFS order
• Skipping nodes in path reconstruction
• Confusing path with distance array