BFS Breadth First Search on Graph in DSA C++

Mental Model

BFS explores all neighbors of a node before moving to the next level of nodes. It spreads out evenly like ripples in water.

Analogy: Imagine dropping a stone in a pond. The ripples spread out evenly in circles, visiting all points at the same distance before moving further.

Graph:
  1
 / \
2   3
|    |
4    5

Queue: []
Visited: {}

Dry Run Walkthrough

Input: Graph edges: 1-2, 1-3, 2-4, 3-5; Start BFS from node 1

Goal: Visit all nodes in order of their distance from node 1

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

Queue: [1]
Visited: {1}

Why: We begin from the start node to explore its neighbors

Step 2: Dequeue node 1, enqueue its neighbors 2 and 3, mark visited

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

Why: Visit all neighbors of node 1 before moving deeper

Step 3: Dequeue node 2, enqueue its neighbor 4, mark visited

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

Why: Explore neighbors of node 2 next

Step 4: Dequeue node 3, enqueue its neighbor 5, mark visited

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

Why: Explore neighbors of node 3 next

Step 5: Dequeue node 4, no new neighbors to enqueue

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

Why: Node 4 has no unvisited neighbors

Step 6: Dequeue node 5, no new neighbors to enqueue

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

Why: Node 5 has no unvisited neighbors

Result:

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

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Graph {
public:
    int V;
    vector<vector<int>> adj;

    Graph(int vertices) {
        V = vertices;
        adj.resize(V + 1);
    }

    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u); // undirected graph
    }

    void BFS(int start) {
        vector<bool> visited(V + 1, false);
        queue<int> q;

        visited[start] = true; // mark start visited
        q.push(start); // enqueue start

        while (!q.empty()) {
            int node = q.front();
            q.pop();
            cout << node << " "; // visit node

            for (int neighbor : adj[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true; // mark neighbor visited
                    q.push(neighbor); // enqueue neighbor
                }
            }
        }
    }
};

int main() {
    Graph g(5);
    g.addEdge(1, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    g.addEdge(3, 5);

    g.BFS(1);
    return 0;
}

visited[start] = true; // mark start visited q.push(start); // enqueue start

Initialize BFS by marking start node visited and enqueue it

while (!q.empty()) {

Continue until all reachable nodes are visited

int node = q.front(); q.pop(); cout << node << " "; // visit node

Dequeue node and process it (print)

for (int neighbor : adj[node]) { if (!visited[neighbor]) { visited[neighbor] = true; // mark neighbor visited q.push(neighbor); // enqueue neighbor } }

Enqueue all unvisited neighbors and mark them visited

Output

1 2 3 4 5 

Complexity Analysis

Time: O(V + E) because each vertex and edge is visited once during BFS

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

vs Alternative: Compared to DFS which uses stack/recursion, BFS uses queue and explores level by level, useful for shortest path in unweighted graphs

Edge Cases

Empty graph (no vertices)

BFS does nothing as there are no nodes to visit

DSA C++

visited[start] = true; // mark start visited

Graph with single node and no edges

BFS visits the single node and stops

DSA C++

while (!q.empty()) {

Disconnected graph

BFS visits only nodes reachable from start node

DSA C++

if (!visited[neighbor]) {

When to Use This Pattern

When you need to explore nodes layer by layer or find shortest path in unweighted graphs, BFS is the pattern to use because it visits nodes in order of distance.

Common Mistakes

Mistake: Not marking nodes visited before enqueueing causes repeated visits and infinite loops
Fix: Mark nodes visited immediately when enqueueing to avoid duplicates

Summary

Visits all nodes in a graph level by level starting from a given node.

Use BFS when you want to find shortest paths or explore nodes in layers.

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

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