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

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

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

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

Алгоритм

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

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

Момент нахождения цикла: синие ребра - уже пройденные, красное ребро ведет в серую, уже пройденную, вершину.

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

Пусть дан граф [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] состоящий из одного ребра. И так как оба эти пути не пересекаются, то цикл существует.

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

Литература

• Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ.[1] — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296.