BFS Breadth First Search on Graph in DSA C# - Time & Space Complexity

Time Complexity: BFS Breadth First Search on Graph

O(n + m)

Understanding Time Complexity

We want to understand how the time needed to explore a graph grows as the graph gets bigger using BFS.

How does BFS's work change when the graph has more nodes and edges?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// BFS on a graph using adjacency list
void BFS(int start, List<int>[] graph) {
    bool[] visited = new bool[graph.Length];
    Queue<int> queue = new Queue<int>();
    visited[start] = true;
    queue.Enqueue(start);

    while (queue.Count > 0) {
        int node = queue.Dequeue();
        foreach (int neighbor in graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.Enqueue(neighbor);
            }
        }
    }
}
    

This code explores all nodes reachable from the start node using BFS on a graph represented by adjacency lists.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Visiting each node and checking all its neighbors in the adjacency list.
• How many times: Each node is enqueued and dequeued once; each edge is checked once in the neighbor loops.

How Execution Grows With Input

As the graph grows, BFS visits every node and edge once.

Input Size (n nodes, m edges)	Approx. Operations
10 nodes, 15 edges	About 10 + 15 = 25 operations
100 nodes, 200 edges	About 100 + 200 = 300 operations
1000 nodes, 5000 edges	About 1000 + 5000 = 6000 operations

Pattern observation: The work grows roughly with the sum of nodes and edges, so more nodes or edges means more work.

Final Time Complexity

Time Complexity: O(n + m)

This means BFS takes time proportional to the number of nodes plus the number of edges in the graph.

Common Mistake

[X] Wrong: "BFS always takes O(n²) time because it uses nested loops."

[OK] Correct: BFS uses adjacency lists, so it only checks each edge once, not all pairs of nodes. The loops are not nested over all nodes but over neighbors, which keeps it efficient.

Interview Connect

Understanding BFS time complexity helps you explain how graph searches scale and why BFS is efficient for many problems. This skill shows you can analyze algorithms clearly and confidently.

Self-Check

"What if the graph was represented by an adjacency matrix instead of adjacency lists? How would the time complexity change?"

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