Викиконспекты - Вклад участника [ru]

Использование обхода в глубину для поиска цикла

2012-04-09T21:57:02Z

178.70.142.20:

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

Решим эту задачу с помощью [[Обход в глубину, цвета вершин|поиска в глубину]] за <tex>O(M)</tex>.

= Алгоритм =

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

Сам цикл можно восстановить проходом по массиву предков.
[[Файл: Dfs_cycle.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> существует белый путь (они лежат на одном цикле), то по [[Лемма о белых путях|лемме о белых путях]] во время выполнения процедуры поиска в глубину от вершины <tex> u </tex>, вершина <tex> v </tex> будет серой. Так как из <tex> u </tex> есть ребро в <tex> v </tex>, то это ребро в серую вершину. Следовательно <tex>dfs(G)</tex> нашел цикл.

= Реализация =

Здесь приведена реализация алгоритма.

===Псевдокод===

int graph[][];
int color[];
dfs(int index)
color[index] = grey; // красит вершину в серый цвет
for (v : uv - ребро)
if ( color[v] == white )
dfs(v);
if ( color[v] == grey )
print(); // вывод ответа
color[index] = black; // красит вершину в черный цвет

== Литература ==
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ.[http://wmate.ru/ebooks/?dl=380&mirror=1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]

Использование обхода в глубину для поиска цикла

2012-04-09T21:56:00Z

178.70.142.20:

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

Решим эту задачу с помощью [[Обход в глубину, цвета вершин|поиска в глубину]] за <tex>O(M)</tex>.

= Алгоритм =

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

Сам цикл можно восстановить проходом по массиву предков.
[[Файл: Dfs_cycle.png|right|300px| Момент нахождения цикла]]

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

Пусть дан граф <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> нашел цикл.

= Реализация =

Здесь приведена реализация алгоритма.

===Псевдокод===

int graph[][];
int color[];
dfs(int index)
color[index] = grey; // красит вершину в серый цвет
for (v : uv - ребро)
if ( color[v] == white )
dfs(v);
if ( color[v] == grey )
print(); // вывод ответа
color[index] = black; // красит вершину в черный цвет

== Литература ==
* ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ.[http://wmate.ru/ebooks/?dl=380&mirror=1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.

[[Категория: Алгоритмы и структуры данных]]
[[Категория: Обход в глубину]]