BFS for Disconnected Graph

Below is an implementation of the breadth-first search (BFS) algorithm for disconnected graphs. The BFS_for_Disconnected_Graph class represents a graph using an adjacency list, where _adj[v] is a list of the vertices adjacent to the vertex v. The class has three methods: a constructor, an AddEdge method, and a Bfs method.

class BFS_for_Disconnected_Graph
{
    int V;
    List<int>[] _adj;

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

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

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

        for (int i = 0; i < V; i++)
        {
            if (!visited[i])
            {
                queue.Enqueue(i);
                visited[i] = true;
                Console.WriteLine(i);

                while (queue.Count > 0)
                {
                    int v = queue.Dequeue();
                    foreach (int w in _adj[v])
                    {
                        if (!visited[w])
                        {
                            visited[w] = true;
                            queue.Enqueue(w);
                            Console.WriteLine(w);
                        }
                    }
                }
            }
        }
    }
}

The constructor takes an integer argument v representing the number of vertices in the graph and initializing the _adj field to an array of List<int> with length v. Each element of the array is initialized to an empty List<int>.

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

The AddEdge the method takes two integer arguments v and w representing the two vertices connected by an edge and adds w to the adjacency list of v.

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

The Bfs method performs a breadth-first search traversal on the graph. It uses a boolean array visited to keep track of which vertices have been visited and a queue to store the vertices to be visited. The method iterates over all vertices in the graph and performs a BFS traversal starting from each unvisited vertex. This ensures that all connected components of the graph are visited.

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


         for (int i = 0; i < V; i++)
         {
             if (!visited[i])
             {
                 queue.Enqueue(i);
                 visited[i] = true;
                 Console.WriteLine(i);

                 while (queue.Count > 0)
                 {
                     int v = queue.Dequeue();
                     foreach (int w in _adj[v])
                     {
                         if (!visited[w])
                         {
                             visited[w] = true;
                             queue.Enqueue(w);
                             Console.WriteLine(w);
                         }
                     }
                 }
             }
         }

     }

The time complexity of this implementation is O(V+E), where V is the number of vertices in the graph, and E is the number of edges. This is because each vertex and each edge is visited exactly once during the BFS traversal.

Let's see an example below.

 BFS_for_Disconnected_Graph g = new BFS_for_Disconnected_Graph(5); 
 g.AddEdge(0, 4);
 g.AddEdge(1, 2);
 g.AddEdge(1, 3);
 g.AddEdge(1, 4);
 g.AddEdge(2, 3);
 g.AddEdge(3, 4);
 g.Bfs();

1. BFS_for_Disconnected_Graph g = new BFS_for_Disconnected_Graph(5); creates a new instance of the BFS_for_Disconnected_Graph class with 5 vertices. The adjacency list for each vertex is initialized to an empty list.
2. g.AddEdge(0, 4); adds an edge between vertices 0 and 4.
3. g.AddEdge(1, 2); adds an edge between vertices 1 and 2.
4. g.AddEdge(1, 3); adds an edge between vertices 1 and 3.
5. g.AddEdge(1, 4); adds an edge between vertices 1 and 4.
6. g.AddEdge(2, 3); adds an edge between vertices 2 and 3.
7. g.AddEdge(3, 4); adds an edge between vertices 3 and 4.
8. g.Bfs(); performs a BFS traversal on the graph starting from vertex 0.

After running this code, the BFS traversal will visit the vertices in the following order: 0, 4, 1, 3, 2.