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

Concept Flow - BFS Breadth First Search on Graph

Start at source node

↓

Mark source as visited

↓

Add source to queue

↓

While queue not empty

↓

Dequeue node

↓

Visit node's neighbors

↓

If neighbor not visited

↓

Mark visited

↓

Add neighbor to queue

↓

Repeat until queue empty

↓

End - All reachable nodes visited

BFS starts at a node, visits neighbors level by level using a queue, marking nodes visited to avoid repeats.

Execution Sample

DSA C#

Queue<string> queue = new Queue<string>();
HashSet<string> visited = new HashSet<string>();
queue.Enqueue("A");
visited.Add("A");
while(queue.Count > 0) {
  var node = queue.Dequeue();
  foreach(var neighbor in graph[node]) {
    if(!visited.Contains(neighbor)) {
      visited.Add(neighbor);
      queue.Enqueue(neighbor);
    }
  }
}

This code performs BFS on a graph starting from node 'A', visiting neighbors in order.

Execution Table

Step	Operation	Current Node	Visited Set	Queue State	Action Taken	Graph State
1	Initialize	None	{}	[]	Enqueue 'A', Mark 'A' visited	Graph unchanged
2	Dequeue	A	{A}	[]	Visit neighbors B, C	Graph unchanged
3	Check neighbor B	A	{A}	[B]	Mark B visited, enqueue B	Graph unchanged
4	Check neighbor C	A	{A, B}	[B, C]	Mark C visited, enqueue C	Graph unchanged
5	Dequeue	B	{A, B, C}	[C]	Visit neighbors A, D	Graph unchanged
6	Check neighbor A	B	{A, B, C}	[C]	Already visited, skip	Graph unchanged
7	Check neighbor D	B	{A, B, C}	[C, D]	Mark D visited, enqueue D	Graph unchanged
8	Dequeue	C	{A, B, C, D}	[D]	Visit neighbors A, E	Graph unchanged
9	Check neighbor A	C	{A, B, C, D}	[D]	Already visited, skip	Graph unchanged
10	Check neighbor E	C	{A, B, C, D}	[D, E]	Mark E visited, enqueue E	Graph unchanged
11	Dequeue	D	{A, B, C, D, E}	[E]	Visit neighbors B	Graph unchanged
12	Check neighbor B	D	{A, B, C, D, E}	[E]	Already visited, skip	Graph unchanged
13	Dequeue	E	{A, B, C, D, E}	[]	Visit neighbors C	Graph unchanged
14	Check neighbor C	E	{A, B, C, D, E}	[]	Already visited, skip	Graph unchanged
15	Queue empty	None	{A, B, C, D, E}	[]	End BFS	Graph unchanged

💡 Queue is empty, all reachable nodes visited

Variable Tracker

Variable	Start	After Step 1	After Step 4	After Step 7	After Step 10	After Step 15
queue	[]	[A]	[B, C]	[C, D]	[D, E]	[]
visited	{}	{A}	{A, B, C}	{A, B, C, D}	{A, B, C, D, E}	{A, B, C, D, E}
current_node	None	A	A	B	C	None

Key Moments - 3 Insights

Why do we mark a node as visited before adding it to the queue?

Marking visited before enqueueing (see Step 3 and 7) prevents adding the same node multiple times, avoiding repeated visits and infinite loops.

Why do we skip neighbors already in the visited set?

Skipping visited neighbors (see Steps 6, 9, 12, 14) ensures BFS does not revisit nodes, keeping traversal efficient and correct.

What happens when the queue becomes empty?

When the queue is empty (Step 15), BFS ends because all reachable nodes have been visited.

Visual Quiz - 3 Questions

Look at the execution table at Step 4, what is the state of the queue?

A [C]

B [B, C]

C [A, B]

D []

💡 Hint

Check the 'Queue State' column at Step 4 in the execution table.

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

A Step 7

B Step 9

C Step 6

D Step 10

💡 Hint

Look for when 'D' is marked visited and enqueued in the 'Action Taken' column.

If we start BFS from node 'B' instead of 'A', how would the initial queue state change?

A Queue starts with [A]

B Queue starts empty

C Queue starts with [B]

D Queue starts with [A, B]

💡 Hint

Refer to the initialization step where the start node is enqueued and marked visited.

Concept Snapshot

BFS (Breadth First Search) explores graph nodes level by level.
Uses a queue to track nodes to visit next.
Marks nodes visited when enqueued to avoid repeats.
Dequeues nodes, visits neighbors, enqueues unvisited neighbors.
Ends when queue is empty, meaning 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. Initially, the start node is marked visited and added to the queue. Then, while the queue is not empty, BFS dequeues a node, visits its neighbors, and for each neighbor not yet visited, marks it visited and enqueues it. This process continues until the queue is empty, meaning all reachable nodes have been visited. This method 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 hash set

