Поиск компонент связности

Путем в графе называется последовательность вершин $v_i \in 𝑉$, $i = 1...k$ таких, что две последовательные вершины в пути соединены ребром, $k$ - длина пути. Граф называется связным, если для любых двух его вершин существует путь между ними. Граф всегда можно разбить на непересекающиеся связные подмножества (возможно одно), между которыми рёбер нет, они называются компонентами связности.

Поиск в глубину dfs будет обходить ту компоненту связности, из вершины которой, он был вызван. Поэтому для поиска компонент связности можно каждый раз вызываться из любой непосещенной вершины и тогда в результате мы посетим все вершины, а следовательно и найдем все компоненты связности.

Граф с тремя компонентами связности :

http://lib.vvsu.ru/books/Bakalavr01/obj.files/image726.gif

1 for (int i = 0; i < n; ++i){
2     if (!used[i]) {
3         amount++;
4         dfs(i);
5     }
6 }

---

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin