A Connected Component is a maximal group of vertices in an undirected graph where every pair of vertices is connected by some path.

If the entire graph has one component, it is connected. If it has more than one, it is disconnected.

Example

A -- B -- C

D -- E

F

contains three connected components:

[A, B, C]
[D, E]
[F]

Core idea

For every unvisited vertex:

1. run DFS or BFS,
2. collect every reachable vertex,
3. that traversal forms one connected component,
4. repeat from the next unvisited vertex.

DFS implementation

function connectedComponentsDFS(graph) {
  const visited = new Set();
  const result = [];

  function dfs(node, component) {
    visited.add(node);
    component.push(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        dfs(next, component);
      }
    }
  }

  for (const node of Object.keys(graph)) {
    if (visited.has(node)) continue;

    const component = [];
    dfs(node, component);
    result.push(component);
  }

  return result;
}

BFS implementation

function connectedComponentsBFS(graph) {
  const visited = new Set();
  const result = [];

  for (const start of Object.keys(graph)) {
    if (visited.has(start)) continue;

    const queue = [start];
    let head = 0;
    const component = [];

    visited.add(start);

    while (head < queue.length) {
      const node = queue[head++];
      component.push(node);

      for (const next of graph[node] ?? []) {
        if (visited.has(next)) continue;

        visited.add(next);
        queue.push(next);
      }
    }

    result.push(component);
  }

  return result;
}

Component IDs

For repeated connectivity queries, assigning every vertex a component ID is useful.

Then:

a and b connected?
componentId[a] === componentId[b]

can be answered in constant time after preprocessing.

Connected vs strongly connected components

Connected Components are primarily an undirected-graph concept.

For directed graphs:

• Weakly Connected Components ignore edge direction.
• Strongly Connected Components require mutual reachability.

Undirected → Connected Components
Directed + ignore direction → Weak Components
Directed + mutual reachability → SCC

Union-Find / DSU

When edges arrive dynamically, Disjoint Set Union is often preferable.

Initially every vertex is its own component.

Every successful union merges two components and reduces the component count by one.

class DSU {
  constructor(nodes) {
    this.parent = new Map();
    this.rank = new Map();

    for (const node of nodes) {
      this.parent.set(node, node);
      this.rank.set(node, 0);
    }
  }

  find(x) {
    if (this.parent.get(x) !== x) {
      this.parent.set(
        x,
        this.find(this.parent.get(x))
      );
    }

    return this.parent.get(x);
  }

  union(a, b) {
    let rootA = this.find(a);
    let rootB = this.find(b);

    if (rootA === rootB) return false;

    const rankA = this.rank.get(rootA);
    const rankB = this.rank.get(rootB);

    if (rankA < rankB) {
      [rootA, rootB] = [rootB, rootA];
    }

    this.parent.set(rootB, rootA);

    if (rankA === rankB) {
      this.rank.set(rootA, rankA + 1);
    }

    return true;
  }
}

Counting components with DSU

function countComponentsDSU(nodes, edges) {
  const dsu = new DSU(nodes);
  let count = nodes.length;

  for (const [u, v] of edges) {
    if (dsu.union(u, v)) {
      count--;
    }
  }

  return count;
}

Number of Islands

A grid can be interpreted as a graph.

Each land cell is a vertex and neighboring land cells are connected.

Every connected region is an island.

This is one of the most common connected-component problems.

Four-direction vs eight-direction connectivity

Grid connectivity must be defined explicitly.

Four-direction connectivity uses:

up, down, left, right

Eight-direction connectivity also includes diagonals.

The number of components can change depending on this definition.

Real-world applications

Social networks

Users are vertices and relationships are edges.

Completely separate groups form different components.

Computer networks

Devices are vertices and links are edges.

Network partitions produce multiple connected components.

Wireless networks

Devices within communication range can be connected. Components identify groups that can communicate indirectly.

Image processing

Connected Component Labeling groups adjacent pixels into separate regions or objects.

Road networks

Road closures can divide a previously connected road graph into independent regions.

Connected components vs community detection

Connected components answer:

Is there any path between two vertices?

Community detection asks a different question:

Which groups have denser internal relationships?

A single connected component can contain many communities.

Largest component

Many systems care about the size of the largest connected region or the giant connected component.

This is common in network science and resilience analysis.

Complexity

With adjacency lists:

Time:  O(V + E)
Space: O(V)

With adjacency matrices, neighbor scanning may require:

O(V²)

time.

Union-Find with path compression and union by rank is nearly linear:

O(E α(V))

Common mistakes

• running DFS/BFS only once,
• forgetting isolated vertices,
• using ordinary connected components on directed graphs without defining the intended connectivity,
• confusing components with communities,
• mutating grid input unintentionally,
• recursion stack overflow on very deep graphs.

TypeScript

type Graph = Record<string, string[]>;

function connectedComponents(
  graph: Graph
): string[][] {
  const visited = new Set<string>();
  const result: string[][] = [];

  function dfs(
    node: string,
    component: string[]
  ): void {
    visited.add(node);
    component.push(node);

    for (const next of graph[node] ?? []) {
      if (!visited.has(next)) {
        dfs(next, component);
      }
    }
  }

  for (const node of Object.keys(graph)) {
    if (visited.has(node)) continue;

    const component: string[] = [];
    dfs(node, component);
    result.push(component);
  }

  return result;
}

When should you use connected components?

Use this pattern when:

• the graph is undirected,
• independent regions must be found,
• network partitions matter,
• island or region counting is required,
• repeated connectivity analysis is needed.

Summary

The standard pattern is:

for each unvisited vertex:
    run DFS/BFS
    one traversal = one component

This runs in O(V + E) with adjacency lists.

For dynamic edge additions and repeated connectivity queries, Union-Find is often the better abstraction.

The most important modeling decision is choosing the correct type of connectivity: ordinary, weak, or strong.