Write an algorithm which counts the number of connected components in a graph G = (V, E) such that the vertices of G are labeled from 1 to n.

The problem is asking to find the number of connected components in a graph. A connected component of an undirected graph is a subgraph in which any two vertices are connected to each other by a path, and which is connected to no additional vertices in the graph.

We can solve this problem using Depth First Search (DFS) or Breadth First Search (BFS) algorithm. Here, I will explain the DFS approach.

Algorithm:

1. Initialize all vertices as not visited.
2. Do the following for every vertex v:
   • If v is not visited before, call DFS(v) and increment the count of connected components.
3. Print the count of connected components.

DFS(v):

1. Mark v as visited and print v.
2. Do the following for every adjacent u of v:
   • If u is not visited, then recursively call DFS(u).

Here is the Python code for the above algorithm:

from collections import defaultdict

class Graph:

    def __init__(self, vertices):
        self.V = vertices
        self.graph = defaultdict(list)

    def addEdge(self, v, w):
        self.graph[v].append(w)
        self.graph[w].append(v)

    def DFSUtil(self, v, visited):
        visited[v] = True
        for i in self.graph[v]:
            if visited[i] == False:
                self.DFSUtil(i, visited)

    def connectedComponents(self):
        visited = [False] * (self.V)
        count = 0
        for v in range(self.V):
            if visited[v] == False:
                self.DFSUtil(v, visited)
                count += 1
        return count

In the above code, DFSUtil(v, visited) is a utility function that does DFS traversal. It uses recursive DFSUtil() to visit all the connected vertices.

The function connectedComponents() uses a visited array to check whether a vertex is visited or not. It does DFS traversal for every vertex and increments count of connected components for every unvisited vertex.

This algorithm runs in O(V+E) time, where V is the number of vertices and E is the number of edges in the graph.

Example:

Let's consider a graph with 5 vertices and edges as {(1, 0), (2, 3), (3, 4)}. The connected components in the graph are {0, 1} and {2, 3, 4}.

g1 = Graph(5)
g1.addEdge(1, 0)
g1.addEdge(2, 3)
g1.addEdge(3, 4)
print("Number of connected components:", g1.connectedComponents())  # Output: 2

In this example, the algorithm first visits vertex 0, then it goes to vertex 1, and marks both as visited. Then it visits vertex 2, goes to vertex 3, then to vertex 4, and marks all as visited. So, the total number of connected components in the graph is 2.