BFS Breadth First Search on Graph in DSA C#

Mental Model

BFS explores all neighbors of a node before moving to the next level, like spreading out evenly layer by layer.

Analogy: Imagine you are in a building and want to visit every room floor by floor, starting from the entrance. You first visit all rooms on the first floor, then all rooms on the second floor, and so on.

Start node: 1
Graph edges:
1 -> 2, 1 -> 3
2 -> 4
3 -> 5

Graph:
1 -> 2 -> 4
 ↓    ↓
 3 -> 5

Queue starts with: [1] ↑

Dry Run Walkthrough

Input: Graph with edges: 1->2, 1->3, 2->4, 3->5; start BFS from node 1

Goal: Visit all nodes in breadth-first order starting from node 1

Step 1: Start BFS from node 1, enqueue 1

Queue: [1↑]
Visited: {}

Why: We begin from the start node and mark it to visit its neighbors next

Step 2: Dequeue 1, visit neighbors 2 and 3, enqueue them

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

Why: Visit all neighbors of 1 before moving deeper

Step 3: Dequeue 2, visit neighbor 4, enqueue 4

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

Why: Explore neighbors of 2 after finishing 1's neighbors

Step 4: Dequeue 3, visit neighbor 5, enqueue 5

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

Why: Explore neighbors of 3 after finishing 2's neighbors

Step 5: Dequeue 4, no new neighbors

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

Why: 4 has no neighbors, so just mark visited

Step 6: Dequeue 5, no new neighbors

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

Why: 5 has no neighbors, BFS ends as queue is empty

Result:

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

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Graph
{
    private readonly Dictionary<int, List<int>> adjList = new();

    public void AddEdge(int u, int v)
    {
        if (!adjList.ContainsKey(u)) adjList[u] = new List<int>();
        adjList[u].Add(v);
        if (!adjList.ContainsKey(v)) adjList[v] = new List<int>();
    }

    public void BFS(int start)
    {
        var visited = new HashSet<int>();
        var queue = new Queue<int>();

        queue.Enqueue(start); // enqueue start node
        visited.Add(start);  // mark start visited

        while (queue.Count > 0)
        {
            int current = queue.Dequeue(); // dequeue front node
            Console.Write(current);
            Console.Write(" ");

            foreach (var neighbor in adjList[current])
            {
                if (!visited.Contains(neighbor))
                {
                    queue.Enqueue(neighbor); // enqueue unvisited neighbor
                    visited.Add(neighbor);  // mark neighbor visited
                }
            }
        }
        Console.WriteLine();
    }
}

class Program
{
    static void Main()
    {
        var graph = new Graph();
        graph.AddEdge(1, 2);
        graph.AddEdge(1, 3);
        graph.AddEdge(2, 4);
        graph.AddEdge(3, 5);

        graph.BFS(1);
    }
}

queue.Enqueue(start); // enqueue start node visited.Add(start); // mark start visited

Initialize BFS by adding start node to queue and marking visited

int current = queue.Dequeue(); // dequeue front node

Remove node from front of queue to process it

foreach (var neighbor in adjList[current])

Check all neighbors of current node

if (!visited.Contains(neighbor)) { queue.Enqueue(neighbor); // enqueue unvisited neighbor visited.Add(neighbor); // mark neighbor visited }

Add unvisited neighbors to queue and mark them visited to avoid repeats

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 set storing nodes

vs Alternative: Compared to DFS which uses stack and explores depth first, BFS uses queue and explores breadth first, useful for shortest path in unweighted graphs

Edge Cases

Empty graph (no nodes)

BFS does nothing as start node is not present

DSA C#

if (!adjList.ContainsKey(start)) return; // guard against missing start node

Graph with single node and no edges

BFS visits only the start node

DSA C#

visited.Add(start);  // mark start visited

Graph with disconnected nodes

BFS visits only nodes reachable from start node

DSA C#

foreach (var neighbor in adjList[current])

When to Use This Pattern

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

Common Mistakes

Mistake: Not marking nodes as visited before enqueueing causes repeated visits and infinite loops
Fix: Mark nodes as visited immediately when enqueueing to prevent 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 neighbors evenly.

The key is to use a queue to process nodes in the order they are discovered.

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