BFS Breadth First Search on Graph in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does BFS stand for in graph traversal?

BFS stands for Breadth First Search, a method to explore nodes level by level starting from a source node.

beginner

In BFS, which data structure is primarily used to keep track of nodes to visit next?

A queue is used in BFS to keep track of nodes to visit next, ensuring nodes are explored in the order they were discovered.

intermediate

What is the main difference between BFS and DFS in graph traversal?

BFS explores nodes level by level using a queue, while DFS explores as deep as possible along each branch using a stack or recursion.

intermediate

What is the time complexity of BFS on a graph with V vertices and E edges?

The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges.

beginner

Why do we mark nodes as visited in BFS?

Marking nodes as visited prevents revisiting the same node multiple times, avoiding infinite loops and ensuring correct traversal.

Which data structure is used in BFS to store nodes to be explored next?

A HashSet

B Stack

C Queue

D Priority Queue

BFS uses a queue to explore nodes in the order they are discovered, ensuring level-by-level traversal.

What is the first step in BFS starting from a source node?

A Remove the source node from the graph

B Add all neighbors of the source node to the queue

C Mark all nodes as visited

D Add the source node to the queue and mark it visited

BFS starts by adding the source node to the queue and marking it visited to begin traversal.

What happens when BFS dequeues a node?

A It deletes the node from the graph

B It explores all unvisited neighbors and adds them to the queue

C It marks the node as unvisited

D It immediately stops the traversal

When BFS dequeues a node, it visits all its unvisited neighbors and adds them to the queue for future exploration.

Which of the following is NOT true about BFS?

A It uses a stack to manage nodes

B It explores nodes level by level

C It can find the shortest path in an unweighted graph

D It requires marking nodes as visited

BFS uses a queue, not a stack, to manage nodes during traversal.

What is the space complexity of BFS in terms of vertices V?

A O(V)

B O(1)

C O(V^2)

D O(log V)

BFS requires space to store the queue and visited nodes, which can be up to O(V) in the worst case.

Explain how BFS traverses a graph starting from a source node.

Think about visiting nodes in layers and how the queue helps.

Describe the differences between BFS and DFS in graph traversal.

Focus on the order nodes are visited and data structures used.

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