Connected Components in Graphs

A connected component is a group of vertices in a graph where every vertex can be reached from every other vertex in that group through one or more edges. A graph can contain one connected component or several separate components.

Finding connected components is a fundamental graph problem. It is commonly solved using Depth-First Search (DFS) or Breadth-First Search (BFS). The general idea is to start a traversal from every vertex that has not been visited yet. Each traversal discovers one complete component.

What Is a Connected Component?

Consider an undirected graph containing several groups of connected vertices:

0 --- 1       3 --- 4       6

|             |
2             5

The graph contains three separate groups:

• Component 1: vertices 0, 1, and 2
• Component 2: vertices 3, 4, and 5
• Component 3: vertex 6

Therefore, this graph has 3 connected components. Vertex 6 is considered a component by itself because it has no connection to another vertex.

Connected Component in an Undirected Graph

Connected components are most commonly introduced using undirected graphs. In an undirected graph, an edge between two vertices can be traversed in either direction.

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

Starting from vertex 0 allows us to reach vertices 1 and 2. Starting from vertex 3 reaches vertices 4 and 5. Vertex 6 cannot reach any other vertex, so it forms its own component.

How Connected Components Are Found

The standard approach uses a visited collection to keep track of vertices that have already been explored.

1. Initialize every vertex as unvisited.
2. Start from the first unvisited vertex.
3. Run DFS or BFS from that vertex.
4. Mark every reachable vertex as visited.
5. Count that traversal as one connected component.
6. Continue until every vertex has been visited.

The important observation is that one complete traversal from an unvisited vertex discovers exactly one connected component in an undirected graph.

Finding Connected Components Using DFS

Depth-First Search explores as far as possible along one path before backtracking. For connected components, DFS can mark every vertex belonging to the current component.

