Shortest Path in Unweighted Graph Using BFS in DSA Go - Build from Scratch

Shortest Path in Unweighted Graph Using BFS

📖 Scenario: Imagine you are navigating a city with intersections connected by roads. You want to find the shortest number of roads to travel from one intersection to another.

🎯 Goal: Build a program that finds the shortest path length between two intersections in an unweighted graph using Breadth-First Search (BFS).

📋 What You'll Learn

Create a graph as an adjacency list with exact nodes and edges

Add variables for the start and target intersections

Implement BFS to find the shortest path length

Print the shortest path length from start to target

💡 Why This Matters

🌍 Real World

Finding shortest routes in maps, social networks, or any system modeled as connections without weights.

💼 Career

Understanding BFS and shortest path algorithms is essential for software engineers working on navigation, recommendation systems, and network analysis.

1

Create the graph as an adjacency list

Create a variable called graph of type map[int][]int with these exact entries: 1: []int{2, 3}, 2: []int{1, 4, 5}, 3: []int{1, 6}, 4: []int{2}, 5: []int{2, 6}, 6: []int{3, 5}

DSA Go

graph := map[int][]int{
    // Your code here
}

Hint

Use a map where keys are intersection numbers and values are slices of connected intersections.

2

Set start and target intersections

Create two variables: start with value 1 and target with value 6

DSA Go

package main

import "fmt"

func main() {
    graph := map[int][]int{
        1: []int{2, 3},
        2: []int{1, 4, 5},
        3: []int{1, 6},
        4: []int{2},
        5: []int{2, 6},
        6: []int{3, 5},
    }
    // Your code here
}

Hint

Use simple integer variables to store the start and target intersections.

3

Implement BFS to find shortest path length

Write a BFS loop using a queue to find the shortest path length from start to target. Use a map called visited to track visited nodes and a map called distance to store distances. Initialize visited[start] = true and distance[start] = 0. Loop until queue is empty or target is found. Update distance for neighbors and mark them visited.

DSA Go

package main

import "fmt"

func main() {
    graph := map[int][]int{
        1: []int{2, 3},
        2: []int{1, 4, 5},
        3: []int{1, 6},
        4: []int{2},
        5: []int{2, 6},
        6: []int{3, 5},
    }
    start := 1
    target := 6

    // Your code here
}

Hint

Use a queue slice to hold nodes to visit. Mark nodes visited and track distance from start.

4

Print the shortest path length

Print the shortest path length from start to target using fmt.Println(distance[target])

DSA Go

package main

import "fmt"

func main() {
    graph := map[int][]int{
        1: []int{2, 3},
        2: []int{1, 4, 5},
        3: []int{1, 6},
        4: []int{2},
        5: []int{2, 6},
        6: []int{3, 5},
    }
    start := 1
    target := 6

    visited := make(map[int]bool)
    distance := make(map[int]int)
    queue := []int{start}
    visited[start] = true
    distance[start] = 0

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

        if current == target {
            break
        }

        for _, neighbor := range graph[current] {
            if !visited[neighbor] {
                visited[neighbor] = true
                distance[neighbor] = distance[current] + 1
                queue = append(queue, neighbor)
            }
        }
    }

    // Your code here
}

Hint

The shortest path length from intersection 1 to 6 is 2 roads.

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