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
- depth-first search — A graph search that follows one path as deep as it can go, then backs up to the last choice point and tries the next branch.
- union-find — A data structure that tracks which items belong to the same group, supporting "find the group of x" and "merge the groups of x and y".
Taught in
- Breadth-First Search And Shortest Paths By Hops — Algorithms & Data Structures for Working Engineers
- Depth-First Search, Cycles And Topological Order — Algorithms & Data Structures for Working Engineers
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers