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