Компонента связности
Компонента связности — это максимальная группа вершин неориентированного графа, в которой из каждой вершины можно попасть в любую другую по рёбрам. Один граф может состоять из нескольких таких независимых частей.
Чтобы найти компоненты, используют поиск в ширину или поиск в глубину. Все вершины сначала считают непосещёнными. Затем перебирают вершины по порядку: если очередная вершина ещё не посещена, начинают из неё обход, помечают найденные вершины и увеличивают счётчик компонент на один. Обход посетит ровно все вершины одной компоненты.
Пусть в графе есть рёбра \(1-2\), \(2-3\) и \(4-5\), а вершина \(6\) изолирована. Первый запуск обхода найдёт вершины \(1,2,3\), второй — \(4,5\), третий — только \(6\). Поэтому число компонент связности равно \(k=3\).
Компонента связности и связный граф — не одно и то же. Связный граф имеет ровно одну компоненту связности. Если компонент несколько, весь граф несвязный, но каждая отдельная компонента является связным подграфом.
В графе 7 вершин. Обход из вершины 1 посетил вершины 1, 2 и 4, а остальные вершины пока не посещены. Что нужно сделать дальше?
Если граф задан списками смежности, обход всей сети работает за время \(O(V+E)\), где \(V\) — число вершин, а \(E\) — число рёбер. Изолированная вершина тоже образует компоненту связности, состоящую из одной вершины.
Главное
- Компонента связности — максимальная связная часть неориентированного графа.
- Число компонент равно числу запусков обхода из непосещённых вершин.
- Изолированная вершина считается отдельной компонентой.