BFS Breadth First Search on Graph in DSA C++ - 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 close to it before moving further away. This method helps find the shortest path in unweighted graphs and checks connectivity between nodes. 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 parts of a graph would be slow and complicated. BFS helps computers solve problems like finding routes on maps, social network connections, or organizing tasks in the right order. Without BFS, many apps and systems would be inefficient or unable to solve these problems quickly.

Where it fits

Before learning BFS, you should understand what graphs are and how they represent connections between things. 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, ensuring the shortest path in unweighted graphs.

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 ground floor, then all rooms on the first floor, and so on, never skipping a floor. BFS works the same way by exploring nodes level by level.

Start Node
  │
  ├─ Level 1 neighbors
  │    ├─ Level 2 neighbors
  │    └─ Level 2 neighbors
  └─ Level 1 neighbors

Queue: [Start] -> [Level 1 neighbors] -> [Level 2 neighbors] -> ...

Build-Up - 7 Steps

1

Foundation

Understanding Graphs and Nodes

Concept: Graphs are made of nodes connected by edges, representing relationships.

A graph is a collection of points called nodes or vertices. Each node can connect to other nodes via 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 picture a graph as dots connected by lines, showing relationships.

Understanding what a graph is and how nodes connect is essential before exploring how to visit or search through them.

2

Foundation

What is BFS and Its Basic Idea

Concept: BFS visits nodes in layers, starting from a chosen node and moving outward.

BFS starts at a chosen node and visits all its neighbors first. Then it visits neighbors of those neighbors, and so on. It uses a queue to remember which nodes to visit next, ensuring nodes closer to the start are visited before farther ones.

Result

Nodes are visited in order of their distance from the start node.

Knowing BFS visits nodes level by level helps understand why it finds shortest paths in unweighted graphs.

3

Intermediate

Implementing BFS Using a Queue

🤔Before reading on: do you think BFS uses a stack or a queue to keep track of nodes? Commit to your answer.

Concept: BFS uses a queue to process nodes in the order they are discovered.

We start by putting the start node in a queue. Then, while the queue is not empty, we remove the front node, visit it, and add all its unvisited neighbors to the back of the queue. This way, nodes are visited in the order they were discovered.

Result

The queue ensures nodes are visited in breadth-first order, level by level.

Understanding the queue's role clarifies how BFS maintains the correct visiting order.

4

Intermediate

Tracking Visited Nodes to Avoid Repeats

🤔Before reading on: what happens if BFS does not track visited nodes? Predict the outcome.

Concept: BFS must remember which nodes it has visited to avoid infinite loops and repeated work.

Graphs can have cycles, meaning nodes connect back to earlier nodes. Without marking nodes as visited, BFS could revisit the same nodes endlessly. We keep a visited list or set to mark nodes once visited, so we never add them to the queue again.

Result

BFS visits each node only once, preventing infinite loops.

Knowing why visited tracking is necessary prevents common bugs and infinite loops in BFS.

5

Intermediate

Using BFS to Find Shortest Paths

🤔Before reading on: does BFS find shortest paths in weighted graphs? Yes or no? Commit your answer.

Concept: BFS finds shortest paths in graphs where all edges have equal weight or no weight.

Because BFS visits nodes in order of distance from the start, the first time it reaches a node is along the shortest path. We can keep track of each node's parent to reconstruct the path after BFS finishes.

Result

BFS returns the shortest path length and route in unweighted graphs.

Understanding BFS's level-by-level visit order explains why it finds shortest paths in unweighted graphs.

6

Advanced

BFS on Directed and Undirected Graphs

🤔Before reading on: do you think BFS works the same on directed and undirected graphs? Commit your answer.

Concept: BFS works on both directed and undirected graphs but follows edges according to their direction.

In undirected graphs, edges connect nodes both ways, so BFS can move freely. In directed graphs, BFS only follows edges in the given direction, which can limit reachable nodes. The algorithm remains the same but the graph's structure affects traversal.

Result

BFS explores reachable nodes respecting edge directions.

Knowing how edge direction affects BFS helps understand graph connectivity and reachability.

7

Expert

Optimizing BFS with Early Stopping and Memory

🤔Before reading on: can BFS stop early when searching for a target? How does this affect performance? Commit your answer.

Concept: BFS can stop as soon as the target node is found, saving time and memory.

When searching for a specific node or shortest path, BFS can stop immediately upon reaching the target. This avoids exploring unnecessary nodes. Also, using adjacency lists instead of matrices reduces memory use. For very large graphs, BFS can be combined with bidirectional search to speed up.

Result

BFS runs faster and uses less memory with these optimizations.

Understanding BFS stopping conditions and data structures improves efficiency in real-world applications.

Under the Hood

