22.2.1. Identifying Connected Components

One fundamental property of undirected graph is whether or not disconnected, can we go from every vertex to every other vertex. So, you can see in these two pictures that the graph on the left is connected, because you can go from every vertex to every other vertex. On the other hand, on the right hand side some vertices cannot be reached from other vertices. For example, one cannot go from 2 to 7 or from 6 to anywhere else.

A graph is defined as a collection of vertices (nodes) connected by edges (lines). We assess whether a graph is connected by determining if there is a path between every pair of vertices. A connected graph allows movement from any one vertex to another, while a disconnected graph has isolated segments preventing such movement. In the example mentioned, the graph on the left is a single connected entity, while the right graph includes isolated vertices which cannot communicate with each other.

Imagine a set of friends where everyone knows each other — this is like a connected graph. If some friends don't know each other at all, and form separate mini-groups, this represents a disconnected graph.

Now, when we have an undirected graph which is disconnected, we are also interested in finding out what the connected components are. So, we want to group together those vertices which are connected to each other into one unit and find out which of these units are there and how many such units are there, in which vertices belong to the same unit.

When dealing with a disconnected graph, it's important to identify its connected components. A connected component refers to a subset of vertices where any two vertices in the subset are connected to each other, and which is connected to no additional vertices in the larger graph. The process of categorizing these components can reveal critical insights about the graph's structure.

Think of it like a large neighborhood where some houses are connected by a network of roads, and others are entirely cut off. Each neighborhood forms a connected component, while the isolated clusters represent different disconnected components.

So, our target is to use BFS or DFS to identify connected components. We start with the node labeled 1 or any other node. Now, we run BFS or DFS from this node and in this process we will mark a number of nodes as visited. If there are any vertices which are not visited by BFS or DFS starting from the first node, this means that they do not belong to the same connected component.

To find the connected components, we can apply graph traversal techniques like Breadth-First Search (BFS) or Depth-First Search (DFS). We begin at an arbitrary node and mark all reachable nodes as visited. If there are still unvisited nodes after completing the first traversal, we initiate a new BFS or DFS from the next unvisited node to identify another connected component. This process continues until all nodes are explored.

Imagine exploring a city, where you start at your friend's house (node 1) and visit all connected houses (nodes) in their block using either BFS or DFS. When you can no longer visit any new houses and return home, you realize there are other blocks in the city you haven't explored yet (unvisited nodes). You start the exploration again from a house in another block.

We can label each DFS with different numbers, at the end we can associate with each vertex, the number of the component in which it was discovered.

Labeling connected components provides a structure to the graph analysis. After performing multiple BFS or DFS traversals, we assign a unique identifier to each connected component, thereby making it easier to reference and analyze different parts of the graph. Each vertex will retain its component label, helping in understanding graph connectivity at a glance.

Consider labeling different zones in a city: if each neighborhood is given a unique color (label), it becomes visually easier to discern which neighborhood belongs where, allowing for better city planning and management.

So, let us look at an example. Suppose we have this graph, we begin by having an extra variable in our BFS for example, or even DFS called 'compt' to number the components. We start our DFS or BFS from node 1. In this process, we will visit nodes 1, 2, 5, 9, and 10 and assign them to component 1. We then realize that all nodes have been visited — only 5 out of the 12 nodes have been visited. We go to the smallest node which is not visited, namely 3, and restart, updating the count to 2. Performing BFS or DFS from node 3 identifies another component.

To solidify our understanding, let's consider a specific example. Starting with an empty graph, we immediately label component 1 after visiting nodes 1 through 10. After completing this search, we note that several nodes remain unvisited. We initiate a new search from the smallest unvisited node (3) and, upon visiting all reachable nodes, assign them to component 2. This repetitive process allows us to classify and label all components in the graph.

Imagine you are inspecting a collection of art pieces in a large gallery, where works from the same artist (connected components) are grouped together. After surveying the first section, you determine that you missed some art in another wing (unvisited nodes), so you go back to explore those sections one by one.

--