Изменения

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

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

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

Пусть дан граф <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 </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> нашел циклВсе вынутые вершины будут лежать на искомом цикле.

Здесь приведена реализация алгоритма[[Файл: Dfs_cycle.png|thumb|200px|right| Момент нахождения цикла: <font color=blue>синие</font> ребра {{---}} уже пройденные, <font color=red>красное</font> ребро ведет в серую, уже пройденную, вершину.]]

===Псевдокод=Доказательство ==

int graph[][]; int color[]; Пусть дан граф <tex>G</tex>. Запустим <tex>\mathrm{dfs}(int indexG) color[index] = grey; </tex>. Рассмотрим выполнение процедуры поиска в глубину от некоторой вершины <tex> v </ красит вершину tex>. Так как все серые вершины лежат в серый цвет for (стеке рекурсии, то для них вершина <tex> v : uv - ребра) if ( color[</tex> достижима, так как между соседними вершинами в стеке есть ребро. Тогда, если из рассматриваемой вершины <tex> v] == white ) dfs(v); if ( color[v] == grey ) print(); </tex> существует ребро в серую вершину <tex> u </tex>, то это значит, что из вершины <tex> u </ вывод ответа color[index] = black; 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> == См. также ==* [[Использование обхода в глубину для проверки связности]]* [[Использование обхода в глубину для топологической сортировки]]* [[Использование обхода в глубину для поиска компонент сильной связности]]* [[Использование обхода в глубину для поиска точек сочленения]]* [[Использование обхода в глубину для поиска мостов]] == Источники информации ==* [http://e-maxx.ru/algo/finding_cycle MAXimal :: algo {{---}} «Проверка графа на ацикличность и нахождение цикла»]* [http://shujkova.ru/sites/default/files/algorithm2.pdf Прикладные задачи алгоритма DFS]