BFS Breadth First Search on Graph in DSA Go

Mental Model

BFS explores all neighbors of a node before moving to the next level, like spreading out evenly in waves.

Analogy: Imagine you are in a building and want to visit every room floor by floor, starting from the entrance. You first check all rooms on the first floor, then all rooms on the second floor, and so on.

Start:
Entrance
  ↓
Neighbors at level 1
  ↓
Neighbors at level 2
  ↓
...

Graph nodes connected by edges:
1 -> 2 -> 3
↓    ↓
4    5

BFS visits nodes level by level.

Dry Run Walkthrough

Input: Graph: 1 connected to 2 and 4; 2 connected to 3 and 5; Start BFS from node 1

Goal: Visit all nodes reachable from node 1 in breadth-first order

Step 1: Start at node 1, mark visited, enqueue 1

Queue: [1]
Visited: {1}

Why: We begin BFS from the start node

Step 2: Dequeue 1, visit neighbors 2 and 4, mark visited and enqueue them

Queue: [2, 4]
Visited: {1, 2, 4}

Why: Explore all neighbors of node 1 before moving deeper

Step 3: Dequeue 2, visit neighbors 3 and 5, mark visited and enqueue them

Queue: [4, 3, 5]
Visited: {1, 2, 3, 4, 5}

Why: Explore neighbors of node 2 next

Step 4: Dequeue 4, no new neighbors to visit

Queue: [3, 5]
Visited: {1, 2, 3, 4, 5}

Why: Node 4 has no unvisited neighbors

Step 5: Dequeue 3, no new neighbors to visit

Queue: [5]
Visited: {1, 2, 3, 4, 5}

Why: Node 3 has no unvisited neighbors

Step 6: Dequeue 5, no new neighbors to visit

Queue: []
Visited: {1, 2, 3, 4, 5}

Why: Node 5 has no unvisited neighbors

Result:

Visited order: 1 -> 2 -> 4 -> 3 -> 5

Annotated Code

DSA Go

package main

import (
	"container/list"
	"fmt"
)

// Graph represents a graph using adjacency list
type Graph struct {
	adj map[int][]int
}

// NewGraph creates a new graph
func NewGraph() *Graph {
	return &Graph{adj: make(map[int][]int)}
}

// AddEdge adds an edge from u to v
func (g *Graph) AddEdge(u, v int) {
	g.adj[u] = append(g.adj[u], v)
}

// BFS performs breadth-first search starting from start node
func (g *Graph) BFS(start int) []int {
	visited := make(map[int]bool)
	queue := list.New()
	order := []int{}

	visited[start] = true
	queue.PushBack(start) // enqueue start

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

		order = append(order, curr) // visit node

		for _, neighbor := range g.adj[curr] {
			if !visited[neighbor] {
				visited[neighbor] = true
				queue.PushBack(neighbor) // enqueue neighbor
			}
		}
	}

	return order
}

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

	order := g.BFS(1)
	for i, node := range order {
		if i > 0 {
			fmt.Print(" -> ")
		}
		fmt.Print(node)
	}
	fmt.Println()
}

visited[start] = true queue.PushBack(start) // enqueue start

Mark start node visited and enqueue it to begin BFS

front := queue.Front() curr := front.Value.(int) queue.Remove(front) // dequeue

Dequeue the front node to visit it

order = append(order, curr) // visit node

Record the current node as visited in BFS order

