Shortest Path in Unweighted Graph Using BFS in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS Shortest Path Distances

What is the output of the following Go code that finds shortest path distances from node 0 in an unweighted graph?

DSA Go

package main

import (
	"fmt"
)

func bfsShortestPath(graph map[int][]int, start int) map[int]int {
	dist := make(map[int]int)
	for node := range graph {
		dist[node] = -1
	}
	dist[start] = 0
	queue := []int{start}

	for len(queue) > 0 {
		current := queue[0]
		queue = queue[1:]

		for _, neighbor := range graph[current] {
			if dist[neighbor] == -1 {
				dist[neighbor] = dist[current] + 1
				queue = append(queue, neighbor)
			}
		}
	}

	return dist
}

func main() {
	graph := map[int][]int{
		0: {1, 2},
		1: {0, 3},
		2: {0, 3, 4},
		3: {1, 2, 4},
		4: {2, 3},
	}
	distances := bfsShortestPath(graph, 0)
	fmt.Println(distances)
}

A {"0":0, "1":0, "2":1, "3":2, "4":2}

B {"0":0, "1":1, "2":1, "3":1, "4":2}

C {"0":0, "1":1, "2":2, "3":2, "4":3}

D {"0":0, "1":1, "2":1, "3":2, "4":2}

💡 Hint

Think about the shortest number of edges from node 0 to each node.

The BFS starts at node 0 with distance 0. Nodes 1 and 2 are directly connected, so distance 1. Nodes 3 and 4 are two edges away, so distance 2.

🧠 Conceptual

intermediate

Why BFS Finds Shortest Path in Unweighted Graphs

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

A Because BFS explores nodes level by level, ensuring the first time a node is visited is via the shortest path.

B Because BFS uses a priority queue to pick the closest node first.

C Because BFS backtracks to find all possible paths and picks the shortest.

D Because BFS uses recursion to explore all paths simultaneously.

💡 Hint

Think about the order in which BFS visits nodes.

BFS explores nodes in layers: all nodes at distance 1, then distance 2, and so on. The first time BFS visits a node, it is via the shortest path.

🔧 Debug

advanced

Identify the Bug in BFS Implementation

What error will this BFS code produce when run on a graph with nodes 0 to 3?

DSA Go

func bfsBuggy(graph map[int][]int, start int) map[int]int {
	dist := make(map[int]int)
	queue := []int{start}
	dist[start] = 0

	for len(queue) > 0 {
		current := queue[0]
		queue = queue[1:]

		for _, neighbor := range graph[current] {
			if dist[neighbor] == 0 {
				dist[neighbor] = dist[current] + 1
				queue = append(queue, neighbor)
			}
		}
	}

	return dist
}

A Incorrect distances because unvisited nodes are not detected properly

B KeyError or panic due to accessing dist[neighbor] when neighbor not in map

C Infinite loop because queue never empties

D No error, correct output

💡 Hint

Check how unvisited nodes are detected in the if condition.

The code uses dist[neighbor] == 0 to check if a node is unvisited. But the start node has distance 0, so other nodes with distance 0 are considered visited incorrectly. This causes wrong distances.

❓ Predict Output

advanced

Shortest Path Reconstruction Output

What is the output of the following Go code that reconstructs the shortest path from node 0 to node 4?

DSA Go

package main

import (
	"fmt"
)

func bfsWithParent(graph map[int][]int, start int) (map[int]int, map[int]int) {
	dist := make(map[int]int)
	parent := make(map[int]int)
	for node := range graph {
		dist[node] = -1
		parent[node] = -1
	}
	dist[start] = 0
	queue := []int{start}

	for len(queue) > 0 {
		current := queue[0]
		queue = queue[1:]

		for _, neighbor := range graph[current] {
			if dist[neighbor] == -1 {
				dist[neighbor] = dist[current] + 1
				parent[neighbor] = current
				queue = append(queue, neighbor)
			}
		}
	}

	return dist, parent
}

func reconstructPath(parent map[int]int, start, end int) []int {
	path := []int{}
	current := end
	for current != -1 {
		path = append([]int{current}, path...)
		current = parent[current]
	}
	if len(path) > 0 && path[0] == start {
		return path
	}
	return []int{}
}

func main() {
	graph := map[int][]int{
		0: {1, 2},
		1: {0, 3},
		2: {0, 3, 4},
		3: {1, 2, 4},
		4: {2, 3},
	}
	dist, parent := bfsWithParent(graph, 0)
	path := reconstructPath(parent, 0, 4)
	fmt.Println(path)
}

A [0 2 3 4]

B [0 1 3 4]

C [0 2 4]

D []

💡 Hint

Check the parent links from node 4 back to 0 after BFS.

The BFS visits node 2 before node 3 when exploring neighbors of 0. So the shortest path to 4 is 0 -> 2 -> 4.

🧠 Conceptual

expert

Time Complexity of BFS for Shortest Path

What is the time complexity of BFS when finding the shortest path in an unweighted graph with V vertices and E edges?

A O(E^2)

B O(V + E)

C O(V * E)

D O(V^2)

💡 Hint

Consider how many times each vertex and edge is processed.

BFS visits each vertex once and explores all edges from each vertex once, so total time is proportional to vertices plus edges.

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