Изменения

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

Пусть дан В случае <b>ориентированный графориентированного графа</b>. Произведём произведём серию поисков в глубину в графе. Т.еобходов. То есть из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе из нее {{---}} в чёрный. И , если поиск в глубину алгоритм пытается пойти в серую вершину, то это означает, что мы нашли циклнайден.

В случае <b>неориентированного графа</b> любое , одно ребро представляется как два ребра {{---}} прямое и обратноене должно встречаться в [[Основные определения теории графов#def_no_graph_path|цикле]] дважды по определению. Тогда мы посчитаемПоэтому необходимо дополнительно проверять, что эти два ребра составляют цикл, что неверно. Чтобы избежать этого, будем передавать еще один параметр поиска в глубину {{---}} вершину, текущее рассматриваемое из которой мы пришли. Теперь мы считаем, что нашли цикл, если вершина, в которую мы хотим пойти серая и вершины ребро не является вершиной из которой тем ребром, по которому мы пришлив эту вершину.

Для восстановления самого цикла достаточно Заметим, что, если в графе есть вершины с петлями, то алгоритм будет работать корректно, так как при запуске поиска в глубину из очередной такой вершины добавлять эту вершину в стек. Когда поиск в глубину нашел вершину, которая лежит на цикленайдется ребро, будем последовательно вынимать вершины из стека, пока не встретим найденную еще раз. Все вынутые вершины будут лежать на искомом цикле.[[Файл: Dfs_cycle.png|thumb|200px|right| Момент нахождения цикла: синие ребра {{---}} уже пройденные, красное ребро ведет ведущее в серую, уже пройденнуюнее же, вершинуа значит эта петля и будет являться циклом.]]

Пусть дан граф <tex>G</tex>. Запустим <tex>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 O(|V| + |E|)</tex> состоящий из одного ребра. И так как оба эти пути не пересекаются, то цикл существует.

Докажем, что если в графе <tex>G</tex> существует цикл, то <tex>dfs(G)</tex> его всегда найдет[[Файл: Dfs_cycle. Пусть png|thumb|200px|right| Момент нахождения цикла: <texfont color=blue> v синие</texfont> ребра {{---}} первая вершина принадлежащая циклууже пройденные, рассмотренная поиском в глубину. Тогда существует вершина <texfont color=red> u красное</texfont>, принадлежащая циклу и имеющая ребро ведет в серую, уже пройденную, вершину <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> нашел цикл.

== Реализация для случая ориентированного графа Доказательство ==

'''int''' graph[][]; '''int''' color[] Пусть дан граф <tex>G</tex>. Запустим <tex> \leftarrow mathrm{dfs}(G)</tex> white; . Рассмотрим выполнение процедуры поиска в глубину от некоторой вершины <font color=darkgreentex> v </tex>. Так как все серые вершины лежат в стеке рекурсии, то для них вершина <tex> v </ Массив цветовtex> достижима, изначально все так как между соседними вершинами в стеке есть ребро. Тогда, если из рассматриваемой вершины <tex> v </tex> существует ребро в серую вершину <tex> u </tex>, то это значит, что из вершины <tex> u </tex> существует путь в <tex> v </tex> и из вершины белые <tex> v </tex> существует путь в <tex> u </fonttex>состоящий из одного ребра. И так как оба эти пути не пересекаются, то цикл существует.

'''func''' Докажем, что если в графе <tex>G</tex> существует цикл, то <tex>\mathrm{dfs}(u: '''int'''G): <font color=darkgreen/tex> его всегда найдет. Пусть <tex> v <// u tex> {{---}} первая вершинапринадлежащая циклу, рассмотренная поиском в которой мы сейчас находимся глубину. Тогда существует вершина <tex> u </fonttex>, принадлежащая циклу и имеющая ребро в вершину <tex> v </tex>. Так как из вершины <tex> v </tex> в вершину <tex> color[u] = grey; '''for''' </tex> существует белый путь (v : uv {{---}} edgeони лежат на одном цикле) if (color, то по [[vЛемма о белых путях|лемме о белых путях]] == white) dfs(во время выполнения процедуры поиска в глубину от вершины <tex> u </tex>, вершина <tex> v); if (color[v] == grey) print(); <font color=darkgreen/tex> будет серой. Так как из <tex> u </tex> есть ребро в <tex> v </ вывод ответа tex>, то это ребро в серую вершину. Следовательно <tex>\mathrm{dfs}(G)</fonttex> color[u] = black; нашел цикл.

== Реализация для случая неориентированного ориентированного графа == <font color=darkgreen>// color {{---}} массив цветов, изначально все вершины белые </font> '''func''' dfs(v: '''vertex'''): <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) '''if''' (color[u] == <i>grey</i>) print() <font color=darkgreen> // вывод ответа </font> color[v] = <i>black</i>

'''int''' graph== См. также ==* [[Использование обхода в глубину для проверки связности]]* [[Использование обхода в глубину для топологической сортировки]]; '''int''' color* [[Использование обхода в глубину для поиска компонент сильной связности]]* [[Использование обхода в глубину для поиска точек сочленения]]* [[Использование обхода в глубину для поиска мостов]] <tex> \leftarrow </tex> white; <font color=darkgreen> // Массив цветов, изначально все вершины белые </font>