B. A stack data structure

C. A priority queue

D. A queue data structure

Solution

1. Step 1: Understand BFS traversal method

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

2. Step 2: Identify data structure used for level order traversal

   To achieve level order, BFS uses a queue to process nodes in the order they are discovered.

3. Final Answer:

   A queue data structure -> Option D

4. Quick Check:

   BFS uses queue = A [OK]

Hint: BFS uses queue to explore neighbors level-wise [OK]

Common Mistakes:

• Confusing BFS with DFS which uses stack
• Thinking BFS uses priority queue
• Assuming BFS uses only a hash set

2. Which of the following is the correct way to enqueue a node current in a BFS queue in C#?

easy

A. queue.Enqueue(current);

B. queue.Push(current);

C. queue.Add(current);

D. queue.Insert(current);

Solution

1. Step 1: Recall C# Queue methods

   The Queue class in C# uses Enqueue() to add elements at the end.

2. Step 2: Match method to enqueue operation

   Push() is for stacks, Add() and Insert() are not Queue methods.

3. Final Answer:

   queue.Enqueue(current); -> Option A

4. Quick Check:

   Queue add method = Enqueue [OK]

Hint: Use Enqueue() to add items to a C# queue [OK]

Common Mistakes:

• Using Push() which is for stacks
• Using Add() or Insert() which are not queue methods
• Confusing queue with list methods

3. Given the following graph adjacency list and BFS starting from node 1, what is the order of nodes visited?

var graph = new Dictionary {
  {1, new List<int>{2, 3}},
  {2, new List<int>{4}},
  {3, new List<int>{4}},
  {4, new List<int>{}}
};

medium

A. [1, 2, 3, 4]

B. [1, 3, 2, 4]

C. [1, 4, 2, 3]

D. [1, 2, 4, 3]

Solution

1. Step 1: Start BFS from node 1

   Visit 1, enqueue neighbors 2 and 3 in order.

2. Step 2: Visit nodes in queue order

   Dequeue 2, visit it, enqueue 4. Then dequeue 3, visit it, enqueue 4 (already enqueued).

3. Step 3: Visit node 4

   Dequeue 4, visit it. No new nodes to enqueue.

4. Final Answer:

   [1, 2, 3, 4] -> Option A

5. Quick Check:

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

Hint: Visit neighbors in enqueue order, process queue FIFO [OK]

Common Mistakes:

• Visiting neighbors in wrong order
• Visiting node 3 before 2
• Adding duplicates of node 4

4. What is the error in this BFS code snippet in C#?

var queue = new Queue<int>();
var visited = new HashSet<int>();
queue.Enqueue(1);
while(queue.Count > 0) {
  int node = queue.Dequeue();
  if(!visited.Contains(node)) {
    visited.Add(node);
    foreach(var neighbor in graph[node]) {
      queue.Enqueue(neighbor);
    }
  }
}

medium

A. Dequeue method is incorrect

B. Visited nodes are never added

C. Neighbors are enqueued even if already visited

D. Queue is not initialized

Solution

1. Step 1: Analyze neighbor enqueue logic

   Neighbors are enqueued without checking if visited, causing duplicates.

2. Step 2: Identify missing visited check before enqueue

   Should check if neighbor is visited before enqueue to avoid repeated processing.

3. Final Answer:

   Neighbors are enqueued even if already visited -> Option C

4. Quick Check:

   Check visited before enqueue = D [OK]

Hint: Check visited before enqueue to avoid duplicates [OK]

Common Mistakes:

• Enqueueing visited neighbors multiple times
• Not adding nodes to visited set
• Incorrect queue initialization

5. You want to find the shortest path from node 1 to node 5 in an unweighted graph using BFS. Which modification is needed to the BFS algorithm to track the path?

hard

A. Mark nodes as visited only after dequeuing

B. Maintain a dictionary to store each node's parent during traversal

C. Use a stack instead of a queue to track nodes

D. Enqueue nodes multiple times to find all paths

Solution

1. Step 1: Understand BFS for shortest path

   BFS finds shortest paths in unweighted graphs by exploring neighbors level-wise.

2. Step 2: Track path using parent dictionary

   Store each node's parent when first visited to reconstruct path after BFS completes.

3. Final Answer:

   Maintain a dictionary to store each node's parent during traversal -> Option B

4. Quick Check:

   Parent tracking dictionary = C [OK]

Hint: Track parents to reconstruct shortest path after BFS [OK]

Common Mistakes:

• Using stack breaks BFS order
• Marking visited too late causes duplicates
• Enqueueing nodes multiple times wastes time