BFS Breadth First Search on Graph in DSA C# - Build from Scratch

BFS Breadth First Search on Graph

📖 Scenario: You are working with a simple map of connected cities. Each city is connected to some other cities by roads. You want to explore the cities starting from a specific city and visit all reachable cities in order of their closeness.

🎯 Goal: Build a program that uses Breadth First Search (BFS) to visit all cities reachable from a starting city in the order of their distance. You will create the graph, set the starting city, write the BFS logic, and print the order of visited cities.

📋 What You'll Learn

Create a graph using a dictionary where keys are city names (strings) and values are lists of connected city names.

Set a starting city for BFS traversal.

Implement BFS using a queue to visit cities in breadth-first order.

Print the order of cities visited by BFS.

💡 Why This Matters

🌍 Real World

BFS is used in maps and navigation apps to find the shortest path or explore nearby locations first.

💼 Career

Understanding BFS is important for software engineers working on graph problems, network analysis, and search algorithms.

1

Create the graph data structure

Create a dictionary called graph with these exact entries: "A" connected to ["B", "C"], "B" connected to ["A", "D", "E"], "C" connected to ["A", "F"], "D" connected to ["B"], "E" connected to ["B", "F"], and "F" connected to ["C", "E"].

DSA C#

# Your code here

Hint

Use a Dictionary<string, List<string>> to represent the graph. Each key is a city name, and the value is a list of connected cities.

2

Set the starting city for BFS

Create a string variable called startCity and set it to "A".

DSA C#

using System.Collections.Generic;

Dictionary> graph = new Dictionary>
{
    { "A", new List { "B", "C" } },
    { "B", new List { "A", "D", "E" } },
    { "C", new List { "A", "F" } },
    { "D", new List { "B" } },
    { "E", new List { "B", "F" } },
    { "F", new List { "C", "E" } }
};

// Your code here

Hint

Just create a string variable named startCity and assign it the value "A".

3

Implement BFS traversal logic

Write code to perform BFS starting from startCity. Use a Queue<string> called queue and a HashSet<string> called visited. Enqueue startCity, mark it visited, then while queue is not empty, dequeue a city, enqueue its unvisited neighbors, and mark them visited. Store the order of visited cities in a List<string> called order.

DSA C#

using System.Collections.Generic;

Dictionary> graph = new Dictionary>
{
    { "A", new List { "B", "C" } },
    { "B", new List { "A", "D", "E" } },
    { "C", new List { "A", "F" } },
    { "D", new List { "B" } },
    { "E", new List { "B", "F" } },
    { "F", new List { "C", "E" } }
};

string startCity = "A";

// Your code here

Hint

Use a queue to keep track of cities to visit next. Use a hash set to remember visited cities. Add neighbors to the queue only if they are not visited yet.

4

Print the BFS traversal order

Write a foreach loop to print each city in the order list separated by spaces on one line.

DSA C#

using System;
using System.Collections.Generic;

Dictionary> graph = new Dictionary>
{
    { "A", new List { "B", "C" } },
    { "B", new List { "A", "D", "E" } },
    { "C", new List { "A", "F" } },
    { "D", new List { "B" } },
    { "E", new List { "B", "F" } },
    { "F", new List { "C", "E" } }
};

string startCity = "A";

Queue queue = new Queue();
HashSet visited = new HashSet();
List order = new List();

queue.Enqueue(startCity);
visited.Add(startCity);

while (queue.Count > 0)
{
    string city = queue.Dequeue();
    order.Add(city);

    foreach (string neighbor in graph[city])
    {
        if (!visited.Contains(neighbor))
        {
            queue.Enqueue(neighbor);
            visited.Add(neighbor);
        }
    }
}

// Print the BFS order below

Hint

Use a foreach loop to print each city in order followed by a space.

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