BFS Breadth First Search on Graph in DSA Go - Deep Dive

Overview - BFS Breadth First Search on Graph

What is it?

Breadth First Search (BFS) is a way to explore all the points (nodes) in a graph by visiting neighbors level by level. It starts from one node and visits all nodes that are one step away before moving to nodes two steps away, and so on. This method helps find the shortest path in unweighted graphs and explore all connected parts. BFS uses a queue to keep track of nodes to visit next.

Why it matters

Without BFS, finding the shortest path or exploring all connected nodes in a graph would be slow and complicated. BFS solves this by visiting nodes in an organized way, ensuring no node is missed or visited twice. This is important in many real-world problems like finding routes on maps, social network connections, or spreading information efficiently.

Where it fits

Before learning BFS, you should understand what graphs are and how they represent connections between points. After BFS, you can learn about Depth First Search (DFS), shortest path algorithms like Dijkstra's, and graph traversal optimizations.

Mental Model

Core Idea

BFS explores a graph by visiting all neighbors at the current distance before moving to nodes further away, using a queue to track the order.

Think of it like...

Imagine you are in a building and want to visit every room floor by floor. You first visit all rooms on the first floor, then all rooms on the second floor, and so on, making sure you don't skip any room or go back unnecessarily.

Start Node
  │
  ▼
[Queue] -> [Visit neighbors]
  │
  ▼
Level 0: Start Node
Level 1: Neighbors of Start Node
Level 2: Neighbors of Level 1 nodes
...

Graph traversal order flows like waves expanding from the start node.

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Nodes

Concept: Introduce what a graph is and how nodes and edges represent connections.

A graph is a collection of points called nodes connected by lines called edges. For example, a social network where people are nodes and friendships are edges. Graphs can be directed (one-way connections) or undirected (two-way connections).

Result

You can visualize relationships as points connected by lines, preparing to explore them.

Understanding the structure of graphs is essential before learning how to explore or search them.

2

Foundation

Queues: The Waiting Line Structure

Concept: Introduce the queue data structure used to manage the order of visiting nodes.

A queue is like a line at a store: first person in is first person out (FIFO). We add new neighbors to the back and visit nodes from the front. This order ensures we explore nodes level by level.

Result

You know how to keep track of nodes to visit next in BFS.

Using a queue is key to BFS's level-by-level exploration, unlike other methods that use stacks or recursion.

3

Intermediate

Basic BFS Algorithm Steps

🤔Before reading on: do you think BFS visits nodes in order of their distance from the start or randomly? Commit to your answer.

Concept: Learn the step-by-step process of BFS using a queue and a visited set.

1. Start by putting the start node in the queue and marking it visited. 2. While the queue is not empty: a. Remove the front node from the queue. b. Visit all its neighbors that are not visited yet. c. Add those neighbors to the queue and mark them visited. 3. Repeat until all reachable nodes are visited.

Result

Nodes are visited in order of their distance from the start node, ensuring no node is visited twice.

This process guarantees BFS explores nodes in layers, which is why it finds shortest paths in unweighted graphs.

4

Intermediate

Implementing BFS in Go

🤔Before reading on: do you think BFS needs recursion or can it be done with loops? Commit to your answer.

Concept: Show how to write BFS code in Go using slices as queues and maps for visited nodes.

package main import "fmt" func BFS(graph map[int][]int, start int) []int { visited := make(map[int]bool) queue := []int{start} visited[start] = true order := []int{} 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{ 1: {2, 3}, 2: {4}, 3: {4, 5}, 4: {}, 5: {}, } order := BFS(graph, 1) fmt.Println(order) }

Result

[1 2 3 4 5]

Knowing BFS can be implemented with loops and queues in Go helps understand its iterative nature and avoids confusion with recursive DFS.

5

Intermediate

Handling Disconnected Graphs

🤔Before reading on: do you think BFS alone visits all nodes in a disconnected graph? Commit to your answer.

Concept: Learn how to run BFS multiple times to cover all parts of a graph that are not connected.

If the graph has multiple disconnected parts, running BFS from one node visits only that part. To visit all nodes, run BFS from each unvisited node until all nodes are covered.

Result

All nodes in the graph are visited, even if disconnected.

Understanding this prevents missing parts of the graph in real applications like network analysis.

6

Advanced

BFS for Shortest Path Finding

🤔Before reading on: do you think BFS can find shortest paths in weighted graphs? Commit to your answer.

Concept: Use BFS to find the shortest path in unweighted graphs by tracking parents of nodes.

Modify BFS to keep track of each node's parent when visiting neighbors. After BFS, reconstruct the path from the target node back to the start by following parents. This works only if edges have equal weight (unweighted).

Result

You get the shortest path as a list of nodes from start to target.

Knowing BFS finds shortest paths in unweighted graphs is crucial for routing and navigation problems.

7

Expert

Optimizations and BFS Variants

🤔Before reading on: do you think BFS always uses a simple queue or can it be optimized? Commit to your answer.

Concept: Explore BFS optimizations like bidirectional BFS and using specialized queues for performance.

Bidirectional BFS runs two BFS searches simultaneously from start and target nodes, meeting in the middle to reduce search space. Also, using double-ended queues (deque) or adjacency lists improves speed and memory. These optimizations matter in large graphs like social networks or maps.

Result

Faster BFS execution and less memory use on big graphs.

