BFS Breadth First Search on Graph in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the queue for BFS traversal.

DSA C#

Queue<int> queue = new Queue<int>();
queue.[1](startNode);

Drag options to blanks, or click blank then click option'

APush

BEnqueue

CAdd

DInsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using stack methods like Push instead of queue methods.

Trying to use Add or Insert which are not queue methods.

The Enqueue method adds an element to the end of the queue, which is needed to start BFS.

2fill in blank

medium

Complete the code to dequeue the next node in BFS.

DSA C#

int current = queue.[1]();

Drag options to blanks, or click blank then click option'

ADequeue

BPop

CRemove

DPoll

Attempts:

3 left

💡 Hint

Common Mistakes

Using Pop which is for stacks, not queues.

Using Remove which is not a queue method.

The Dequeue method removes and returns the element at the front of the queue, which is needed to process nodes in BFS order.

3fill in blank

hard

Fix the error in the BFS loop condition to continue while the queue is not empty.

DSA C#

while (queue.[1] > 0) {
    // BFS logic
}

Drag options to blanks, or click blank then click option'

ACount

BLength

CSize

DCapacity

Attempts:

3 left

💡 Hint

Common Mistakes

Using Length or Size which are not properties of Queue in C#.

Using Capacity which is the allocated space, not the current count.

The Count property gives the number of elements in the queue. We continue while it is greater than zero.

4fill in blank

hard

Fill both blanks to check if a neighbor node is not visited and then mark it visited.

DSA C#

if (visited[neighbor][1]) {
    visited[neighbor] = [2];
    queue.Enqueue(neighbor);
}

Drag options to blanks, or click blank then click option'

A]

Btrue

C== false

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Using just ']' without a comparison in the condition.

Marking visited as false instead of true.

The condition visited[neighbor] == false checks if the neighbor is not visited. Then we mark it visited by setting true.

5fill in blank

hard

Fill all three blanks to complete the BFS method signature and initialize the visited array.

DSA C#

public void BFS(int [1], List<int>[] [2]) {
    bool[] visited = new bool[[3]];
    // BFS logic
}

Drag options to blanks, or click blank then click option'

AstartNode

Bgraph

Cgraph.Length

Dnodes

Attempts:

3 left

💡 Hint

Common Mistakes

Using incorrect parameter names that don't match the graph or start node.

Using a wrong size for the visited array.

The method takes a starting node startNode and a graph represented as an adjacency list graph. The visited array size is the number of nodes, which is graph.Length.

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