Connected Components

A connected component is a maximal set of vertices in a graph such that every pair of vertices within the set is connected by a path. In simple terms, a connected component represents a self-contained subgraph where all nodes can reach each other.

Connected components are most commonly discussed in undirected graphs, though related concepts exist for directed graphs as well.

What Is a Connected Component?

In an undirected graph:

• Two vertices belong to the same connected component if there is at least one path between them
• A graph may contain one or many connected components

Example:

Component 1:     Component 2:

A --- B          D --- E
|                |
C                F

This graph has two connected components:

• {A, B, C}
• {D, E, F}

Why Connected Components Matter

Connected components help answer questions like:

• Is the graph fully connected?
• How many independent subgraphs exist?
• Can one node reach another?

They are used in:

• Network analysis
• Social graph clustering
• Image segmentation
• Detecting isolated systems or failures

How to Find Connected Components

The idea is straightforward:

1. Keep track of visited vertices

2. For each unvisited vertex:

   • Run a graph traversal (DFS or BFS)
   • Mark all reachable vertices as part of the same component

3. Repeat until all vertices are visited

Each traversal discovers one connected component.

Algorithm Steps (Using DFS)

1. Initialize an empty visited set

2. Initialize a component counter

3. Loop through all vertices:

   • If a vertex is unvisited:

     • Run DFS from that vertex
     • Increment the component count

Rust Implementation (Using DFS)

This implementation finds all connected components in an undirected graph represented as an adjacency list.

use std::collections::{HashMap, HashSet};

type Graph = HashMap<i32, Vec<i32>>;

pub fn connected_components(graph: &Graph) -> Vec<Vec<i32>> {
    let mut visited = HashSet::new();
    let mut components = Vec::new();

    for &node in graph.keys() {
        if !visited.contains(&node) {
            let mut component = Vec::new();
            dfs(graph, node, &mut visited, &mut component);
            components.push(component);
        }
    }

    components
}

fn dfs(
    graph: &Graph,
    node: i32,
    visited: &mut HashSet<i32>,
    component: &mut Vec<i32>,
) {
    visited.insert(node);
    component.push(node);

    if let Some(neighbors) = graph.get(&node) {
        for &neighbor in neighbors {
            if !visited.contains(&neighbor) {
                dfs(graph, neighbor, visited, component);
            }
        }
    }
}

Example Usage

fn main() {
    let mut graph: Graph = HashMap::new();

    graph.insert(1, vec![2]);
    graph.insert(2, vec![1, 3]);
    graph.insert(3, vec![2]);
    graph.insert(4, vec![5]);
    graph.insert(5, vec![4]);
    graph.insert(6, vec![]);

    let components = connected_components(&graph);

    for (i, component) in components.iter().enumerate() {
        println!("Component {}: {:?}", i + 1, component);
    }
}

Output (one possible ordering):

Component 1: [1, 2, 3]
Component 2: [4, 5]
Component 3: [6]

Time and Space Complexity

Time Complexity

Each vertex and edge is visited once.

Space Complexity

Notes on Directed Graphs

For directed graphs, connected components split into two related concepts:

• Weakly connected components - ignore edge direction
• Strongly connected components (SCCs) - every vertex reachable from every other vertex

SCCs require specialized algorithms such as Kosaraju’s or Tarjan’s, which can be covered later.

Playground Links

Rust - Connected Components