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

Материал из Algocode wiki
Версия от 16:28, 26 сентября 2019; Глеб (обсуждение | вклад) (Новая страница: «Путем в графе называется последовательность вершин $v_i \in 𝑉$, $i = 1...k$ таких, что две послед...»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Путем в графе называется последовательность вершин $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 }