Использование обхода в глубину для поиска цикла — различия между версиями
(→Доказательство) |
|||
| Строка 12: | Строка 12: | ||
= Доказательство = | = Доказательство = | ||
| − | Пусть дан граф <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> v </tex> достижима, так как между соседними вершинами в стеке есть ребро. Тогда если из рассматриваемой вершины <tex> v </tex> существует ребро в серую вершину <tex> u </tex>, то это значит, что из вершины <tex> u </tex> существует путь в <tex> v </tex> и из вершины <tex> v </tex> существует путь в <tex> u </tex> состоящий из одного ребра. И так как оба эти пути не пересекаются, то цикл существует. |
= Реализация = | = Реализация = | ||
| Строка 30: | Строка 30: | ||
print(); // вывод ответа | print(); // вывод ответа | ||
color[index] = black; // красит вершину в черный цвет | color[index] = black; // красит вершину в черный цвет | ||
| + | |||
| + | == Литература == | ||
| + | * ''Кормен Т., Лейзерсон Ч., Ривест Р.'' Алгоритмы: построение и анализ.[http://wmate.ru/ebooks/?dl=380&mirror=1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296. | ||
| + | |||
[[Категория: Алгоритмы и структуры данных]] | [[Категория: Алгоритмы и структуры данных]] | ||
[[Категория: Обход в глубину]] | [[Категория: Обход в глубину]] | ||
Версия 16:54, 22 декабря 2010
Постановка задачи
Пусть дан ориентированный граф без петель и кратных рёбер. Требуется проверить наличие цикла в этом графе.
Решим эту задачу с помощью поиска в глубину за O (M).
Алгоритм
Произведём серию поисков в глубину в графе. Т.е. из каждой вершины, в которую мы ещё ни разу не приходили, запустим поиск в глубину, который при входе в вершину будет красить её в серый цвет, а при выходе - в чёрный. И если поиск в глубину пытается пойти в серую вершину, то это означает, что мы нашли цикл.
Сам цикл можно восстановить проходом по массиву предков.
Доказательство
Пусть дан граф . Запустим . Рассмотрим выполнение процедуры поиска в глубину от некоторой вершины . Так как все серые вершины лежат в стеке рекурсии, то для них вершина достижима, так как между соседними вершинами в стеке есть ребро. Тогда если из рассматриваемой вершины существует ребро в серую вершину , то это значит, что из вершины существует путь в и из вершины существует путь в состоящий из одного ребра. И так как оба эти пути не пересекаются, то цикл существует.
Реализация
Здесь приведена реализация алгоритма на С++.
С++
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; // красит вершину в черный цвет
Литература
- Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.[1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.
