BFS Breadth First Search on Graph in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of BFS traversal on a simple graph

What is the output of the BFS traversal starting from node 0 in the given graph?

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    private int V;
    private List<int>[] adj;

    public Graph(int v) {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int v, int w) {
        adj[v].Add(w);
        adj[w].Add(v);
    }

    public void BFS(int s) {
        bool[] visited = new bool[V];
        Queue<int> queue = new Queue<int>();

        visited[s] = true;
        queue.Enqueue(s);

        while (queue.Count != 0) {
            s = queue.Dequeue();
            Console.Write(s + " ");

            foreach (int n in adj[s]) {
                if (!visited[n]) {
                    visited[n] = true;
                    queue.Enqueue(n);
                }
            }
        }
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(4);
        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(1, 2);
        g.AddEdge(2, 3);

        g.BFS(0);
    }
}

A 0 3 1 2

B 0 2 1 3

C 0 1 3 2

D 0 1 2 3

💡 Hint

Remember BFS visits neighbors level by level, starting from the source node.

BFS starts at node 0, visits its neighbors 1 and 2 in order, then visits neighbors of 1 and 2. Node 3 is neighbor of 2, so it is visited last.

🧠 Conceptual

intermediate

BFS queue usage explanation

Why does BFS use a queue data structure during traversal?

A To sort nodes by their values before visiting.

B To store nodes in reverse order for depth-first traversal.

C To explore nodes in the order they are discovered, ensuring level-by-level traversal.

D To keep track of visited nodes only.

💡 Hint

Think about how BFS visits nodes closest to the start first.

BFS uses a queue to process nodes in the order they are discovered, which ensures nodes are visited level by level from the source.

🔧 Debug

advanced

Identify the error in BFS implementation

What error will occur when running this BFS code snippet?

DSA C#

bool[] visited = new bool[V];
Queue<int> queue = new Queue<int>();

visited[s] = true;
queue.Enqueue(s);

while (queue.Count != 0) {
    s = queue.Dequeue();
    Console.Write(s + " ");

    foreach (int n in adj[s]) {
        if (visited[n]) {
            visited[n] = true;
            queue.Enqueue(n);
        }
    }
}

A No nodes are enqueued after the first, so only the start node is printed.

B No output, infinite loop occurs.

C Runtime error: NullReferenceException.

D Syntax error due to missing semicolon.

💡 Hint

Check the condition inside the foreach loop for visiting neighbors.

The condition 'if (visited[n])' is incorrect. It should be 'if (!visited[n])' to enqueue unvisited neighbors. Because of this, no new nodes are enqueued after the start node.

🚀 Application

advanced

Find shortest path length using BFS

Given an unweighted graph, which BFS modification helps find the shortest path length from source to all nodes?

A Maintain a distance array updated when nodes are first visited.

B Use a stack instead of a queue for traversal.

C Visit nodes multiple times to update distances.

D Ignore visited nodes to explore all paths.

💡 Hint

Shortest path in unweighted graph is number of edges from source.

BFS can find shortest paths by tracking distance from source when nodes are first visited. Using a queue ensures shortest paths are found first.

❓ Predict Output

expert

BFS traversal output on disconnected graph

What is the output of BFS starting from node 0 on this disconnected graph?

DSA C#

using System;
using System.Collections.Generic;

class Graph {
    private int V;
    private List<int>[] adj;

    public Graph(int v) {
        V = v;
        adj = new List<int>[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new List<int>();
        }
    }

    public void AddEdge(int v, int w) {
        adj[v].Add(w);
        adj[w].Add(v);
    }

    public void BFS(int s) {
        bool[] visited = new bool[V];
        Queue<int> queue = new Queue<int>();

        visited[s] = true;
        queue.Enqueue(s);

        while (queue.Count != 0) {
            s = queue.Dequeue();
            Console.Write(s + " ");

            foreach (int n in adj[s]) {
                if (!visited[n]) {
                    visited[n] = true;
                    queue.Enqueue(n);
                }
            }
        }
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(6);
        g.AddEdge(0, 1);
        g.AddEdge(0, 2);
        g.AddEdge(3, 4);
        g.AddEdge(4, 5);

        g.BFS(0);
    }
}

A 0 1 2 3 4 5

B 0 1 2

C 0 2 1 3 4 5

D 0 1 2 4 5

💡 Hint

BFS only visits nodes reachable from the start node.

The graph has two disconnected parts: nodes 0,1,2 and nodes 3,4,5. Starting BFS at 0 visits only nodes 0,1,2.

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