42
правки
Изменения
Нет описания правки
{{Задача
|definition = Дан граф, требуется проверить наличие [[Основные определения теории графов|цикла]] в этом графе. Будем решать задачу с помощью [[Обход в глубину, цвета вершин|поиска в глубину]] за <tex>O(|V| + |E|)</tex>.
}}
== Алгоритм ==
В случае <b>неориентированного ориентированного графа</b>произведём серию обходов. То есть из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, используя указанный алгоритмкоторый при входе в вершину будет красить её в серый цвет, мы перейдем по какомуа при выходе из нее {{---либо ребру }} в обратном направлении и попадем чёрный. И, если алгоритм пытается пойти в серую вершину, то это означает, что будет означать наличие циклацикл найден. Проблема В случае <b>неориентированного графа</b>, одно ребро не должно встречаться в том, что по определению [[Основные определения теории графов#def_no_graph_path|циклацикле]] дважды по определению. Поэтому необходимо дополнительно проверять, что текущее рассматриваемое из вершины ребро не то, по которому мы пришли в эту вершину. Заметим, что, если в неориентированном графеесть вершины с петлями, одно и то алгоритм будет работать корректно, так как при запуске поиска в глубину из такой вершины, найдется ребро, ведущее в нее же ребро не может содержаться , а значит эта петля и будет являться циклом. Для восстановления самого цикла достаточно при запуске поиска в глубину из очередной вершины добавлять эту вершину в [[Стек|стек]]. Когда поиск в глубину нашел вершину, которая лежит на цикле дважды. Чтобы избежать этого, необходимо передавать будем последовательно вынимать вершины из стека, пока не встретим найденную еще один параметр раз. Все вынутые вершины будут лежать на искомом цикле. Асимптотика поиска цикла совпадает с асимптотикой поиска в глубину {{---}} вершину, из которой мы пришли. Теперь можно считать, что цикл найден, если вершина, в которую мы хотим пойти серая и не является вершиной, из которой мы пришли<tex>O(|V| + |E|)</tex>.
[[Файл: Dfs_cycle.png|thumb|200px|right| Момент нахождения цикла: <font color=blue>синие</font> ребра {{---}} уже пройденные, <font color=red>красное</font> ребро ведет в серую, уже пройденную, вершину.]]
Докажем, что если в графе <tex>G</tex> существует цикл, то <tex>\mathrm{dfs}(G)</tex> его всегда найдет. Пусть <tex> v </tex> {{---}} первая вершина принадлежащая циклу, рассмотренная поиском в глубину. Тогда существует вершина <tex> u </tex>, принадлежащая циклу и имеющая ребро в вершину <tex> v </tex>. Так как из вершины <tex> v </tex> в вершину <tex> u </tex> существует белый путь (они лежат на одном цикле), то по [[Лемма о белых путях|лемме о белых путях]] во время выполнения процедуры поиска в глубину от вершины <tex> u </tex>, вершина <tex> v </tex> будет серой. Так как из <tex> u </tex> есть ребро в <tex> v </tex>, то это ребро в серую вершину. Следовательно <tex>\mathrm{dfs}(G)</tex> нашел цикл.
== Реализация для случая ориентированного графа ==
