BFS Breadth First Search on Graph in DSA Go - Execution Trace

Concept Flow - BFS Breadth First Search on Graph

Start at source node

↓

Mark node visited

↓

Add node neighbors to queue if not visited

↓

Dequeue next node from queue

↓

Repeat until queue empty

↓

End: All reachable nodes visited

BFS starts at a node, visits neighbors level by level using a queue until all reachable nodes are visited.

Execution Sample

DSA Go

graph := map[string][]string{
  "A": {"B", "C"},
  "B": {"D"},
  "C": {"E"},
  "D": {},
  "E": {},
}
BFS(graph, "A")

Perform BFS starting from node A on a simple graph.

Execution Table

Step	Operation	Current Node	Queue State	Visited Set	Action Taken	Visual State
1	Start BFS	A	[A]	{A}	Mark A visited, enqueue neighbors B, C	A(visited) in queue
2	Dequeue	A	[B, C]	{A, B, C}	Visit A, enqueue B and C	Visited: A, B, C; Queue: B, C
3	Dequeue	B	[C, D]	{A, B, C, D}	Visit B, enqueue D	Visited: A, B, C, D; Queue: C, D
4	Dequeue	C	[D, E]	{A, B, C, D, E}	Visit C, enqueue E	Visited: A, B, C, D, E; Queue: D, E
5	Dequeue	D	[E]	{A, B, C, D, E}	Visit D, no neighbors	Visited: A, B, C, D, E; Queue: E
6	Dequeue	E	[]	{A, B, C, D, E}	Visit E, no neighbors	Visited: A, B, C, D, E; Queue empty
7	End	None	[]	{A, B, C, D, E}	Queue empty, BFS complete	All reachable nodes visited

💡 Queue is empty, all reachable nodes visited

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	Final
Current Node	None	A	A	B	C	D	E	None
Queue	[]	[A]	[B, C]	[C, D]	[D, E]	[E]	[]	[]
Visited Set	{}	{A}	{A, B, C}	{A, B, C, D}	{A, B, C, D, E}	{A, B, C, D, E}	{A, B, C, D, E}	{A, B, C, D, E}

Key Moments - 3 Insights

Why do we mark a node as visited before enqueueing its neighbors?

Marking a node visited before enqueueing neighbors prevents adding the same node multiple times to the queue, as shown in Step 1 and Step 2 where A is marked visited before B and C are enqueued.

What happens if the queue becomes empty?

When the queue is empty, BFS ends because there are no more nodes to visit. This is shown in Step 7 where the queue is empty and BFS completes.

Why do we use a queue instead of a stack?

A queue ensures nodes are visited in the order they are discovered (level by level). Using a stack would cause depth-first behavior, not breadth-first. The queue state in the table shows nodes processed in FIFO order.

Visual Quiz - 3 Questions

Look at the execution table, what is the queue state after Step 3?

A [D, E]

B [B, C]

C [C, D]

D [E]

💡 Hint

Check the 'Queue State' column in row for Step 3.

At which step does node E get visited?

A Step 6

B Step 5

C Step 4

D Step 7

💡 Hint

Look at the 'Current Node' and 'Visited Set' columns in the execution table.

If node C had an additional neighbor F, when would F be enqueued?

A After visiting node B

B After visiting node C

C At the start of BFS

D After visiting node E

💡 Hint

Neighbors are enqueued when their parent node is dequeued and visited, see Steps 3 and 4.

Concept Snapshot

BFS (Breadth First Search) explores nodes level by level.
Use a queue to track nodes to visit.
Mark nodes visited when enqueued to avoid repeats.
Dequeue nodes, visit, enqueue unvisited neighbors.
Stop when queue is empty.
Useful for shortest path in unweighted graphs.

Full Transcript

Breadth First Search (BFS) starts at a source node and explores all its neighbors before moving to the next level neighbors. It uses a queue to keep track of nodes to visit. Each node is marked visited when it is added to the queue to avoid revisiting. The process continues by dequeuing nodes, visiting them, and enqueueing their unvisited neighbors until the queue is empty. This ensures nodes are visited in order of their distance from the start node. The example graph shows BFS starting at node A, visiting nodes B and C next, then D and E, completing when all reachable nodes are visited.

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