BFS uses a queue data structure to manage the order of node visits. Internally, it marks nodes as visited to avoid revisiting. The queue ensures nodes are processed in the order they are discovered, which corresponds to their distance from the start node. This level-order traversal guarantees shortest path discovery in unweighted graphs. Memory stores the graph as adjacency lists or matrices, and the algorithm iterates over neighbors efficiently.

Why designed this way?

BFS was designed to explore graphs systematically without missing nodes or getting stuck in cycles. Using a queue naturally fits the level-by-level exploration needed for shortest paths. Alternatives like Depth First Search use stacks and explore deeply first, which doesn't guarantee shortest paths. BFS balances simplicity, correctness, and efficiency for many graph problems.

┌─────────────┐
│ Start Node  │
└──────┬──────┘
       │
       ▼
┌─────────────┐       ┌─────────────┐
│ Queue Front │──────▶│ Visit Node  │
└──────┬──────┘       └──────┬──────┘
       │                     │
       │                     ▼
       │             ┌─────────────┐
       │             │ Add Neighbors│
       │             └──────┬──────┘
       │                    │
       └────────────────────┘
       (Repeat until queue empty)

Myth Busters - 4 Common Misconceptions

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

Common Belief: BFS finds the shortest path in all graphs, including weighted ones.

Reality: BFS only guarantees shortest paths in unweighted graphs or graphs where all edges have equal weight.

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

Quick: Can BFS use a stack instead of a queue and still work correctly? Commit yes or no.

Common Belief: BFS can use a stack or queue interchangeably to explore nodes.

Reality: BFS requires a queue to explore nodes level by level; using a stack changes the order and becomes Depth First Search.

Why it matters: Using a stack instead of a queue changes the traversal order and breaks BFS's guarantees.

Quick: Does BFS always visit all nodes in a graph? Commit yes or no.

Common Belief: BFS visits every node in the graph regardless of the start node.

Reality: BFS only visits nodes reachable from the start node; disconnected parts remain unvisited.

Why it matters: Assuming BFS visits all nodes can cause bugs when graphs are disconnected or have isolated components.

Quick: Is it safe to add nodes to the queue multiple times in BFS? Commit yes or no.

Common Belief: Adding nodes multiple times to the queue is fine; BFS will handle duplicates.

Reality: Adding duplicates causes repeated visits and can lead to infinite loops or inefficiency; visited tracking is essential.

Why it matters: Ignoring visited tracking can cause BFS to run forever or waste resources.

Expert Zone

1

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

2

In very large graphs, BFS can be parallelized by processing nodes at the same level concurrently, but synchronization is needed to maintain correctness.

3

Bidirectional BFS, running two simultaneous BFS from start and target nodes, can drastically reduce search space and time for shortest path queries.

When NOT to use

BFS is not suitable for graphs with weighted edges where weights differ; algorithms like Dijkstra's or A* are better. Also, for deep traversal or path existence without shortest path needs, Depth First Search may be more memory efficient.

Production Patterns

BFS is used in social networks to find friend recommendations, in GPS systems for shortest routes on unweighted maps, in web crawlers to explore links level by level, and in AI for state space exploration where all moves have equal cost.

Connections

Depth First Search (DFS)

Opposite traversal order; DFS explores deeply before breadth.

Understanding BFS helps contrast with DFS, clarifying when to use each for graph problems.

Queue Data Structure

BFS relies on queues to manage node visiting order.

Knowing queue behavior is essential to grasp BFS's level-order traversal.

Wave Propagation in Physics

BFS mimics wavefront expansion from a source point.

Seeing BFS as wave propagation helps understand shortest path discovery and spreading processes.

Common Pitfalls

#1 Not marking nodes as visited causes infinite loops.

Wrong approach:

while (!queue.empty()) {
int node = queue.front();
queue.pop();
for (int neighbor : graph[node]) {
queue.push(neighbor); // No visited check
}
}

Correct approach:

while (!queue.empty()) {
int node = queue.front();
queue.pop();
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
}
}

Root cause:

Forgetting to track visited nodes leads to revisiting the same nodes endlessly.

#2 Using a stack instead of a queue changes BFS to DFS.

Wrong approach:

stack.push(start);
while (!stack.empty()) {
int node = stack.top();
stack.pop();
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
stack.push(neighbor);
}
}
}

Correct approach:

queue.push(start);
while (!queue.empty()) {
int node = queue.front();
queue.pop();
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
queue.push(neighbor);
}
}
}

Root cause:

Confusing stack and queue changes traversal order and algorithm behavior.

#3 Assuming BFS finds shortest paths in weighted graphs.

Wrong approach:

Use BFS on weighted graph edges with different costs expecting shortest path.

Correct approach:

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

Root cause:

Misunderstanding BFS's limitation to unweighted or equally weighted graphs.

Key Takeaways

BFS explores graphs level by level using a queue, ensuring nodes closer to the start are visited first.

Tracking visited nodes is essential to avoid infinite loops and repeated visits in BFS.

