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

Несвязный граф с тремя компонентами связности

Компонента связности графа $G$ $G$ (или просто компонента графа $G$ $G$ ) — максимальный (по включению) связный подграф графа $G$ $G$ .

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

Для ориентированных графов определено понятие компоненты сильной связности .

Алгоритм

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