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();
```

- 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.
- g.AddEdge(0, 4); adds an edge between vertices 0 and 4.
- g.AddEdge(1, 2); adds an edge between vertices 1 and 2.
- g.AddEdge(1, 3); adds an edge between vertices 1 and 3.
- g.AddEdge(1, 4); adds an edge between vertices 1 and 4.
- g.AddEdge(2, 3); adds an edge between vertices 2 and 3.
- g.AddEdge(3, 4); adds an edge between vertices 3 and 4.
- 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.