CoreSource checked

Connected Components

Groups graph nodes by which nodes can reach each other.

Explore relationships Open constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category: Graph Traversal
Difficulty: Beginner
Family: Connectivity
Tier: Core
Status: Verified
Review: Source Checked
Sources: 2
Formulas: 0
Relationships: 4
Code example: Ready
Visualization: Ready

Overview

Connected Components runs traversal from unvisited nodes to label each reachable group in an undirected graph.

Core Concepts

graph representationconnected componenttraversal orderconnectivityvisited setfrontier expansion

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(V + E)

Average

O(V + E)

Worst

O(V + E)

Space

O(V)

When to Use

Use Connected Components when you need to find reachable node groups.
Use it for network cluster detection with inputs like undirected graph.
Use it when relationships are naturally modeled as nodes connected by edges.
Use it when the Connectivity tradeoff is acceptable for the problem size.

When Not to Use

Avoid it when the graph is so large that storing every visited node is not practical.
Avoid it when the required output is not component labels.

What It Does

Finds reachable node groups
Labels each node with a component

Use Cases

Network cluster detection
Image component labeling
Graph preprocessing

Inputs

Undirected graph

Outputs

Component labels
Component groups

Pseudocode

1.Mark every node unvisited
2.Start BFS or DFS from an unvisited node
3.Label every reached node with the same component
4.Repeat from the next unvisited node
5.Return all component groups

Canonical Example

Input: graph = {A: [B, C], B: [D], C: [], D: []}, start = A
Output: visited = [A, B, C, D]
Explanation: Connected Components: The traversal starts at A and visits reachable nodes by following edges.

Implementation Notes

Keep the input contract explicit: Undirected graph.
Use this step as the implementation spine: Mark every node unvisited.
Then preserve the next state change: Start BFS or DFS from an unvisited node.
Keep node ids, edge direction, and visited state explicit in the implementation.
Represent neighbors consistently and keep traversal state separate from the graph data.

Common Pitfalls

For dynamic connectivity, Union-Find is often a better fit.
Not defining directed versus undirected edges clearly can change the result.
Forgetting to mark visited nodes before revisiting cycles or shared neighbors.
Returning component labels without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Graph Frontier & Edge Relaxation

Show each connected group receiving a different color.

Step 1 of 5: Mark every node unvisited

component-coloring

Notes

Connected Components operates in O(V + E) time and O(V) space within the Connectivity family. Often compared with Breadth-First Search and Union-Find.