Изменения

Пусть дан [[ориентированный граф{{Задача|ориентированный definition = Дан граф]] без петель и кратных рёбер. Требуется , требуется проверить наличие [[Основные определения теории графов|цикла]] в этом графе.}}

Решим эту == Алгоритм == Будем решать задачу с помощью [[Обход в глубину, цвета вершин|поиска в глубину]] за . В случае <b>ориентированного графа</b> произведём серию обходов. То есть из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе из нее {{---}} в чёрный. И, если алгоритм пытается пойти в серую вершину, то это означает, что цикл найден. В случае <texb>O(M)неориентированного графа</texb>, одно ребро не должно встречаться в [[Основные определения теории графов#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> v </tex> достижима, так как между соседними вершинами в стеке есть ребро. Тогда , если из рассматриваемой вершины <tex> v </tex> существует ребро в серую вершину <tex> u </tex>, то это значит, что из вершины <tex> u </tex> существует путь в <tex> v </tex> и из вершины <tex> v </tex> существует путь в <tex> u </tex> состоящий из одного ребра. И так как оба эти пути не пересекаются, то цикл существует. Докажем, что если в графе <tex>G</tex> существует цикл, то <tex>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>dfs(G)</tex> нашел цикл.

== Реализация для случая ориентированного графа == <font color=darkgreen>// color {{---}} массив цветов, изначально все вершины белые </font> '''intfunc''' dfs(v: ''' graphvertex'''): <font color=darkgreen> // v {{---}} вершина, в которой мы сейчас находимся </font> color[v]= <i>grey</i> '''for''' (u: vu <tex>\in</tex> E) '''if''' (color[u];== <i>white</i>) dfs(u) '''intif''' (color[u] == <texi>grey</i>) print() <font color=darkgreen> // вывод ответа </font> color[v] = <i> \leftarrow black</texi> white;

'''func''' dfs(u: '''int'''): == См. также == color* [u[Использование обхода в глубину для проверки связности]] = grey; <font color=darkgreen> // красит вершину u * [[Использование обхода в серый цвет </font>глубину для топологической сортировки]] '''for''' (v : uv {{---}} edge) if (color* [[vИспользование обхода в глубину для поиска компонент сильной связности]] == white) dfs(v); if (color* [[vИспользование обхода в глубину для поиска точек сочленения]] == grey) print(); <font color=darkgreen> // вывод ответа </font> color* [[uИспользование обхода в глубину для поиска мостов]] = black; <font color=darkgreen> // красит вершину u в черный цвет </font>