C# Program to Implement BFS (Breadth-First Search)

A C# program to implement BFS uses a Queue to explore nodes level by level, starting from a source node, visiting neighbors before moving deeper, like Queue queue = new Queue(); and processing nodes until all reachable nodes are visited.

Examples

InputGraph edges: 0->1, 0->2, 1->2, 2->0, 2->3, 3->3; Start node: 2

Output2 0 3 1

InputGraph edges: 0->1, 1->2, 2->3; Start node: 0

Output0 1 2 3

InputGraph edges: 0->1; Start node: 1

Output1

How to Think About It

To implement BFS, think of exploring a graph like visiting rooms in a building floor by floor. Start at the given node, visit all its neighbors first, then move to neighbors of those neighbors, and so on. Use a queue to keep track of nodes to visit next and a set or array to remember which nodes are already visited to avoid repeats.

Algorithm

1

Create a queue and add the start node to it.

2

Mark the start node as visited.

3

While the queue is not empty, do:

4

Remove the front node from the queue and process it (e.g., print it).

5

Add all unvisited neighbors of this node to the queue and mark them visited.

6

Repeat until all reachable nodes are processed.

Code

csharp

using System;
using System.Collections.Generic;

class BFSExample {
    static void BFS(Dictionary<int, List<int>> graph, int start) {
        var visited = new HashSet<int>();
        var queue = new Queue<int>();
        visited.Add(start);
        queue.Enqueue(start);

        while (queue.Count > 0) {
            int node = queue.Dequeue();
            Console.Write(node + " ");
            foreach (var neighbor in graph[node]) {
                if (!visited.Contains(neighbor)) {
                    visited.Add(neighbor);
                    queue.Enqueue(neighbor);
                }
            }
        }
    }

    static void Main() {
        var graph = new Dictionary<int, List<int>> {
            {0, new List<int>{1, 2}},
            {1, new List<int>{2}},
            {2, new List<int>{0, 3}},
            {3, new List<int>{3}}
        };
        BFS(graph, 2);
    }
}

Output

2 0 3 1 

Dry Run

Let's trace BFS on the graph starting from node 2.

1

Initialize

visited = {2}, queue = [2]

2

Dequeue 2

Print 2; neighbors = [0, 3]; visited = {2}; queue = []

3

Enqueue neighbors of 2

Add 0 and 3 to visited and queue; visited = {2,0,3}; queue = [0,3]

4

Dequeue 0

Print 0; neighbors = [1, 2]; visited = {2,0,3}; queue = [3]

5

Enqueue neighbor 1

1 not visited, add to visited and queue; visited = {1,2,0,3}; queue = [3,1]

6

Dequeue 3

Print 3; neighbors = [3]; visited = {1,2,0,3}; queue = [1]

7

Neighbor 3 already visited

No new nodes added; queue = [1]

8

Dequeue 1

Print 1; neighbors = [2]; visited = {1,2,0,3}; queue = []

9

Neighbor 2 already visited

No new nodes added; queue = []

Queue	Visited	Output
[2]	{2}
[]	{2}	2
[0,3]	{0,2,3}	2
[3]	{0,2,3}	2 0
[3,1]	{0,1,2,3}	2 0
[1]	{0,1,2,3}	2 0 3
[1]	{0,1,2,3}	2 0 3
[]	{0,1,2,3}	2 0 3 1

Why This Works

Step 1: Use a queue to explore nodes

The queue ensures nodes are visited in the order they are discovered, which is key to BFS's level-by-level traversal.

Step 2: Track visited nodes

Marking nodes as visited prevents revisiting and infinite loops in cyclic graphs.

Step 3: Process neighbors

Adding neighbors to the queue after visiting a node ensures all nodes at the current depth are processed before moving deeper.

Alternative Approaches

Recursive BFS using a helper function

csharp

using System;
using System.Collections.Generic;

class RecursiveBFS {
    static void BFS(Dictionary<int, List<int>> graph, Queue<int> queue, HashSet<int> visited) {
        if (queue.Count == 0) return;
        int node = queue.Dequeue();
        Console.Write(node + " ");
        foreach (var neighbor in graph[node]) {
            if (!visited.Contains(neighbor)) {
                visited.Add(neighbor);
                queue.Enqueue(neighbor);
            }
        }
        BFS(graph, queue, visited);
    }

    static void Main() {
        var graph = new Dictionary<int, List<int>> {
            {0, new List<int>{1, 2}},
            {1, new List<int>{2}},
            {2, new List<int>{0, 3}},
            {3, new List<int>{3}}
        };
        var visited = new HashSet<int>{2};
        var queue = new Queue<int>();
        queue.Enqueue(2);
        BFS(graph, queue, visited);
    }
}

Uses recursion instead of a loop; less common and can cause stack overflow on large graphs.

BFS using adjacency matrix

csharp

using System;
using System.Collections.Generic;

class BFSMatrix {
    static void BFS(int[,] graph, int start) {
        int n = graph.GetLength(0);
        var visited = new bool[n];
        var queue = new Queue<int>();
        visited[start] = true;
        queue.Enqueue(start);

        while (queue.Count > 0) {
            int node = queue.Dequeue();
            Console.Write(node + " ");
            for (int i = 0; i < n; i++) {
                if (graph[node, i] == 1 && !visited[i]) {
                    visited[i] = true;
                    queue.Enqueue(i);
                }
            }
        }
    }

    static void Main() {
        int[,] graph = {
            {0,1,1,0},
            {0,0,1,0},
            {1,0,0,1},
            {0,0,0,1}
        };
        BFS(graph, 2);
    }
}

Uses a matrix to represent edges; simpler for dense graphs but uses more memory.

Complexity: O(V + E) time, O(V) space

Time Complexity

BFS visits each vertex once and checks all edges once, so time is proportional to vertices plus edges.

Space Complexity

The queue and visited set store up to all vertices, so space is proportional to the number of vertices.

Which Approach is Fastest?

Using adjacency lists is generally faster and more memory efficient than adjacency matrices for sparse graphs.

Approach	Time	Space	Best For
Adjacency List BFS	O(V + E)	O(V)	Sparse graphs, memory efficient
Adjacency Matrix BFS	O(V^2)	O(V^2)	Dense graphs, simple edge checks
Recursive BFS	O(V + E)	O(V) + call stack	Small graphs, educational use