42
правки
Изменения
Добавлен случай неориентированности
Пусть дан [[ориентированный граф|ориентированный граф]] без петель и кратных рёбер. Требуется проверить наличие [[Основные определения теории графов|цикла]] в этом графе.
Решим эту задачу с помощью [[Обход в глубину, цвета вершин|поиска в глубину]] за <tex>O(M)</tex>.
== Алгоритм ==
Пусть дан <b>ориентированный граф</b>. Произведём серию поисков в глубину в графе. Т.е. из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе {{---}} в чёрный. И если поиск в глубину пытается пойти в серую вершину, то это означает, что мы нашли цикл.
[[Файл: 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[] <tex> \leftarrow </tex> white;<font color=darkgreen> // Массив цветов, изначально все вершины белые </font>
'''func''' dfs(u: '''int'''): color[u] = grey; <font color=darkgreen> // красит вершину u {{---}} вершина, в серый цвет которой мы сейчас находимся </font> color[u] = grey;
'''for''' (v : uv {{---}} edge)
if (color[v] == white)
if (color[v] == grey)
print(); <font color=darkgreen> // вывод ответа </font>
color[u] = black; == Реализация для случая неориентированного графа == '''int''' graph[][]; '''int''' color[] <tex> \leftarrow </tex> white; <font color=darkgreen> // красит вершину u в черный цвет Массив цветов, изначально все вершины белые </font>
'''func''' dfs(u, par: '''int'''): <font color=darkgreen> // u {{---}} вершина, в которой мы сейчас находимся; par {{---}} вершина, из которой мы пришли в u </font>
color[u] = grey;
'''for''' (v : uv {{---}} edge)
if (color[v] == white)
dfs(v, u);
if (color[v] == grey '''and''' v <tex>\neq</tex> par)
print(); <font color=darkgreen> // вывод ответа </font>
color[u] = black;
== Источники информации ==
* [http://e-maxx.ru/algo/finding_cycle MAXimal :: algo {{---}} «Проверка графа на ацикличность и нахождение цикла»]
