Проверка орграфа на ацикличность

Алгоритмы   1 Апрель 2015  Автор статьи:  

Пусть дан орграф G(V, E) без петель и кратных дуг. Требуется ответить на вопрос, содержит ли исходный орграф G цикл или является ациклическим.

Данная задача решается на основе метода обхода в глубину с использованием раскраски вершин исходного орграфа G(V, E) в три цвета. Каждая вершина v \in V вначале белая. Будучи обнаруженной в процессе обхода, ее цвет становится серым. Цвет вершины станет черным, когда она будет полностью обработана, то есть когда список смежных с ней вершин будет просмотрен. Каждая вершина v попадает ровно в одно дерева обхода в глубину, так что эти деревья не пересекаются.

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

 

Пошаговое представление

G(V, E) – исходный граф, в котором V – это множество вершин, а E – это множество ребер.
colov – массив для хранения цветов вершин графа G.
pred – массив предков, необходимых для восстановления цикла, в случае его наличия.
cyclic — булевская переменная, служащая индикатором того, является орграф ациклическим или нет. Переменная cyclic принимает значение {\bf false}, если орграф G является ациклическим, и значение {\bf true}, если орграф содержит хотя бы один цикл.

1
2
3
4
{\bf for} (для) всех вершин v \in V[G]
    color[v] \gets {\bf 0} //изначально цвет каждой вершины является белым
    pred[v] \gets {\bf -1}
cyclic \gets {\bf false} //изначально считаем орграф ациклическим

 
DFS_CYCLE(v)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
{\bf if} color[v] = {\bf 2}
    {\bf return} //если вершина является черной, то не производим из нее вызов процедуры
{\bf if} cyclic = {\bf true}
    {\bf return} //выходим из процедуры, если уже нашли один из циклов
{\bf if} color[v] = {\bf 1} //если вершина является серой, то орграф содержит цикл
    {\bf cyclic \gets true} //помечаем орграф, как содержащий цикл
    {\bf return}
color[v] \gets {\bf 1} //вершина обнаружена, помечаем ее цвет серым
{\bf for} (для) всех вершин w \in E[v] //обрабатываем ребро (v, w)
    pred[w] \gets v //помечаем вершину v как предка вершины w при обходе
    DFS\_CYCLE(w) //вызываем процедуру рекурсивно от каждой вершины w, смежной с вершиной v
   {\bf if} cyclic = {\bf true} //выходим из процедуры, если уже нашли один из циклов
       {\bf return}
color[v] \gets {\bf 2} //вершина обработана, устанавливаем ее цвет черным

Сам цикл, в случае его наличия, можно восстановить проходом по массиву предков. Наглядно процедуру восстановления цикла смотрите в статьях по реализации алгоритма на языке Java и на языке С++

Примеры

Рассмотрим работу алгоритма и процесс окрашивание вершин исходного орграфа на двух примерах. Вершины на схемах окрашены в белый, серый и черный цвет согласно описанию выше. Просмотренные дуги в процессе обхода выделены жирным шрифтом.

Орграф G_1, изображенный на первом рисунке, содержит цикл 1 \rightarrow 2 \rightarrow 3 \rightarrow 1.

демонстрация обхода в глубину

Стадии окрашивания вершин и посещения дуг орграфа G_1 изображены на схемах (a-г). На стадии (г) по обратной дуге (1, 3) обход попадает в серую вершину 1, что говорит о наличии цикла в орграфе G_1.

 

Орграф G_2, изображенный на втором рисунке, является ациклическим.

демонстрация обхода в глубину

Стадии окрашивания вершин и посещения дуг орграфа G_2 изображены на схемах (a-и). Ни на одной стадии (a-и) обход не проходит по обратной дуге. На стадиях (a-г) обход идет по дугам дерева обхода в белые вершины. На стадиях (д-з) серые вершины становятся черными. На стадии (и) обход идет по прямой дуге (1, 4) в уже просмотренную вершину черного цвета.

 

Асимптотическая сложность

Процесс инициализации массива color и массива pred осуществляется за O(|V|).
Процедура DFS_CYCLE вызывается ровно по одному разу для каждой вершины v \in V орграфа, так как она вызывается только для белых вершин, то есть еще не обработанных. Первое, что она делает, это помечает переданную в качестве параметра вершину v процедуры как серую, строка 5. В процессе выполнения процедуры DFS_CYCLE цикл в строках 9 - 13 выполняется ровно |adj[v]| раз. Так как \sum_{v \in V} |adj [v]|=O(|E|), то общая стоимость выполнения строк 9 - 13 процедуры DFS_CYCLE равна O(|E|). В строке 14 вершина v помечается как черная за O(1), так как становится обработанной.
Таким образом, асимптотическая сложность алгоритма проверки орграфа на ацикличность равна O(|V|+|E|), то есть такая же, как и асимптотическая сложность алгоритма обхода в глубину.

Реализации проверки орграфа на ацикличность

Научиться программировать

  • на Delphi

  • на Java

  • на C++