Изменения

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

[[Файл: Dfs_cycle.png|thumb|200px|right| Момент нахождения цикла: синие ребра {{- --}} уже пройденные, красное ребро ведет в серую, уже пройденную, вершину.]]

Докажем, что если в графе <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> нашел цикл.

===Псевдокод===  int graph[][]; int color[]; '''func''' dfs(u: '''int index''') : color[indexu] = grey; <font color=darkgreen> // красит вершину u в серый цвет</font> '''for ''' (v : uv {{--- ребро}} edge) if ( color[v] == white )

if ( color[v] == grey ) print(); <font color=darkgreen> // вывод ответа </font> color[indexu] = black; <font color=darkgreen> // красит вершину u в черный цвет</font>

== Литература Источники информации ==* [http://e-maxx.ru/algo/finding_cycle MAXimal :: algo {{---}} «Проверка графа на ацикличность и нахождение цикла»]* [http://shujkova.ru/sites/default/files/algorithm2.pdf Прикладные задачи алгоритма DFS]