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

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

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

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

Реализация

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

С++

vector < vector<int> > graph;
vector<int> color;

void dfs(int index) 
{
    color[index] = 1;      // красит вершину в серый цвет
    for (vector<int>::iterator i = graph[index].begin(); i != graph[index].end(); ++i)
    {
        if ( color[*i] == 0 )
            dfs(*i);
        if ( color[*i] == 1 )
            print();       // вывод ответа   
    }
    color[index] = 2;      // красит вершину в черный цвет
}