Изменения

Перейти к: навигация, поиск
пункты 2, 5 - 11
Пусть дан граф без петель и кратных рёбер. Требуется проверить наличие [[Основные определения теории графов|цикла]] в этом графе.
Решим эту задачу с помощью [[Обход в глубину, цвета вершин|поиска в глубину]] за <tex>O(|V| + |E|)</tex>.
== Алгоритм ==
Для восстановления самого цикла достаточно при запуске поиска в глубину из очередной вершины добавлять эту вершину в стек. Когда поиск в глубину нашел вершину, которая лежит на цикле, будем последовательно вынимать вершины из стека, пока не встретим найденную еще раз. Все вынутые вершины будут лежать на искомом цикле.
[[Файл: Dfs_cycle.png|thumb|200px|right| Момент нахождения цикла: <font color=blue>синие </font> ребра {{---}} уже пройденные, <font color=red>красное </font> ребро ведет в серую, уже пройденную, вершину.]]
== Доказательство ==
Пусть дан граф <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 </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(v)
'''if''' (color[u] == <i>grey</i>)
print() <font color=darkgreen> // вывод ответа </font>
color[v] = <i>black</i>
'''int''' graph[][];
'''int''' color[] <tex> \leftarrow </tex> white; <font color=darkgreen> // Массив цветов, изначально все вершины белые </font>
 
'''func''' dfs(u: '''int'''): <font color=darkgreen> // u {{---}} вершина, в которой мы сейчас находимся </font>
color[u] = grey;
'''for''' (v : uv {{---}} edge)
if (color[v] == white)
dfs(v);
if (color[v] == grey)
print(); <font color=darkgreen> // вывод ответа </font>
color[u] = black;
 
== Реализация для случая неориентированного графа ==
 
'''int''' graph[][];
'''int''' color[] <tex> \leftarrow </tex> white; <font color=darkgreen> // Массив цветов, изначально все вершины белые </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 {{---}} «Проверка графа на ацикличность и нахождение цикла»]
* [http://shujkova.ru/sites/default/files/algorithm2.pdf Прикладные задачи алгоритма DFS]
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ.[http://wmate.ru/ebooks/?dl=380&mirror=1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]
42
правки

Навигация