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.

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.

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.

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.