connected components
Imagine a map of islands joined by bridges. Some islands are linked into one landmass you can walk across without getting your feet wet; others are off on their own. A connected component of an undirected graph is one such reachable cluster: a maximal set of vertices where you can travel from any one to any other along edges. 'Maximal' means you cannot add another vertex and stay connected — each component is a complete, self-contained piece, and the whole graph is a disjoint pile of these pieces.
Finding them is the cleanest possible use of graph search. Mark every vertex unvisited; then for each vertex that is still unvisited, launch a fresh BFS or DFS from it, which floods outward and marks everything reachable, labelling them all with the same component number; increment the number and repeat until no unvisited vertex remains. The count of fresh launches is the number of connected components. Why is each flood exactly one component? Because a traversal from v reaches precisely the vertices connected to v (that is what reachability means in an undirected graph), and it stops exactly at the boundary where no edge crosses — so it captures a maximal connected set, no more and no less. Across the whole run each vertex is visited once and each edge inspected once, so the total cost is O(n + m).
Connected components answer 'how many separate pieces is this network in, and which vertices share a piece?' — used in clustering, image segmentation (pixels that touch and share a color), checking whether a network is fully connected, and as a preprocessing step before many algorithms. Two honest notes. First, this notion is for undirected graphs; directed graphs need the subtler idea of strongly connected components, because in a directed graph you might reach v from u but not u from v. Second, an incremental cousin, the union-find (disjoint-set) structure, maintains components as edges are added one at a time, which is what Kruskal's MST algorithm relies on — but for a static graph, a single linear traversal is the simplest correct tool.
Six vertices, edges {1-2, 2-3, 4-5}. Vertex 6 has no edges. BFS from 1 floods {1,2,3} (component 1). BFS from 4 floods {4,5} (component 2). BFS from 6 floods just {6} (component 3). Three launches, so three connected components.
Each fresh search launch covers exactly one component; the number of launches is the component count.
Connected components are an undirected idea. In a directed graph, mutual reachability is required, so you need strongly connected components instead — they are not the same and can differ wildly.