Shortest Path in Unweighted Graph Using BFS in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the queue with the start node.

DSA Go

queue := []int[1]

Drag options to blanks, or click blank then click option'

Astart

B0

Cnil

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing queue with 0 instead of start node

Starting with nil or empty queue

Using -1 which is invalid node

The BFS queue must start with the start node to begin traversal.

2fill in blank

medium

Complete the code to mark the start node as visited.

DSA Go

visited[start] = [1]

Drag options to blanks, or click blank then click option'

Afalse

Bnil

Ctrue

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Marking visited as false initially

Leaving visited uninitialized

Using 0 or nil instead of true

Marking the start node as visited prevents revisiting it during BFS.

3fill in blank

hard

Fix the error in the BFS loop condition to continue while queue is not empty.

DSA Go

for len(queue) [1] 0 {

Drag options to blanks, or click blank then click option'

A<

B>

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using '<' which stops immediately

Using '==' which runs only if empty

Using '!=' which is invalid for int comparison

The BFS loop runs while the queue length is greater than zero.

4fill in blank

hard

Fill both blanks to correctly update distance and enqueue neighbors.

DSA Go

if !visited[neighbor] {
    visited[neighbor] = true
    distance[neighbor] = distance[current] [1] 1
    queue = append(queue, [2])
}

Drag options to blanks, or click blank then click option'

A+

B-

C*

Dneighbor

Attempts:

3 left

💡 Hint

Common Mistakes

Using '-' or '*' instead of '+' for distance

Appending current instead of neighbor to queue

Distance to neighbor is current distance plus one, and neighbor is added to queue.

5fill in blank

hard

Fill all three blanks to return the shortest path distance or -1 if unreachable.

DSA Go

if distance[target] == [1] {
    return [2]
}
return [3]

Drag options to blanks, or click blank then click option'

A0

B-1

Cdistance[target]

Dnil

Attempts:

3 left

💡 Hint

Common Mistakes

Returning 0 instead of -1 for unreachable

Returning nil which is invalid

Returning distance[target] without checking

If distance[target] is 0 (unvisited except start), return -1 for unreachable; else return distance.

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