Изменения

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

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

Сам цикл можно восстановить проходом по массиву предков.В случае <b>неориентированного графа</b>, одно ребро не должно встречаться в [[Файл: Dfs_cycleОсновные определения теории графов#def_no_graph_path|цикле]] дважды по определению.png|thumb|300px|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 </tex> состоящий из одного ребра. И так как оба эти пути не пересекаются, то цикл существуетбудут лежать на искомом цикле.

Докажем, что если Асимптотика поиска цикла совпадает с асимптотикой поиска в графе <tex>G</tex> существует цикл, то <tex>dfs(G)</tex> его всегда найдет. Пусть <tex> v </tex> глубину {{--- первая вершина принадлежащая циклу, рассмотренная поиском в глубину. Тогда существует вершина <tex> u </tex>, принадлежащая циклу и имеющая ребро в вершину <tex> v </tex>. Так как из вершины <tex> v </tex> в вершину }} <tex> u </tex> существует белый путь O(они лежат на одном цикле), то по [[Лемма о белых путях|лемме о белых путях]] во время выполнения процедуры поиска в глубину от вершины <tex> u </tex>, вершина <tex> v </tex> будет серой. Так как из <tex> u </tex> есть ребро в <tex> v </tex>, то это ребро в серую вершину. Следовательно <tex>dfs(GV| + |E|)</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> {{---}} первая вершина принадлежащая циклу, рассмотренная поиском в глубину. Тогда существует вершина <tex> u </ красит tex>, принадлежащая циклу и имеющая ребро в вершину <tex> v </tex>. Так как из вершины <tex> v </tex> в серый цвет for вершину <tex> u </tex> существует белый путь (v : uv - реброони лежат на одном цикле) if ( color, то по [[vЛемма о белых путях|лемме о белых путях] == white ) dfs(v); if ( color[v] == grey ) print(); во время выполнения процедуры поиска в глубину от вершины <tex> u </tex>, вершина <tex> v </ вывод ответа color[index] = black; 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]