Faangprep Logo
Log inStart free
Browse curriculum

Connected Components

Connected components are the separate groups of vertices in an undirected graph, found and counted with BFS or DFS. They are useful for social network analysis and image segmentation.

NEW COMPONENT

Components found: 1

#1 {A}

Not yet reached

B
C
D
E
F

 

A has not been reached by any earlier search. It opens component #1.

Next

B is reachable from A, so it belongs to component #1 too.

Intuition

Imagine a group of islands. You can walk anywhere on a single island, but you can't walk to another island without swimming.

Each island is a Connected Component.

Graph traversal algorithms like BFS or DFS can explore one entire island before moving to the next.

Concept

  • Connected Component: A subgraph where every node is reachable from every other node in that subgraph.
  • Traversal: To find all components, we iterate through every node. If a node hasn't been visited, it belongs to a new component. We then traverse (BFS/DFS) to find all nodes in that component.

How it Works

Algorithm Steps:
  1. Initialize count = 0 and a visited set.
  2. Iterate through all nodes i from 0 to N-1.
  3. If node i is NOT visited:
    • Increment count.
    • Start a traversal (BFS or DFS) from node i.
    • Mark all reachable nodes as visited.
  4. Return count.

Step-by-Step Breakdown

Watch the visualization:

  • White Node: Currently being visited.
  • Colored Node: Assigned to a specific component. Different components have different colors.

When to Use

Use Connected Components when:

  • Counting distinct groups in a social network (e.g., groups of friends).
  • Image segmentation (grouping connected pixels).
  • Finding isolated systems or unreachable servers in a network.

When NOT to Use

  • Directed Graphs: For directed graphs, you typically look for Strongly Connected Components (SCC), which need their own algorithms (Tarjan's or Kosaraju's). Weakly Connected Components are simpler: ignore edge directions and run this same traversal.

How to Identify

Problems asking to "count groups", "count provinces", "number of islands", or "check path existence" often relate to connected components.

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Cycle Detection

Next

Bipartite Graph

Frequently Asked Questions

What are Connected Components?

A connected component is a maximal set of nodes where a path exists between every pair of nodes in the set.

How to count components?

Start a traversal (BFS/DFS) from an unvisited node, mark all reachable nodes, and increment the count. Repeat until all nodes are visited.

Strongly vs Weakly Connected?

Only applicable to directed graphs. "Strongly" means a bidirectional path exists between all pairs. "Weakly" means the underlying undirected graph is connected.