Shortest Path in Unweighted Graph Using BFS in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS Shortest Path Distances

What is the output of the following C# code that finds shortest distances from node 0 in an unweighted graph?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int n = 5;
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) graph[i] = new List<int>();
        graph[0].Add(1); graph[0].Add(2);
        graph[1].Add(2); graph[1].Add(3);
        graph[2].Add(3);
        graph[3].Add(4);

        int[] dist = new int[n];
        for (int i = 0; i < n; i++) dist[i] = -1;
        dist[0] = 0;

        Queue<int> q = new Queue<int>();
        q.Enqueue(0);

        while (q.Count > 0) {
            int u = q.Dequeue();
            foreach (int v in graph[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    q.Enqueue(v);
                }
            }
        }

        Console.WriteLine(string.Join(",", dist));
    }
}

A "0,1,2,3,4"

B "0,1,1,2,3"

C "0,1,1,1,2"

D "0,-1,-1,-1,-1"

💡 Hint

Think about how BFS explores neighbors level by level and assigns distances.

The BFS starts from node 0 with distance 0. It visits nodes 1 and 2 next, assigning distance 1. Then node 3 is reached from nodes 1 or 2 with distance 2, and finally node 4 from node 3 with distance 3.

🧠 Conceptual

intermediate

Why BFS is used for shortest path in unweighted graphs?

Why is BFS the preferred method to find the shortest path in an unweighted graph?

A Because BFS explores nodes in order of increasing distance from the start node.

B Because BFS uses a stack to explore nodes deeply first.

C Because BFS always finds the longest path first.

D Because BFS ignores visited nodes and revisits them multiple times.

💡 Hint

Think about how BFS visits nodes level by level.

BFS explores nodes in layers, starting from the source node and moving outward. This ensures the first time a node is visited, it is via the shortest path.

🔧 Debug

advanced

Identify the bug in BFS shortest path code

What error will this BFS shortest path code produce when run?

DSA C#

int n = 4;
List<int>[] graph = new List<int>[n];
for (int i = 0; i < n; i++) graph[i] = new List<int>();
graph[0].Add(1);
graph[1].Add(2);
graph[2].Add(3);

int[] dist = new int[n];
for (int i = 0; i < n; i++) dist[i] = -1;
dist[0] = 0;

Queue<int> q = new Queue<int>();
q.Enqueue(0);

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);
        }
    }
}

Console.WriteLine(string.Join(",", dist));

A Infinite loop or incorrect distances due to wrong visited check

B Output: 0,0,0,0

C Compilation error due to missing semicolon

D Output: 0,1,2,3

💡 Hint

Check the condition that decides if a node is visited.

The condition 'if (dist[v] == 0)' is wrong because distance 0 means the node is the start node. Unvisited nodes have distance -1. This causes nodes to be revisited incorrectly, leading to infinite loops or wrong distances.

❓ Predict Output

advanced

Shortest path reconstruction output

What is the output of the following code that reconstructs the shortest path from node 0 to node 4?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static void Main() {
        int n = 5;
        List<int>[] graph = new List<int>[n];
        for (int i = 0; i < n; i++) graph[i] = new List<int>();
        graph[0].Add(1); graph[0].Add(2);
        graph[1].Add(3);
        graph[2].Add(3);
        graph[3].Add(4);

        int[] dist = new int[n];
        int[] parent = new int[n];
        for (int i = 0; i < n; i++) {
            dist[i] = -1;
            parent[i] = -1;
        }
        dist[0] = 0;

        Queue<int> q = new Queue<int>();
        q.Enqueue(0);

        while (q.Count > 0) {
            int u = q.Dequeue();
            foreach (int v in graph[u]) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    parent[v] = u;
                    q.Enqueue(v);
                }
            }
        }

        List<int> path = new List<int>();
        int cur = 4;
        while (cur != -1) {
            path.Add(cur);
            cur = parent[cur];
        }
        path.Reverse();

        Console.WriteLine(string.Join(" -> ", path) + " -> null");
    }
}

A 0 -> 3 -> 4 -> null

B 0 -> 2 -> 3 -> 4 -> null

C 0 -> 1 -> 3 -> 4 -> null

D 4 -> 3 -> 1 -> 0 -> null

💡 Hint

Check which parent is assigned first for node 3.

Node 3 is first reached from node 1, so parent[3] = 1. The path from 0 to 4 is 0 -> 1 -> 3 -> 4.

🧠 Conceptual

expert

Time complexity of BFS shortest path in unweighted graph

What is the time complexity of BFS when used to find the shortest path in an unweighted graph with V vertices and E edges?

A O(E^2)

B O(V * E)

C O(V^2)

D O(V + E)

💡 Hint

Consider how many times each vertex and edge is processed.

BFS visits each vertex once and explores all edges from each vertex once, resulting in O(V + E) time complexity.

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