Алгоритм определения циклов

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

Принцип выделения циклов следующий. Если вершина имеет только входные или только выходные дуги, то она явно не входит ни в один цикл. Можно удалить все такие вершины из графа вместе со связанными с ними дугами. В результате появятся новые вершины, имеющие только входные или только выходные дуги. Они также удаляются. Итерации повторяются до тех пор, пока граф не перестанет изменяться. Отсутствие изменений свидетельствует об отсутствии циклов, если все вершины были удалены. Все оставшиеся вершины обязательно принадлежат циклам.

Сформулируем алгоритм, используя матрицу смежности (см. п. 2.3.3.2):

var

M: TAdjacencyMatrix;

repeat

for i := 1 to n begin

if строка M(i ,*) = 0 then обнулить столбец M(*, i);

if столбец M(*, i) = 0 then обнулить строку M(i ,*);

end;

until M не изменилась;

if M нулевая then граф ациклический

else граф содержит циклы;

Достоинством данного алгоритма является то, что происходит одновременное определение цикличности или ацикличности графа и исключение дуг, не входящих в циклы. После завершения алгоритма остается матрица смежности, соответствующая подграфу, содержащему все циклы исходного графа.

Рисунок 50. Определение циклов

В худшем случае этот алгоритм дает временную сложность T_max(n), пропорциональную O(n³).