Connected Components

Connected components are separate groups of vertices where each vertex can reach the others in the same group.

In an undirected graph, connected components describe the graph’s disconnected pieces.

Core Idea

Start a traversal from an unvisited vertex. Everything reached belongs to one component. Then repeat from another unvisited vertex until every vertex has been assigned to a component.

BFS or DFS can find components.

Function Contracts

count_components(graph) expects an undirected graph represented as an adjacency list. It returns the number of connected groups.

components(graph) uses the same graph shape and returns the actual groups as lists of vertices. Both functions assume the outer visited set persists across component searches.

Python Example

def count_components(graph):
    visited = set()
    count = 0
 
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
 
    for node in graph:
        if node not in visited:
            count += 1
            dfs(node)
 
    return count

Each new DFS starts a new component.

Step-by-Step Idea

Imagine this undirected graph:

0 -- 1     3 -- 4
|
2

Starting DFS at 0 reaches 0, 1, and 2. Those vertices form one connected component. The next unvisited vertex is 3, and DFS from 3 reaches 3 and 4. That is the second component.

The outer loop is necessary because one traversal cannot reach vertices in other disconnected groups.

Returning the Groups

Sometimes the problem needs the actual groups, not only the count:

def components(graph):
    visited = set()
    groups = []
 
    def dfs(node, group):
        visited.add(node)
        group.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor, group)
 
    for node in graph:
        if node not in visited:
            group = []
            dfs(node, group)
            groups.append(group)
 
    return groups

Complexity

With an adjacency list, finding connected components is O(V + E) because each vertex and edge is processed a limited number of times.

Common Confusions

Connected components are straightforward in undirected graphs. Directed graphs need more precise terms, such as strongly connected components, because reachability has direction.

One traversal from one start vertex may not visit the whole graph if the graph is disconnected.

Another common mistake is resetting visited for each start vertex. For component counting, visited must persist across the outer loop.

When To Use It

Use connected components when the problem asks how many separate groups exist, whether all nodes are connected, or which nodes belong together.

If the graph is directed, first check whether the problem means weak connectivity, strong connectivity, or reachability from a specific start.

The Main Point

Connected components are found by starting a traversal from each still-unvisited vertex. The persistent visited set is what prevents counting the same group twice.