= Постановка задачи ={{ЗадачаПусть дан [[ориентированный граф|ориентированный definition = Дан граф]] без петель и кратных рёбер. Требуется , требуется проверить наличие [[Основные определения теории графов|цикла]] в этом графе.}}
Решим эту задачу с помощью [[Обход в глубину, цвета вершин|поиска в глубину]] за O (M).== Алгоритм ==
= Алгоритм =Будем решать задачу с помощью [[Обход в глубину, цвета вершин|поиска в глубину]].
Произведём В случае <b>ориентированного графа</b> произведём серию поисков в глубину в графе. Т.еобходов. То есть из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе из нее {{- --}} в чёрный. И , если поиск в глубину алгоритм пытается пойти в серую вершину, то это означает, что мы нашли циклнайден.
Сам цикл можно восстановить проходом В случае <b>неориентированного графа</b>, одно ребро не должно встречаться в [[Основные определения теории графов#def_no_graph_path|цикле]] дважды по массиву предковопределению. Поэтому необходимо дополнительно проверять, что текущее рассматриваемое из вершины ребро не являетя тем ребром, по которому мы пришли в эту вершину.
= Реализация =Заметим, что, если в графе есть вершины с петлями, то алгоритм будет работать корректно, так как при запуске поиска в глубину из такой вершины, найдется ребро, ведущее в нее же, а значит эта петля и будет являться циклом.
Здесь приведена реализация алгоритма Для восстановления самого цикла достаточно при запуске поиска в глубину из очередной вершины добавлять эту вершину в [[Стек|стек]]. Когда поиск в глубину нашел вершину, которая лежит на С++цикле, будем последовательно вынимать вершины из стека, пока не встретим найденную еще раз. Все вынутые вершины будут лежать на искомом цикле.
===САсимптотика поиска цикла совпадает с асимптотикой поиска в глубину {{---}} <tex>O(|V| ++===|E|)</tex>.
vector [[Файл: Dfs_cycle.png|thumb|200px|right| Момент нахождения цикла: < vectorfont color=blue>синие<int/font> ребра {{---}} уже пройденные, <font color=red> graph;красное</font> ребро ведет в серую, уже пройденную, вершину.]] vector== Доказательство == Пусть дан граф <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 <int/tex> color;состоящий из одного ребра. И так как оба эти пути не пересекаются, то цикл существует. void Докажем, что если в графе <tex>G</tex> существует цикл, то <tex>\mathrm{dfs}(int indexG) </tex> его всегда найдет. Пусть <tex> v </tex> {{ color---}} первая вершина принадлежащая циклу, рассмотренная поиском в глубину. Тогда существует вершина <tex> u </tex>, принадлежащая циклу и имеющая ребро в вершину <tex> v </tex>. Так как из вершины <tex> v </tex> в вершину <tex> u </tex> существует белый путь (они лежат на одном цикле), то по [[indexЛемма о белых путях|лемме о белых путях]] = 1; во время выполнения процедуры поиска в глубину от вершины <tex> u </tex>, вершина <tex> v </tex> будет серой. Так как из <tex> u </tex> есть ребро в <tex> v </ красит tex>, то это ребро в серую вершину в серый цвет. Следовательно <tex>\mathrm{dfs}(G)</tex> нашел цикл. == Реализация для случая ориентированного графа == for (vector <font color=darkgreen>// color {{---}} массив цветов, изначально все вершины белые <int/font> '''func''' dfs(v:'''vertex'''):iterator i <font color= graphdarkgreen> // v {{---}} вершина, в которой мы сейчас находимся </font> color[indexv].begin(); = <i != graph[index].end(); ++>grey</i)> {'''for''' (u: vu <tex>\in</tex> E) '''if ''' ( color[*iu] == 0 <i>white</i>) dfs(*iu); '''if ''' ( color[*iu] == 1 <i>grey</i>) print(); <font color=darkgreen> // вывод ответа </font> } color[indexv] = 2; <i>black<// красит вершину i> == См. также ==* [[Использование обхода в глубину для проверки связности]]* [[Использование обхода в глубину для топологической сортировки]]* [[Использование обхода в глубину для поиска компонент сильной связности]]* [[Использование обхода в глубину для поиска точек сочленения]]* [[Использование обхода в черный цветглубину для поиска мостов]] == Источники информации ==* [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. [[Категория: Алгоритмы и структуры данных]][[Категория: Обход в глубину]]
