Пусть дан [[ориентированный граф{{Задача|ориентированный definition = Дан граф]] без петель и кратных рёбер. Требуется , требуется проверить наличие [[Основные определения теории графов|цикла]] в этом графе.}}
Решим эту == Алгоритм == Будем решать задачу с помощью [[Обход в глубину, цвета вершин|поиска в глубину]] за . В случае <texb>O(M)ориентированного графа</texb>произведём серию обходов. То есть из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе из нее {{---}} в чёрный. И, если алгоритм пытается пойти в серую вершину, то это означает, что цикл найден.
== Алгоритм ==В случае <b>неориентированного графа</b>, одно ребро не должно встречаться в [[Основные определения теории графов#def_no_graph_path|цикле]] дважды по определению. Поэтому необходимо дополнительно проверять, что текущее рассматриваемое из вершины ребро не является тем ребром, по которому мы пришли в эту вершину.
Произведём серию поисков в глубину Заметим, что, если в графе. Т.е. из каждой есть вершиныс петлями, в которую мы ещё ни разу не приходилито алгоритм будет работать корректно, запустим поиск так как при запуске поиска в глубинуиз такой вершины, найдется ребро, который при входе в вершину будет красить её ведущее в серый цветнее же, а при выходе - в чёрный. И если поиск в глубину пытается пойти в серую вершину, то это означает, что мы нашли циклзначит эта петля и будет являться циклом.
Сам цикл можно восстановить проходом по массиву предков.Для восстановления самого цикла достаточно при запуске поиска в глубину из очередной вершины добавлять эту вершину в [[Файл: Dfs_cycleСтек|стек]].png|thumb|200px|right| Момент нахождения цикла: синие ребра - уже пройденныеКогда поиск в глубину нашел вершину, красное ребро ведет в серуюкоторая лежит на цикле, уже пройденнуюбудем последовательно вынимать вершины из стека, вершинупока не встретим найденную еще раз. Все вынутые вершины будут лежать на искомом цикле.]]
== Доказательство ==Асимптотика поиска цикла совпадает с асимптотикой поиска в глубину {{---}} <tex>O(|V| + |E|)</tex>.
Пусть дан граф <tex>G</tex>[[Файл: Dfs_cycle. Запустим png|thumb|200px|right| Момент нахождения цикла: <texfont color=blue>dfs(G)синие</texfont>. Рассмотрим выполнение процедуры поиска в глубину от некоторой вершины <tex> v </tex>. Так как все серые вершины лежат в стеке рекурсии, то для них вершина <tex> v </tex> достижимаребра {{---}} уже пройденные, так как между соседними вершинами в стеке есть ребро. Тогда если из рассматриваемой вершины <texfont color=red> v красное</texfont> существует ребро ведет в серую вершину <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> нашел цикл.== Доказательство ==
== Реализация ==Пусть дан граф <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>\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> нашел цикл.
==Реализация для случая ориентированного графа =Псевдокод= <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* [[Использование обхода в глубину для топологической сортировки]]; dfs(int index) color* [[indexИспользование обхода в глубину для поиска компонент сильной связности]] = grey; // красит вершину в серый цвет for (v : uv - ребро) if ( color* [[vИспользование обхода в глубину для поиска точек сочленения]] == white ) dfs(v); if ( color* [[vИспользование обхода в глубину для поиска мостов] == grey ) print(); // вывод ответа color[index] = black; // красит вершину в черный цвет
== Литература Источники информации ==* [http://e-maxx.ru/algo/finding_cycle MAXimal :: algo {{---}} «Проверка графа на ацикличность и нахождение цикла»]* [http://shujkova.ru/sites/default/files/algorithm2.pdf Прикладные задачи алгоритма DFS]
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ.[http://wmate.ru/ebooks/?dl=380&mirror=1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]
