Изменения

== Алгоритм проверки наличия пути из S s в T t ==

Дан граф <tex>G </tex> и две вершины S <tex>s</tex> и T<tex>t</tex>. Необходимо проверить , существует ли путь из вершины S <tex>s</tex> в вершину T <tex>t</tex> по рёбрам графа <tex>G</tex>.

Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Смысл алгоритма заключается в том, чтобы запустить обход в глубину из вершины S <tex>s</tex> и проверять при каждом посещении вершины, не является ли она искомой вершиной T<tex>t</tex>.Так как в первый момент времени все пути в графе "белые", то если вершина T <tex>t</tex> и была достижима из S<tex>s</tex>, то по [[Лемма о белых путях|лемме о белых путях]] в какой-то момент времени мы зайдём в вершину T<tex>t</tex>, чтобы её покрасить. Время работы алгоритма <tex>O(M + N)</tex>.

Дан [[Основные определения теории графов|неориентированный граф]] <tex>G</tex>. Необходимо проверить , является ли он связным.

Заведём счётчик количества вершин которые мы ещё не посетили. В стандартной процедуре dfs() будем уменьшать счётчик на единицу при входе в процедуру. Запустимся от какой-то вершины нашего графа. Если в конце работы процедуры dfs() счётчик равен нулю, то мы побывали во всех вершинах графа, а следовательно он связен. Если счётчик отличен от нуля, то мы не побывали в какой-то вершине графа. Работает алгоритм за <tex>O(M + N)</tex>.