Breadth First Search for a Graph

In this article, I'm going to explain the BFS traversal of graphs. The graph is a very important topic in data structure and algorithms, and this is also important from the interview point of view.

 class BfsGraph
    {
        LinkedList<int>[] _adj;
        int _V;

        public BfsGraph(int v)
        {
            _adj = new LinkedList<int>[v];

            for (int i = 0; i < v; i++)
            {
                _adj[i] = new LinkedList<int>();
            }
            _V = v;

        }

        public void AddEdge(int v, int w)
        {
            _adj[v].AddLast(w);
        }

        public void BFS(int v)
        {

            Queue<int> q = new Queue<int>();
            bool[] flag = new bool[_V];


            q.Enqueue(v);
            flag[v] = true;
            Console.WriteLine(v);

            while (q.Count > 0)
            {
                int w = q.Dequeue();
                LinkedList<int> linledList = _adj[w];
                LinkedListNode<int> currentNode = linledList.First;
                while (currentNode != null && !flag[currentNode.Value])
                {
                    Console.WriteLine(currentNode.Value);
                    q.Enqueue(currentNode.Value);
                    flag[currentNode.Value] = true;
                    currentNode = currentNode.Next;
                }
            }


        }


    }

Above C# code defines a class named BfsGraph that represents a graph data structure and implements the Breadth-First Search (BFS) algorithm. The class has two instance variables: _adj, which is an array of LinkedList<int> objects representing the adjacency list of the graph, and _V, which is an int representing the number of vertices in the graph.

The BfsGraph constructor takes an int parameter v representing the number of vertices in the graph. It initializes the _adj array with a new array of LinkedList<int> objects of size v, and sets the value of _V to v. The constructor also initializes each element of the _adj array with a new LinkedList<int> object.

The AddEdge method takes two int parameters, v and w, representing two vertices in the graph. It adds an edge between these two vertices by adding w to the end of the linked list at the index v in the _adj array.

The BFS method takes an int parameter v representing the starting vertex for the BFS traversal. It creates a new Queue<int> object to store the vertices to be visited and a new bool[] array to keep track of which vertices have been visited. The method enqueues the starting vertex v, sets its corresponding element in the flag array to true, and outputs its value using Console.WriteLine.

The method then enters a loop that continues until the queue is empty. In each iteration, it dequeues a vertex from the queue, retrieves its adjacency list from the _adj array, and iterates over its elements using a while loop. For each unvisited vertex in the adjacency list, it outputs its value using Console.WriteLine, enqueues it and sets its corresponding element in the flag array to true.

Here’s an example that demonstrates how to use this class to create a graph with 4 vertices and perform a BFS traversal starting from vertex 2:

var graph = new BfsGraph(4);
graph.AddEdge(0, 1);
graph.AddEdge(0, 2);
graph.AddEdge(1, 2);
graph.AddEdge(2, 0);
graph.AddEdge(2, 3);
graph.AddEdge(3, 3);

Console.WriteLine("Breadth First Traversal starting from vertex 2:");
graph.BFS(2);

This code creates a new instance of the BfsGraph class with 4 vertices, adds edges between them using the AddEdge method, and performs a BFS traversal starting from vertex 2 using the BFS method. The output of this code would be:

Breadth First Traversal starting from vertex 2:
2
0
3
1

Time Complexity: O(v+e), where v is the number of nodes and e is the number of edges.

Auxiliary Space: O(v)