Parts of a graph that are linked together. Two vertices are in the same connected component if there is some path between them.

Many practical problems involve connected components:

For directed graphs, there are two definitions of connected components. A directed graph is *weakly connected* if it would be connected by ignoring the direction of edges, i.e., if all edges were replaced by undirected edges. A directed graph is *strongly connected* if there exists a (directed) path between every pair of vertices. Consider a city traffic network consisting of one-way and two-way streets. The network is strongly connected if it is possible to drive legally between every two intersections. The network is weakly connected if it is possible to drive, legally *or* illegally, between every two intersections. The network is disconnected if it's impossible to drive between some point and some other point.