Компонента связности графа

---

Компонента связности графа ${\displaystyle G}$ (или просто компонента графа ${\displaystyle G}$) — максимальный (по включению) связный подграф графа ${\displaystyle G}$.^[1][2][3]

Другими словами, это подграф ${\displaystyle G(U)}$, порождённый множеством ${\displaystyle U\subseteq V(G)}$ вершин, в котором для любой пары вершин ${\displaystyle u,v\in U}$ в графе ${\displaystyle G}$ существует ${\displaystyle (u,v)}$-цепь и для любой пары вершин ${\displaystyle u\in U}$, ${\displaystyle w\notin U}$ не существует ${\displaystyle (u,w)}$-цепи.

Для выделения компонент связности можно использовать поиск в ширину или поиск в глубину. При этом затраченное время будет линейным от суммы числа вершин и числа рёбер графа.

---