function dfs(node, graph, visited) {
  visited.add(node);

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

function countComponents(graph) {
  const visited = new Set();
  let count = 0;

  for (const node of Object.keys(graph)) {
    const vertex = Number(node);

    if (!visited.has(vertex)) {
      dfs(vertex, graph, visited);
      count++;
    }
  }

  return count;
}

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

console.log(countComponents(graph)); // 3

Every time the outer loop encounters an unvisited vertex, DFS explores its entire component. The counter is then increased by one.

DFS Step by Step

Using the previous graph, the algorithm starts at vertex 0.

• Start at 0 and mark it visited.
• Visit 1 through the edge from 0.
• Visit 2 through the edge from 1.
• No new vertices can be reached from 2.
• The first DFS finishes, so component count becomes 1.
• The next unvisited vertex is 3.
• DFS visits 3, 4, and 5.
• Component count becomes 2.
• Vertex 6 is still unvisited.
• DFS from 6 visits only 6, producing the third component.

Finding Connected Components Using BFS

Breadth-First Search can solve the same problem. Instead of recursively exploring one path, BFS uses a queue and visits vertices level by level.

function bfs(start, graph, visited) {
  const queue = [start];
  visited.add(start);

  let index = 0;

  while (index < queue.length) {
    const node = queue[index++];

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

function countComponents(graph) {
  const visited = new Set();
  let count = 0;

  for (const node of Object.keys(graph)) {
    const vertex = Number(node);

    if (!visited.has(vertex)) {
      bfs(vertex, graph, visited);
      count++;
    }
  }

  return count;
}

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

console.log(countComponents(graph)); // 3

DFS and BFS both visit every vertex and edge required to identify the components. The choice between them often depends on the surrounding problem and implementation requirements.

Counting Components vs Listing Components

The same traversal can do more than simply count components. Instead of incrementing a counter, we can collect the vertices discovered during each traversal.

function findComponents(graph) {
  const visited = new Set();
  const components = [];

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

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

  for (const node of Object.keys(graph)) {
    const vertex = Number(node);

    if (!visited.has(vertex)) {
      const component = [];
      dfs(vertex, component);
      components.push(component);
    }
  }

  return components;
}

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

console.log(findComponents(graph));

The result represents the individual groups rather than only the total number of components.

Connected Components with an Adjacency List

An adjacency list is a common graph representation for connected-component problems. Each vertex stores the vertices directly connected to it.

const graph = {
  A: ["B"],
  B: ["A", "C"],
  C: ["B"],
  D: ["E"],
  E: ["D"]
};

Here, the graph contains two connected components: A-B-C and D-E.

Visited Array and Visited Set

When vertices are numbered from 0 to n - 1, a Boolean array is often convenient for tracking visited vertices.

const visited = new Array(6).fill(false);

visited[0] = true;
visited[1] = true;

console.log(visited);

A Set is useful when vertices may have arbitrary identifiers, such as strings.

const visited = new Set();

visited.add("A");
visited.add("B");

console.log(visited.has("A"));

Time Complexity

Using an adjacency-list representation, a DFS or BFS connected-components algorithm typically visits each vertex and examines each edge a bounded number of times.

For a graph with V vertices and E edges, the time complexity is:

Time Complexity: O(V + E)

The additional space used for the visited collection and traversal structure is generally O(V), excluding the graph representation itself.

Connected Components with an Adjacency Matrix

An adjacency matrix represents connections using a two-dimensional matrix. For each vertex, the algorithm may need to inspect an entire row to discover its neighbors.

const graph = [
  [0, 1, 0],
  [1, 0, 1],
  [0, 1, 0]
];

With an adjacency matrix, scanning all possible neighbors for every vertex can result in O(V²) traversal work. Therefore, adjacency lists are often more efficient for sparse graphs.

Connected Components in a Grid

Connected-component ideas also appear in two-dimensional grids. A group of adjacent cells can be treated as one component.

For example, consider 1 as land and 0 as empty space:

1 1 0 0
1 0 0 1
0 0 1 1

A DFS or BFS can be started from every unvisited land cell. Each traversal marks one connected region. This pattern is commonly used in grid and island-counting problems.

Connected Components vs Reachability

These concepts are related but should not be confused.

• Reachability: asks whether one vertex can reach another.
• Connected components: identify all groups of mutually reachable vertices in an undirected graph.
• Graph traversal: provides the mechanism used to explore vertices and determine these relationships.

Connected Components vs Strongly Connected Components

In directed graphs, the term strongly connected component (SCC) describes a related but different concept.

A strongly connected component is a maximal group of vertices where every vertex is reachable from every other vertex following the direction of the edges. Algorithms such as Kosaraju's and Tarjan's algorithm are commonly used to find SCCs.

Practical Applications

Connected-component detection is useful whenever a system needs to identify separate groups within connected data.

• Finding groups of connected users or devices.
• Identifying isolated networks.
• Analyzing connected regions in images.
• Counting islands or regions in a grid.
• Grouping related records based on relationships.
• Analyzing dependency or connectivity networks.
• Determining whether all nodes in a network belong to one connected group.

Checking Whether a Graph Is Connected

A graph is connected if every vertex belongs to the same connected component. Therefore, we can check connectivity by counting the components.

function isConnected(graph) {
  const visited = new Set();

  function dfs(node) {
    visited.add(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        dfs(neighbor);
      }
    }
  }

  const nodes = Object.keys(graph);

  if (nodes.length === 0) {
    return true;
  }

  dfs(nodes[0]);

  return visited.size === nodes.length;
}

const graph = {
  A: ["B"],
  B: ["A", "C"],
  C: ["B"]
};

console.log(isConnected(graph)); // true

If the traversal starting from one vertex visits every vertex, the undirected graph has exactly one connected component and is therefore connected.

Common Mistakes

• Running DFS or BFS only once and assuming the entire graph has been explored.
• Forgetting to track visited vertices.
• Counting every visited vertex as a separate component.
• Confusing connected components with strongly connected components.
• Forgetting that an isolated vertex forms a component of its own.
• Using a directed-graph definition when solving an undirected connected-components problem.
• Ignoring the graph representation when analyzing complexity.

Interview Pattern to Remember

Many connected-component problems can be recognized from a simple pattern:

for each vertex:
    if vertex is not visited:
        traverse from vertex
        componentCount++

The traversal can be DFS or BFS. The outer loop is what allows the algorithm to discover components that are disconnected from previously explored vertices.

Key Takeaways

• A connected component is a maximal group of connected vertices in an undirected graph.
• A graph can contain one or many connected components.
• DFS and BFS can both be used to find connected components.
• A visited set or array prevents repeated traversal of the same vertex.
• Every traversal started from an unvisited vertex identifies one component.
• An isolated vertex is a connected component containing one vertex.
• With an adjacency list, DFS/BFS component detection typically runs in O(V + E).
• The same idea can be applied to grid problems such as counting connected regions.
• Connected components in undirected graphs are different from strongly connected components in directed graphs.