Number of Connected Components in an Undirected Graph

Connected Components in Graph Theory

In graph theory, the concept of connectedness is central to understanding how nodes, or vertices, relate to each other. In an undirected graph, a connected component is a set of vertices that are all reachable from each other through a series of edges, and disconnected from any other set of nodes.

But what if you're given a graph and asked:
"How many connected components are there?"
That’s exactly what the Number of Connected Components in an Undirected Graph problem is all about.

This guide explains everything—from foundational concepts to efficient algorithms—so you can master this problem and use it in practical applications like network clustering, system partitioning, and even social network analysis.

What Is an Undirected Graph and Why Components Matter?

An undirected graph consists of a set of vertices connected by edges where each edge is bidirectional. This means if vertex A is connected to vertex B, you can go both ways—A to B and B to A.

Understanding components is crucial in analyzing a graph’s connectivity. A graph may be:

• Fully connected (1 component)
• Partially connected (multiple components)

Component count tells us how many isolated subgraphs exist within the larger graph.

Graph Representation: Adjacency List vs Adjacency Matrix

Before we perform any graph traversal, we need to represent the graph properly.

• Adjacency List: Stores each vertex with a list of its neighbors. Space-efficient for sparse graphs.
• Adjacency Matrix: A 2D grid indicating direct connections between all pairs of vertices. Useful for dense graphs.

Example of an adjacency list:

1
2
3
4
5
6
graph = {
    0: [1],
    1: [0, 2],
    2: [1],
    3: []
}

This example shows 2 connected components: {0,1,2} and {3}.

Graph Traversal to Count Components

Depth-First Search (DFS)

A popular approach to count connected components is to use depth-first search.

DFS recursively explores each unvisited node and all nodes connected to it. Once one component is explored, we increment our component count.

DFS Implementation:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def countComponents(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = [False] * n

    def dfs(node):
        for neighbor in graph[node]:
            if not visited[neighbor]:
                visited[neighbor] = True
                dfs(neighbor)

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

    return count

Code Explanation:

• We first build the adjacency list to represent the undirected graph.
• The dfs() function recursively visits all vertices in a component.
• We keep a visited list to avoid revisiting nodes.
• For each unvisited node, we run DFS and increase the component count.

Time Complexity:

• Building the graph: O(V + E) where V is number of vertices, and E is number of edges.
• Traversal: Each node and edge is visited once → O(V + E).
• Overall time complexity: O(V + E)

Breadth-First Search (BFS)

Another graph traversal method is breadth-first search, which uses a queue to explore neighbors level by level.

BFS Version:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from collections import deque

def countComponents(n, edges):
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    visited = [False] * n
    count = 0

    for i in range(n):
        if not visited[i]:
            queue = deque([i])
            visited[i] = True
            while queue:
                node = queue.popleft()
                for neighbor in graph[node]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        queue.append(neighbor)
            count += 1

    return count

Code Explanation:

• Uses a queue for graph traversal layer by layer.
• For each unvisited node, we start a BFS traversal to mark all reachable vertices.
• Each component is explored fully before moving to the next.

Time Complexity:

• Building the adjacency list: O(V + E)
• Traversing each node and edge once: O(V + E)
• Overall time complexity: O(V + E)

Efficient Component Count with Union-Find Data Structure

When the number of vertices and edges is large, we prefer using the union-find data structure, also known as disjoint sets. It helps track and merge components efficiently.

Union-Find with Path Compression

Code Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def countComponents(n, edges):
    parent = list(range(n))

    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]

    def union(x, y):
        rootX = find(x)
        rootY = find(y)
        if rootX != rootY:
            parent[rootX] = rootY

    for u, v in edges:
        union(u, v)

    return len(set(find(i) for i in range(n)))

Code Explanation:

• Initializes each vertex as its own parent in the disjoint sets.
• find() uses path compression to flatten the tree for faster access.
• union() merges sets to reduce connected components.
• Final step counts the unique root parents, which equals the component count.

Time Complexity:

• Find and Union operations are near constant with path compression: O(α(N)), where α is the inverse Ackermann function.
• Total time for all operations: O(E × α(N)) + O(N × α(N))
• Overall: O(N + E × α(N)) — nearly linear in practice.

Real-World Use Cases of Component Counting

• Social networks: Find isolated friend groups
• Computer networks: Detect disconnected subnets
• Geography: Count separate landmasses (like islands)
• Image segmentation: Identify regions in a pixel matrix

Conclusion

Counting the number of connected components in an undirected graph is a core problem in graph theory with practical implications in many domains. Whether using graph traversal techniques like depth-first search and breadth-first search, or the highly efficient union-find data structure, mastering this problem gives you a deeper understanding of graph connectivity, disjoint sets, and efficient graph algorithms.