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

Задача:

Дан граф, требуется проверить наличие цикла в этом графе. Будем решать задачу с помощью поиска в глубину за [math]O(|V| + |E|)[/math].

Алгоритм

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

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

Для восстановления самого цикла достаточно при запуске поиска в глубину из очередной вершины добавлять эту вершину в стек. Когда поиск в глубину нашел вершину, которая лежит на цикле, будем последовательно вынимать вершины из стека, пока не встретим найденную еще раз. Все вынутые вершины будут лежать на искомом цикле.

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

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

Пусть дан граф [math]G[/math]. Запустим [math]\mathrm{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]\mathrm{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]\mathrm{dfs}(G)[/math] нашел цикл.

Заметим, что, если в графе есть вершины с петлями, то алгоритм будет работать корректно, так как при запуске поиска в глубину из такой вершины, найдется ребро, ведущее в нее же, а значит эта петля и будет являться циклом.

Реализация для случая ориентированного графа

// color — массив цветов, изначально все вершины белые  
func dfs(v: vertex):           // v — вершина, в которой мы сейчас находимся 
    color[v] = grey             
    for (u: vu [math]\in[/math] E)
        if (color[u] == white)
            dfs(v)
        if (color[u] == grey)
            print()              // вывод ответа    
    color[v] = black         

См. также

• Использование обхода в глубину для проверки связности
• Использование обхода в глубину для топологической сортировки
• Использование обхода в глубину для поиска компонент сильной связности
• Использование обхода в глубину для поиска точек сочленения
• Использование обхода в глубину для поиска мостов

Источники информации

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