Understanding the connected component pattern
A connected component in a graph is a subgraph where there is a path between every pair of nodes. Connected components are usually used in the context of undirected graphs only. Directed graphs have more complex connectivity due to unidirectional edges, and such subgraphs where there is a path between every pair of nodes are called strongly connected components. We will only learn about connected components in undirected graphs in this lesson. Some graph problems require us to find and process all the connected components and the nodes in them in an undirected graph. We can solve such problems efficiently using the connected component technique.
An undirected graph with three connected components.
The connected component technique
To understand the technique to find and process all connected components, let's look at the generic problem it tries to solve. Consider that we are given a graph and we need to aggregate the value of a function f over all the nodes of all the connected components. We need to further aggregate the aggregated value of each connected component over a function g. Consider the following graph as an example.
Liking the course? Check our discounted plans to continue learning.