connected component

A group of vertices that can all reach one another, with no path to any vertex outside the group.

In more detail

Running DFS or BFS from an unvisited vertex marks exactly its component, so repeating from each unvisited vertex finds them all. Union-find tracks components as edges are added, which Kruskal's algorithm relies on.

Related terms

Taught in

References