Finding connected components

Finding connected components

Introduction

Depth First Search, or DFS, is one of the most basic graph traversal algorithms. It starts from one vertex, goes to an unvisited neighbor, then continues deeper and deeper until it cannot move anymore. After that, it returns back and tries other unused edges.

In this lecture, we will use DFS to find connected components in an undirected graph. A connected component is a group of vertices where every vertex can reach every other vertex inside the same group. This idea appears in many graph problems: counting separate groups, checking if a graph is connected, processing each independent part of a graph, and reducing a graph problem into smaller pieces.

Problem or motivation

We are given an undirected graph with $n$ vertices and $m$ edges. We need to find all connected components.

More concretely, we want to know:

• how many connected components the graph has;
• which component each vertex belongs to.

For example, suppose the graph has vertices $1, 2, 3, 4, 5, 6$ and edges , , . Then the connected components are: