BFS Breadth First Search on Graph in DSA C++ - Execution Trace

Concept Flow - BFS Breadth First Search on Graph

Start at source node

↓

Mark node visited

↓

Add node to queue

↓

While queue not empty

↓

Dequeue front node

↓

Visit all unvisited neighbors

↓

Mark neighbors visited and enqueue

↓

While queue not empty

↓

End

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

Execution Sample

DSA C++

graph = {
  'A': ['B', 'D'],
  'B': ['A', 'C'],
  'C': ['B', 'F'],
  'D': ['A', 'E'],
  'E': ['D', 'F'],
  'F': ['C', 'E']
}

def BFS(start):
    visited = set()
    queue = []
    visited.add(start)
    queue.append(start)

    while queue:
        node = queue.pop(0)
        print(node, end=' ')
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

BFS('A')

Perform BFS starting from node 'A' on the given graph.

Execution Table

Step	Operation	Current Node	Queue State	Visited Set	Visual State
1	Start BFS	-	[]	{}	Graph: A-B-C-F, D-E-F Queue: [] Visited: {}
2	Visit start node	A	[A]	{A}	Queue: [A] Visited: {A}
3	Dequeue node	A	[]	{A}	Dequeued A Queue: [] Visited: {A}
4	Enqueue neighbors	-	[B, D]	{A, B, D}	Neighbors B, D enqueued Queue: [B, D] Visited: {A, B, D}
5	Dequeue node	B	[D]	{A, B, D}	Dequeued B Queue: [D] Visited: {A, B, D}
6	Enqueue neighbors	-	[D, C]	{A, B, C, D}	Neighbor C enqueued (A visited) Queue: [D, C] Visited: {A, B, C, D}
7	Dequeue node	D	[C]	{A, B, C, D}	Dequeued D Queue: [C] Visited: {A, B, C, D}
8	Enqueue neighbors	-	[C, E]	{A, B, C, D, E}	Neighbor E enqueued (A visited) Queue: [C, E] Visited: {A, B, C, D, E}
9	Dequeue node	C	[E]	{A, B, C, D, E}	Dequeued C Queue: [E] Visited: {A, B, C, D, E}
10	Enqueue neighbors	-	[E, F]	{A, B, C, D, E, F}	Neighbor F enqueued (B visited) Queue: [E, F] Visited: {A, B, C, D, E, F}
11	Dequeue node	E	[F]	{A, B, C, D, E, F}	Dequeued E Queue: [F] Visited: {A, B, C, D, E, F}
12	Enqueue neighbors	-	[F]	{A, B, C, D, E, F}	Neighbors D, F visited already Queue: [F] Visited: {A, B, C, D, E, F}
13	Dequeue node	F	[]	{A, B, C, D, E, F}	Dequeued F Queue: [] Visited: {A, B, C, D, E, F}
14	Enqueue neighbors	-	[]	{A, B, C, D, E, F}	Neighbors C, E visited already Queue: [] Visited: {A, B, C, D, E, F}
15	End BFS	-	[]	{A, B, C, D, E, F}	Queue empty, BFS complete

💡 Queue is empty, all reachable nodes visited

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 8	After Step 10	After Step 12	After Step 14	Final
Queue	[]	[A]	[B, D]	[D, C]	[C, E]	[E, F]	[F]	[]	[]
Visited Set	{}	{A}	{A, B, D}	{A, B, C, D}	{A, B, C, D, E}	{A, B, C, D, E, F}	{A, B, C, D, E, F}	{A, B, C, D, E, F}	{A, B, C, D, E, F}
Current Node	-	A	A	B	D	C	E	F	-

Key Moments - 3 Insights

Why do we mark nodes as visited before enqueueing them?

Marking nodes visited before enqueueing (see Step 4, 6, 8, 10) prevents adding the same node multiple times to the queue, avoiding repeated visits and infinite loops.

Why does BFS use a queue instead of a stack?

BFS uses a queue (FIFO) to explore nodes level by level. Using a stack (LIFO) would explore depth first, changing the order of traversal (see Queue state changes in execution_table).

What happens when the queue becomes empty?

When the queue is empty (Step 15), it means all reachable nodes have been visited and BFS ends, as no more nodes are left to explore.

Visual Quiz - 3 Questions

Look at the execution_table, what is the queue state after Step 8?

A [C, E]

B [D, C]

C [E, F]

D [B, D]

💡 Hint

Check the 'Queue State' column in row for Step 8 in execution_table

At which step does node 'F' get added to the queue?

A Step 4

B Step 6

C Step 10

D Step 12

💡 Hint

Look at 'Enqueue neighbors' operations and when 'F' appears in the queue in execution_table

If we start BFS from node 'C' instead of 'A', which node will be visited first?

A A

B C

C B

D F

💡 Hint

Starting node is the first visited and enqueued (see Step 2 in execution_table)

Concept Snapshot

BFS (Breadth First Search) explores graph nodes level by level.
Uses a queue to track nodes to visit next.
Mark nodes visited when enqueued to avoid repeats.
Dequeue node, visit neighbors, enqueue unvisited neighbors.
Stops when queue is empty (all reachable nodes visited).

Full Transcript

Breadth First Search (BFS) starts at a chosen node and explores all its neighbors before moving to the next level neighbors. It uses a queue to keep track of nodes to visit. When a node is visited, it is marked to avoid revisiting. The algorithm dequeues a node, visits its unvisited neighbors by marking and enqueueing them, and repeats until the queue is empty. This ensures nodes are visited in order of their distance from the start node, level by level.

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