Understanding BFS optimizations helps build scalable graph algorithms for real-world large datasets.

Under the Hood

BFS uses a queue to store nodes to visit next, ensuring nodes are explored in order of their distance from the start. Internally, it marks nodes as visited to avoid revisiting and loops until all reachable nodes are processed. The queue operations (enqueue and dequeue) maintain the order of exploration, and the visited set prevents infinite loops in cyclic graphs.

Why designed this way?

BFS was designed to explore graphs level by level to guarantee shortest path discovery in unweighted graphs. Using a queue fits naturally with this goal because it processes nodes in the order they are discovered. Alternatives like depth-first search use stacks or recursion but do not guarantee shortest paths. BFS's design balances simplicity and correctness for many applications.

┌─────────────┐
│ Start Node  │
└──────┬──────┘
       │
       ▼
┌─────────────┐      ┌─────────────┐
│  Queue      │─────▶│ Visit Node  │
└──────┬──────┘      └──────┬──────┘
       │                    │
       ▼                    ▼
┌─────────────┐      ┌─────────────┐
│ Enqueue    │◀─────│ Neighbors   │
│ neighbors  │      │ not visited │
└─────────────┘      └─────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does BFS always find the shortest path in any graph? Commit yes or no.

Common Belief: BFS always finds the shortest path regardless of edge weights.

Reality: BFS finds shortest paths only in unweighted graphs or graphs where all edges have the same weight.

Why it matters: Using BFS on weighted graphs can give wrong shortest paths, leading to incorrect routing or decisions.

Quick: Can BFS be implemented using recursion? Commit yes or no.

Common Belief: BFS can be implemented using recursion like DFS.

Reality: BFS is naturally iterative and uses a queue; recursion fits DFS better.

Why it matters: Trying to implement BFS recursively can cause confusion and incorrect traversal order.

Quick: Does BFS visit nodes in random order? Commit yes or no.

Common Belief: BFS visits nodes in no particular order, just as it finds them.

Reality: BFS visits nodes in order of their distance from the start node, level by level.

Why it matters: Misunderstanding BFS order can lead to wrong assumptions about traversal results and path lengths.

Quick: Does BFS visit all nodes in a disconnected graph from one start node? Commit yes or no.

Common Belief: BFS from one node visits all nodes in the graph.

Reality: BFS visits only nodes connected to the start node; disconnected parts remain unvisited.

Why it matters: Assuming BFS covers all nodes can cause missed data or incomplete analysis in disconnected graphs.

Expert Zone

1

BFS's performance depends heavily on graph representation; adjacency lists are more efficient than adjacency matrices for sparse graphs.

2

Bidirectional BFS can reduce search time from O(V+E) to roughly O(b^(d/2)) where b is branching factor and d is distance, a huge gain on large graphs.

3

Tracking parents during BFS not only finds shortest paths but also enables reconstructing multiple shortest paths if needed.

When NOT to use

Avoid BFS for weighted graphs with varying edge costs; use Dijkstra's or A* algorithms instead. Also, for deep or infinite graphs where memory is limited, DFS or iterative deepening may be better.

Production Patterns

BFS is used in social network analysis to find degrees of separation, in web crawlers to explore links level by level, and in AI for shortest path planning in unweighted grids or maps.

Connections

Depth First Search (DFS)

Opposite traversal order and data structure (stack vs queue)

Understanding BFS helps grasp DFS by contrast, showing how traversal order affects path finding and exploration.

Shortest Path Algorithms

BFS is a special case of shortest path algorithms for unweighted graphs

Knowing BFS clarifies why more complex algorithms like Dijkstra's are needed for weighted graphs.

Wave Propagation in Physics

BFS traversal mimics wavefront expansion from a source point

Recognizing BFS as wave propagation helps understand its level-by-level exploration and shortest path properties.

Common Pitfalls

#1 Visiting nodes multiple times causing infinite loops.

Wrong approach:

func BFS(graph map[int][]int, start int) {
queue := []int{start}
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
fmt.Println(node)
for _, neighbor := range graph[node] {
queue = append(queue, neighbor) // No visited check
}
}
}

Correct approach:

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

Root cause:

Not marking nodes as visited causes repeated visits and infinite loops in cyclic graphs.

#2 Using BFS to find shortest path in weighted graphs without modification.

Wrong approach:

Run BFS on weighted graph edges assuming shortest path is found directly.

Correct approach:

Use Dijkstra's algorithm or A* for weighted graphs to find shortest paths correctly.

Root cause:

BFS assumes equal edge weights; ignoring weights leads to incorrect paths.

#3 Assuming BFS visits all nodes from a single start node in disconnected graphs.

Wrong approach:

Run BFS once and expect all nodes visited:
BFS(graph, startNode)

Correct approach:

visited := make(map[int]bool)
for node := range graph {
if !visited[node] {
BFS(graph, node)
}
}

Root cause:

Not accounting for disconnected components causes incomplete traversal.

Key Takeaways

BFS explores graphs level by level using a queue, ensuring nodes are visited in order of their distance from the start.

It guarantees shortest paths in unweighted graphs by visiting neighbors before moving deeper.

Marking nodes as visited is essential to avoid infinite loops and repeated visits.

BFS is iterative and uses a queue, unlike DFS which uses recursion or a stack.

For weighted graphs or large datasets, BFS has limits and requires specialized algorithms or optimizations.

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