connected component

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:

• Finding clusters of similar items, where similarily is represented by a weight associated with an undirected vertex. This is the basic problem of nearest neighbor algorithms.
• Determining whether a computer network has been disconnected. (See the dynamic equivalence problem.)
• Labeling parts of an image. An early process in computer vision is finding groups of pixels corresponding to surfaces.

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.

Equivalently: Define an equivalence relation x~y ("x and y are connected") on points in X: x~y iff there is no partition X=A∪B into disjoint open subsets A,B for which x∈A and y∈B. The connected components of X are the equivalence classes of ~ (aka "X/~").

A related notion is path connected component; however, due to the difference between connectedness and path connectedness, the two concepts are not equivalent for general topological spaces.