Illustrate Breadth First Search (BFS) in C# with example

Here's an example of a C# program that illustrates Breadth First Search (BFS) algorithm on a graph:

using System;
using System.Collections.Generic;

class Graph
{
    private int numVertices;
    private List> adjacencyList;

    public Graph(int vertices)
    {
        numVertices = vertices;
        adjacencyList = new List>(numVertices);
        for (int i = 0; i < numVertices; i++)
        {
            adjacencyList.Add(new List());
        }
    }

    public void AddEdge(int source, int destination)
    {
        adjacencyList[source].Add(destination);
        adjacencyList[destination].Add(source);
    }

    public void BFS(int startVertex)
    {
        bool[] visited = new bool[numVertices];
        Queue queue = new Queue();

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

        Console.WriteLine("Breadth First Traversal (starting from vertex " + startVertex + "):");

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

            List neighbors = adjacencyList[currentVertex];
            foreach (int neighbor in neighbors)
            {
                if (!visited[neighbor])
                {
                    visited[neighbor] = true;
                    queue.Enqueue(neighbor);
                }
            }
        }

        Console.WriteLine();
    }
}

class Program
{
    static void Main(string[] args)
    {
        Graph graph = new Graph(6);

        // Adding edges to the graph
        graph.AddEdge(0, 1);
        graph.AddEdge(0, 2);
        graph.AddEdge(1, 3);
        graph.AddEdge(2, 3);
        graph.AddEdge(2, 4);
        graph.AddEdge(3, 4);
        graph.AddEdge(3, 5);

        // Performing Breadth First Search (BFS) on the graph
        graph.BFS(0);
    }
}

In this program, we have a Graph class that represents a graph data structure. It has a constructor to initialize the number of vertices and an adjacency list to store the edges between vertices.

The AddEdge method is used to add an edge between two vertices. It takes the source vertex and destination vertex as input and adds them to each other's adjacency list.

The BFS method performs the Breadth First Search algorithm. It takes a start vertex as input and performs BFS starting from that vertex. It uses a boolean array visited to keep track of visited vertices and a Queue data structure to implement the BFS traversal. The method outputs the traversal sequence to the console.

In the Main method, we create an instance of the Graph class with 6 vertices and add edges to the graph. We then call the BFS method with a start vertex of 0 to perform BFS on the graph.

Breadth First Traversal (starting from vertex 0):
0 1 2 3 4 5

This demonstrates the implementation of Breadth First Search (BFS) algorithm in C#. The program performs BFS on the graph starting from vertex 0 and outputs the traversal sequence. The BFS traversal visits all vertices in the graph in breadth-first order.