for _, neighbor := range g.adj[curr] { if !visited[neighbor] { visited[neighbor] = true queue.PushBack(neighbor) // enqueue neighbor } }

Enqueue all unvisited neighbors to visit them next

Output

1 -> 2 -> 4 -> 3 -> 5

Complexity Analysis

Time: O(V + E) because we visit every vertex and edge once in BFS

Space: O(V) for the queue and visited map to track nodes

vs Alternative: Compared to DFS which uses a stack or recursion, BFS uses a queue and explores level by level, which is better for shortest path in unweighted graphs

Edge Cases

Empty graph (no nodes)

BFS returns an order containing only the start node, treating it as an isolated node

DSA Go

visited[start] = true

Start node with no neighbors

BFS visits only the start node and stops

DSA Go

for _, neighbor := range g.adj[curr]

Graph with disconnected nodes

BFS visits only nodes reachable from start node

DSA Go

visited[start] = true

When to Use This Pattern

When you need to explore nodes layer by layer or find shortest paths in unweighted graphs, BFS is the pattern to use because it visits neighbors first before going deeper.

Common Mistakes

Mistake: Not marking nodes as visited before enqueueing, causing repeated visits
Fix: Mark nodes visited immediately when enqueueing to avoid duplicates

Mistake: Using stack instead of queue, which changes BFS to DFS
Fix: Use a queue data structure to maintain BFS order

Summary

BFS visits all nodes reachable from a start node in order of their distance (levels).

Use BFS when you want to explore nodes level by level or find shortest paths in unweighted graphs.

The key insight is to use a queue to explore neighbors before moving deeper.

Practice

1. What is the main purpose of BFS (Breadth First Search) on a graph?

easy

A. To sort nodes in descending order

B. To find the shortest path using depth-first traversal

C. To explore all nodes level by level starting from a source node

D. To find cycles in a graph using recursion

Solution

1. Step 1: Understand BFS traversal

   BFS explores nodes by visiting all neighbors of a node before moving to the next level.

2. Step 2: Compare BFS with other traversals

   Unlike DFS, BFS uses a queue to explore nodes level by level, which helps in shortest path problems.

3. Final Answer:

   To explore all nodes level by level starting from a source node -> Option C

4. Quick Check:

   BFS = Level-wise exploration [OK]

Hint: BFS uses a queue to explore nodes level by level [OK]

Common Mistakes:

• Confusing BFS with DFS
• Thinking BFS uses recursion
• Assuming BFS sorts nodes

2. Which of the following Go code snippets correctly initializes a queue for BFS traversal?

easy

A. queue := []int{} // empty slice as queue

B. queue := make(map[int]bool) // map as queue

C. queue := 0 // integer as queue

D. queue := make(chan int) // channel as queue

Solution

1. Step 1: Identify data structure for BFS queue

   BFS requires a FIFO structure; a slice can be used as a queue in Go.

2. Step 2: Check each option

   queue := []int{} // empty slice as queue uses a slice which can enqueue and dequeue elements. queue := make(map[int]bool) // map as queue is a map, not suitable as queue. queue := 0 // integer as queue is an int, not a queue. queue := make(chan int) // channel as queue is a channel, which can be used but requires goroutines and is complex.

3. Final Answer:

   queue := []int{} // empty slice as queue -> Option A

4. Quick Check:

   Slice as queue = queue := []int{} // empty slice as queue [OK]

Hint: Use slice for queue in BFS, not map or int [OK]

Common Mistakes:

• Using map instead of slice for queue
• Using int variable as queue
• Confusing channels with simple queue

3. What is the output of the following Go BFS traversal code on the graph below?

Graph edges:
0 -> 1, 2
1 -> 2
2 -> 0, 3
3 -> 3

package main
import "fmt"
func bfs(graph map[int][]int, start int) []int {
    visited := make(map[int]bool)
    queue := []int{start}
    order := []int{}
    visited[start] = true
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        order = append(order, node)
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                visited[neighbor] = true
                queue = append(queue, neighbor)
            }
        }
    }
    return order
}
func main() {
    graph := map[int][]int{
        0: {1, 2},
        1: {2},
        2: {0, 3},
        3: {3},
    }
    fmt.Println(bfs(graph, 2))
}

medium

A. [2, 0, 1, 3]

B. [2, 0, 3, 1]

C. [2, 3, 0, 1]

D. [2, 1, 0, 3]

Solution

1. Step 1: Start BFS from node 2

   Initialize queue=[2], visited={2}. Dequeue 2, enqueue neighbors 0 and 3. order=[2]

2. Step 2: Process nodes in queue

   Queue=[0,3]. Dequeue 0, enqueue neighbor 1 (2 already visited). order=[2,0]. Queue=[3,1]. Dequeue 3, neighbor 3 already visited. order=[2,0,3]. Queue=[1]. Dequeue 1, neighbor 2 visited. order=[2,0,3,1]. Queue empty.

3. Final Answer:

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

4. Quick Check:

   BFS order from 2 = [2,0,3,1] [OK]

Hint: Track queue and visited sets stepwise [OK]

Common Mistakes:

• Not marking visited before enqueue
• Wrong order of neighbors enqueued
• Confusing BFS with DFS order

4. Identify the bug in the following BFS Go code snippet and select the correct fix.

func bfs(graph map[int][]int, start int) []int {
    visited := make(map[int]bool)
    queue := []int{start}
    order := []int{}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        order = append(order, node)
        for _, neighbor := range graph[node] {
            if !visited[neighbor] {
                queue = append(queue, neighbor)
                visited[neighbor] = true
            }
        }
    }
    return order
}

medium

A. Mark start node as visited before loop

B. Initialize order slice with capacity

C. Use a stack instead of queue

D. Remove visited map entirely

Solution

1. Step 1: Check visited marking for start node

   The code never marks the start node as visited before starting, so it may revisit it.

2. Step 2: Fix by marking start visited before loop

   Adding visited[start] = true before the loop prevents revisiting the start node and infinite loops.

3. Final Answer:

   Mark start node as visited before loop -> Option A

4. Quick Check:

   Start visited before loop = Mark start node as visited before loop [OK]

Hint: Always mark start visited before BFS loop [OK]

Common Mistakes:

• Marking visited after enqueue
• Using stack instead of queue
• Ignoring visited map

5. Given a directed graph represented as adjacency list, how can BFS be adapted to find the shortest path length from a start node to a target node? Choose the best approach.

hard

A. Use BFS but enqueue nodes multiple times to find shortest path

B. Use DFS and backtrack to find all paths, then pick shortest

C. Use BFS but ignore visited nodes to explore all paths

D. Use BFS with a distance map to track levels from start, stop when target found

Solution

1. Step 1: Understand BFS for shortest path

   BFS explores nodes level by level, so the first time target is reached is the shortest path.

2. Step 2: Use a distance map to track levels

   Maintain a map to record distance from start for each node. When target is dequeued, return its distance.

3. Final Answer:

   Use BFS with a distance map to track levels from start, stop when target found -> Option D

4. Quick Check:

   BFS + distance map = shortest path [OK]

Hint: Track distance in BFS, stop at target [OK]

Common Mistakes:

• Using DFS for shortest path in unweighted graph
• Ignoring visited nodes causing infinite loops
• Enqueuing nodes multiple times unnecessarily