68
правок
Изменения
→Идея
Дан [[Основные определения теории графов|неориентированный граф]] G и две вершины U и V. Необходимо проверить существует ли путь из вершины U в вершину V по рёбрам графа G.
== Идея Алгоритм ==Небольшая модификация алгоритма [[Обход в глубину, цвета вершин|обхода в глубину]]. Смысл алгоритма заключается в том, чтобы запустить обход в глубину из вершины U и проверять при каждом посещении вершины, не является ли она искомойвершиной V.Так как в первый момент времени все пути в графе "белые", то если вершина V и была достижима из U, то по [[Лемме о белых путях|Лемма о белых путях]] в какой-то момент времени мы зайдём в вершину V, чтобы её покрасить.
== Алгоритм ==
