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

Материал из Викиконспекты
Перейти к: навигация, поиск
(С++)
(Доказательство)
Строка 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> состоящий из одного ребра. И так как оба эти пути не пересекаются, то существует цикл.
  
 
= Реализация =
 
= Реализация =

Версия 16:52, 22 декабря 2010

Постановка задачи

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

Решим эту задачу с помощью поиска в глубину за O (M).

Алгоритм

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

Сам цикл можно восстановить проходом по массиву предков.

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

Пусть дан граф [math]G[/math]. Запустим [math]dfs(G)[/math]. Рассмотрим выполнение процедуры поиска в глубину от некоторой вершины [math] v [/math]. Так как все серые вершины лежат в стеке рекурсии, то для них вершина [math] v [/math] достижима, так как между соседними вершинами в стеке есть ребро. Тогда если из рассматриваемой вершины [math] v [/math] существует ребро в серую вершину [math] u [/math], то это значит, что из вершины [math] u [/math] существует путь в [math] v [/math] и из вершины [math] v [/math] существует путь в [math] u [/math] состоящий из одного ребра. И так как оба эти пути не пересекаются, то существует цикл.

Реализация

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

С++

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;        // красит вершину в черный цвет