BFS guarantees shortest paths only in unweighted graphs or graphs with equal edge weights.

BFS works on both directed and undirected graphs but respects edge directions in directed graphs.

Optimizations like early stopping and bidirectional search improve BFS efficiency in large graphs.

Practice

1. What does BFS (Breadth First Search) primarily use to keep track of nodes to visit next in a graph?

easy

A. A queue data structure

B. A stack data structure

C. A priority queue

D. A hash map

Solution

1. Step 1: Understand BFS traversal method

   BFS explores nodes level by level, visiting all neighbors before moving deeper.

2. Step 2: Identify the data structure used

   To maintain the order of visiting nodes level-wise, BFS uses a queue which follows FIFO (First In First Out).

3. Final Answer:

   A queue data structure -> Option A

4. Quick Check:

   BFS uses queue = B [OK]

Hint: BFS uses FIFO order, so it needs a queue [OK]

Common Mistakes:

• Confusing BFS with DFS which uses a stack
• Thinking BFS uses a priority queue
• Assuming BFS uses a hash map for order

2. Which of the following is the correct way to declare a queue for BFS traversal of integers in C++?

easy

A. vector<int> q;

B. queue<int> q;

C. stack<int> q;

D. list<int> q;

Solution

1. Step 1: Identify the correct STL container for queue

   In C++, the standard queue container is declared as queue<type>.

2. Step 2: Match the declaration for integer queue

   queue<int> q; correctly declares a queue of integers.

3. Final Answer:

   queue<int> q; -> Option B

4. Quick Check:

   Correct queue syntax = queue<int> q; [OK]

Hint: Use queue<int> for BFS integer queue in C++ [OK]

Common Mistakes:

• Using stack instead of queue
• Using vector or list which are not queues
• Missing template angle brackets

3. Consider the following graph represented as adjacency list:

0: 1, 2
1: 0, 3
2: 0, 3
3: 1, 2

If BFS starts from node 0, what is the order of nodes visited?

medium

A. [0, 1, 3, 2]

B. [0, 2, 1, 3]

C. [0, 3, 1, 2]

D. [0, 1, 2, 3]

Solution

1. Step 1: Start BFS from node 0

   Visit node 0 first, enqueue neighbors 1 and 2.

2. Step 2: Visit neighbors in queue order

   Dequeue 1, enqueue its neighbor 3 (0 already visited). Then dequeue 2, enqueue 3 but already visited.

3. Step 3: Visit node 3

   Finally dequeue 3.

4. Final Answer:

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

5. Quick Check:

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

Hint: Visit neighbors in queue order, avoid revisits [OK]

Common Mistakes:

• Visiting neighbors in wrong order
• Revisiting nodes already visited
• Confusing BFS with DFS order

4. The following BFS code snippet has a bug. What is the error?

void bfs(int start, vector& adj) {
  vector<bool> visited(adj.size(), false);
  queue<int> q;
  q.push(start);
  while (!q.empty()) {
    int node = q.front();
    q.pop();
    cout << node << " ";
    for (int neighbor : adj[node]) {
      if (!visited[neighbor]) {
        q.push(neighbor);
      }
    }
  }
}

medium

A. Neighbors are not iterated correctly

B. Queue is not initialized properly

C. Visited array is never updated to true for visited nodes

D. Start node is not pushed into the queue

Solution

1. Step 1: Check visited array usage

   Visited array is created but nodes are never marked visited after visiting.

2. Step 2: Understand impact on BFS

   Without marking visited true, nodes can be enqueued multiple times causing infinite loops or repeated visits.

3. Final Answer:

   Visited array is never updated to true for visited nodes -> Option C

4. Quick Check:

   Must mark visited[node] = true after popping [OK]

Hint: Always mark nodes visited after dequeuing [OK]

Common Mistakes:

• Forgetting to mark visited nodes
• Pushing start node multiple times
• Incorrect loop conditions

5. Given a graph with nodes 0 to 4 and edges: 0-1, 0-2, 1-3, 2-3, 3-4. Using BFS starting from node 0, which node is visited at the 3rd position in the BFS order?

hard

A. 2

B. 4

C. 1

D. 3

Solution

1. Step 1: List neighbors and BFS order

   Start at 0, enqueue neighbors 1 and 2. BFS order so far: [0]

2. Step 2: Visit nodes in queue order

   Dequeue 1 (2nd visited), enqueue 3. Dequeue 2 (3rd visited), enqueue 3 but already enqueued.

3. Step 3: Confirm 3rd visited node

   The third node visited is 2.

4. Final Answer:

   2 -> Option A

5. Quick Check:

   Third visited node = 2 [OK]

Hint: Track queue order carefully to find nth visited node [OK]

Common Mistakes:

• Mixing order of neighbors
• Counting start node incorrectly
• Ignoring repeated nodes in queue