Shortest Path in Unweighted Graph Using BFS in DSA Go

Mental Model

We find the shortest path by exploring neighbors level by level, like ripples spreading in water.

Analogy: Imagine you are in a maze and shout to find your friend. The sound reaches nearby rooms first, then rooms farther away, so the first time you hear your friend's shout, you know the shortest path.

Graph:
0 -> 1 -> 2
↓    ↓
3    4

Start at 0, explore neighbors 1 and 3 first, then their neighbors.

Dry Run Walkthrough

Input: Graph edges: 0-1, 0-3, 1-2, 1-4; Find shortest path from 0 to 4

Goal: Find the shortest path length from node 0 to node 4 using BFS

Step 1: Start BFS from node 0, mark distance[0] = 0

Queue: [0]
Distances: [0:0, 1:∞, 2:∞, 3:∞, 4:∞]

Why: We begin from the start node with distance zero

Step 2: Dequeue 0, enqueue neighbors 1 and 3, set distance[1]=1, distance[3]=1

Queue: [1, 3]
Distances: [0:0, 1:1, 2:∞, 3:1, 4:∞]

Why: Neighbors of 0 are one step away

Step 3: Dequeue 1, enqueue neighbors 2 and 4, set distance[2]=2, distance[4]=2

Queue: [3, 2, 4]
Distances: [0:0, 1:1, 2:2, 3:1, 4:2]

Why: Neighbors of 1 are two steps away from start

Step 4: Dequeue 3, no new neighbors to enqueue

Queue: [2, 4]
Distances unchanged

Why: 3 has no unvisited neighbors

Step 5: Dequeue 2, no new neighbors to enqueue

Queue: [4]
Distances unchanged

Why: 2 has no unvisited neighbors

Step 6: Dequeue 4, destination found with distance 2

Queue: []
Distances: [0:0, 1:1, 2:2, 3:1, 4:2]

Why: Reached target node, shortest path length is 2

Result:

Final distances: 0:0 -> 1:1 -> 2:2 -> 3:1 -> 4:2
Shortest path length from 0 to 4 is 2

Annotated Code

DSA Go

package main

import (
	"container/list"
	"fmt"
)

type Graph struct {
	adjacency map[int][]int
}

func NewGraph() *Graph {
	return &Graph{adjacency: make(map[int][]int)}
}

func (g *Graph) AddEdge(u, v int) {
	g.adjacency[u] = append(g.adjacency[u], v)
	g.adjacency[v] = append(g.adjacency[v], u) // undirected graph
}

func (g *Graph) ShortestPathBFS(start, target int) int {
	distance := make(map[int]int)
	for node := range g.adjacency {
		distance[node] = -1 // -1 means unvisited
	}
	distance[start] = 0

	queue := list.New()
	queue.PushBack(start)

	for queue.Len() > 0 {
		front := queue.Front()
		current := front.Value.(int)
		queue.Remove(front)

		if current == target {
			return distance[current] // found shortest path
		}

		for _, neighbor := range g.adjacency[current] {
			if distance[neighbor] == -1 {
				distance[neighbor] = distance[current] + 1 // update distance
				queue.PushBack(neighbor) // enqueue neighbor
			}
		}
	}

	return -1 // target not reachable
}

func main() {
	g := NewGraph()
	g.AddEdge(0, 1)
	g.AddEdge(0, 3)
	g.AddEdge(1, 2)
	g.AddEdge(1, 4)

	start, target := 0, 4
	distance := g.ShortestPathBFS(start, target)
	fmt.Printf("Shortest path length from %d to %d is %d\n", start, target, distance)
}

distance := make(map[int]int) for node := range g.adjacency { distance[node] = -1 // -1 means unvisited }

Initialize all nodes as unvisited with distance -1

distance[start] = 0

Set start node distance to zero

queue := list.New() queue.PushBack(start)

Initialize queue and enqueue start node

front := queue.Front() current := front.Value.(int) queue.Remove(front)

Dequeue current node for processing

if current == target { return distance[current] // found shortest path }

If target found, return distance immediately

for _, neighbor := range g.adjacency[current] { if distance[neighbor] == -1 { distance[neighbor] = distance[current] + 1 queue.PushBack(neighbor) } }

Visit unvisited neighbors, update distance, enqueue them

Output

Shortest path length from 0 to 4 is 2

Complexity Analysis

Time: O(V + E) because BFS visits each vertex and edge once

Space: O(V) for storing distances and queue

vs Alternative: Compared to DFS, BFS guarantees shortest path in unweighted graphs with similar time but DFS may not find shortest path

Edge Cases

Start node equals target node

Distance is zero immediately returned

DSA Go

if current == target {
	return distance[current] // found shortest path
}

Target node unreachable

Returns -1 indicating no path

DSA Go

return -1 // target not reachable

Graph with isolated nodes

Distances remain -1 for unreachable nodes

DSA Go

distance initialized to -1 for all nodes

When to Use This Pattern

When asked to find shortest path in an unweighted graph, use BFS because it explores nodes in order of distance from start.

Common Mistakes

Mistake: Not marking nodes as visited before enqueueing, causing repeated visits
Fix: Mark distance or visited status immediately when enqueueing neighbors

Mistake: Returning distance only after BFS completes instead of when target is found
Fix: Return distance as soon as target node is dequeued

Summary

Finds shortest path length in unweighted graphs using breadth-first search.

Use when you need the minimum number of edges between two nodes in an unweighted graph.

The key insight is BFS explores nodes in layers, so the first time you reach the target is the shortest path.

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