Number of Connected Components in an Undirected Graph

January 6, 2024

Problem #

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example: #

Input: n = 5, edges = [[0, 1], [1, 2], [3, 4]]
Output: 2
Explanation: There are two connected components: 0-1-2 and 3-4.

Solution #

Algorithm: Depth-First Search (DFS)

The idea is to use DFS to explore each node and mark all nodes in the same connected component as visited. The number of times a new DFS is initiated gives the number of connected components.

Algorithm Steps: #

1. Create an Adjacency List: Represent the graph using an adjacency list.
2. DFS Traversal: For each unvisited node, perform a DFS traversal and mark all reachable nodes as visited.
3. Count Connected Components: Each time a new DFS starts, increment the count of connected components.

Python Code #

def countComponents(n, edges):
    def dfs(node):
        if visited[node]:
            return
        visited[node] = True
        for neighbor in adj_list[node]:
            dfs(neighbor)

    # Create an adjacency list
    adj_list = {i: [] for i in range(n)}
    for edge in edges:
        adj_list[edge[0]].append(edge[1])
        adj_list[edge[1]].append(edge[0])

    visited = [False] * n
    count = 0
    for i in range(n):
        if not visited[i]:
            dfs(i)
            count += 1
    return count

# Example Usage
n = 5
edges = [[0, 1], [1, 2], [3, 4]]
print(countComponents(n, edges))
# Output: 2

Time Complexity: #

• O(V + E): Where V is the number of vertices and E is the number of edges. The adjacency list is traversed completely.

Space Complexity: #

• O(V + E): Space for the adjacency list and the visited array.