Shortest Path in Unweighted Graph Using BFS 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](start);

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

AEnqueue

BPush

CAdd

DInsert

Attempts:

3 left

💡 Hint

Common Mistakes

Using Add or Push instead of Enqueue causes compilation errors.

In C#, the method to add an element to a queue is Enqueue.

2fill in blank

medium

Complete the code to mark the start node as visited.

DSA C#

bool[] visited = new bool[n];
visited[[1]] = true;

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

A1

Bn

Cstart

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or 1 directly instead of the start variable can cause wrong behavior.

We mark the start node as visited to avoid revisiting it.

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)
{
    int current = queue.Dequeue();
    // process neighbors
}

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

ASize

BCount

CLength

DCapacity

Attempts:

3 left

💡 Hint

Common Mistakes

Using Length or Size causes compilation errors.

The Count property gives the number of elements in the queue.

4fill in blank

hard

Fill both blanks to update the distance and enqueue the neighbor node.

DSA C#

if (!visited[neighbor])
{
    visited[neighbor] = true;
    distance[neighbor] = distance[[1]] + 1;
    queue.[2](neighbor);
}

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

Acurrent

Bstart

CEnqueue

DAdd

Attempts:

3 left

💡 Hint

Common Mistakes

Using start instead of current for distance update.

Using Add instead of Enqueue for queue.

Distance of neighbor is one more than current node's distance, and we add neighbor to the queue using Enqueue.

5fill in blank

hard

Fill all three blanks to reconstruct the shortest path from end to start.

DSA C#

List<int> path = new List<int>();
int node = end;
while (node != [1])
{
    path.[2](node);
    node = parent[[3]];
}
path.Add(start);
path.Reverse();

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

Astart

BAdd

Cnode

Dend

Attempts:

3 left

💡 Hint

Common Mistakes

Using end instead of start in loop condition.

Using wrong method instead of Add for list.

Using parent[end] instead of parent[node].

We loop until we reach the start node, add nodes to path using Add, and update node to its parent.

Practice

1. What does BFS (Breadth-First Search) help find in an unweighted graph?

easy

A. The total number of edges in the graph

B. The node with the highest degree

C. The longest path in the graph

D. The shortest path from a start node to all other nodes

Solution

1. Step 1: Understand BFS traversal

   BFS explores nodes level by level starting from the source node.

2. Step 2: BFS finds shortest paths in unweighted graphs

   Because BFS visits nodes in order of increasing distance, it finds shortest paths.

3. Final Answer:

   The shortest path from a start node to all other nodes -> Option D

4. Quick Check:

   BFS = Shortest path in unweighted graph [OK]

Hint: BFS explores neighbors level-wise to find shortest paths [OK]

Common Mistakes:

• Confusing BFS with DFS for shortest path
• Thinking BFS finds longest path
• Assuming BFS counts edges incorrectly

2. Which C# data structure is best to use as a queue for BFS implementation?

easy

A. Queue<T>

B. List<T>

C. Stack<T>

D. Dictionary

Solution

1. Step 1: Identify BFS traversal order

   BFS uses FIFO order to explore nodes level by level.

2. Step 2: Choose data structure matching FIFO

   Queue<T> provides FIFO behavior, perfect for BFS.

3. Final Answer:

   Queue<T> -> Option A

4. Quick Check:

   Queue = FIFO for BFS [OK]

Hint: Use Queue<T> for BFS to maintain correct node order [OK]

Common Mistakes:

• Using Stack<T> which is LIFO, wrong for BFS
• Using List<T> without queue behavior
• Confusing Dictionary with queue

3. What is the output distance array after running BFS from node 0 on this graph?

Graph edges:
0 - 1
0 - 2
1 - 3
2 - 3
3 - 4

Assume distance to start node 0 is 0 and unreachable nodes have distance -1.

medium

A. [0, 1, 1, 2, 3]

B. [0, 1, 2, 3, 4]

C. [0, 1, 1, 1, 2]

D. [0, -1, -1, -1, -1]

Solution

1. Step 1: Initialize distances and start BFS from node 0

   Distance[0] = 0; others = -1 initially.

2. Step 2: Visit neighbors level-wise

   From 0: nodes 1 and 2 get distance 1. From 1 and 2: node 3 gets distance 2. From 3: node 4 gets distance 3.

3. Final Answer:

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

4. Quick Check:

   Distances = [0,1,1,2,3] [OK]

Hint: Track distances level by level from start node [OK]

Common Mistakes:

• Assigning wrong distances to nodes
• Confusing BFS with DFS distances
• Not initializing unreachable nodes as -1

4. Identify the bug in this BFS shortest path code snippet in C#:

int[] dist = new int[n];
for (int i = 0; i < n; i++) dist[i] = -1;
Queue<int> q = new Queue<int>();
dist[start] = 0;
q.Enqueue(start);
while (q.Count > 0) {
  int u = q.Dequeue();
  foreach (int v in graph[u]) {
    if (dist[v] == 0) {
      dist[v] = dist[u] + 1;
      q.Enqueue(v);
    }
  }
}

medium

A. Enqueue should be done before setting dist[v]

B. Queue should be Stack for BFS

C. dist[v] == 0 should be dist[v] == -1 to check unvisited nodes

D. dist[start] should be -1 initially

Solution

1. Step 1: Understand distance initialization and visit check

   Distances start at -1 for unvisited nodes; 0 means visited or start node.

2. Step 2: Check condition for visiting neighbors

   Condition 'dist[v] == 0' wrongly treats unvisited nodes as visited; should be 'dist[v] == -1'.

3. Final Answer:

   dist[v] == -1 to check unvisited nodes -> Option C

4. Quick Check:

   Check unvisited with -1, not 0 [OK]

Hint: Use -1 to mark unvisited nodes in BFS distance array [OK]

Common Mistakes:

• Checking dist[v] == 0 instead of -1
• Using Stack instead of Queue for BFS
• Incorrect initial distance for start node

5. Given an unweighted graph with nodes 0 to 5 and edges:

0-1, 0-2, 1-3, 3-4, 4-5

What is the shortest path from node 0 to node 5 using BFS?

hard

A. [0, 2, 3, 4, 5]

B. [0, 1, 3, 4, 5]

C. [0, 1, 2, 3, 4, 5]

D. [0, 2, 4, 5]

Solution

1. Step 1: Run BFS from node 0 to find shortest distances

   Distances: 0(0), 1(1), 2(1), 3(2), 4(3), 5(4).

2. Step 2: Trace shortest path back from node 5

   From 5 to 4, 4 to 3, 3 to 1, 1 to 0: 0->1->3->4->5.

3. Final Answer:

   [0, 1, 3, 4, 5] -> Option B

4. Quick Check:

   Shortest path = [0,1,3,4,5] [OK]

Hint: Trace BFS parents backward to find shortest path [OK]

Common Mistakes:

• Attempting path via node 2 (no 2-3 edge)
• Skipping nodes in path
• Confusing BFS with DFS path