68
правок
Изменения
Нет описания правки
== Алгоритм ==
Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Смысл алгоритма заключается в том, чтобы запустить обход в глубину из вершины U и проверять при каждом посещении вершины, не является ли она искомой вершиной V.
Так как в первый момент времени все пути в графе "белые", то если вершина V и была достижима из U, то по [[Лемме о белых путях|Лемма о белых путях]] в какой-то момент времени мы зайдём в вершину V, чтобы её покрасить. == Алгоритм ==Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу перед выходом из процедуры. Запустимся от какой-то вершины нашего графа. По окончании Время работы процедуры dfs() сравним счётчик с нулём. Если они равны, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то в графе несколько компонент связности. Работает алгоритм за алгоритма O(M + N).
=== Реализация ===
return 0;
}
== Алгоритм проверки связности ВСЕГО графа G ==
Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу перед выходом из процедуры. Запустимся от какой-то вершины нашего графа. По окончании работы процедуры dfs() сравним счётчик с нулём. Если они равны, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то мы не побывали в какой-то вершине графа. Работает алгоритм за O(M + N).
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]
