Лучший алгоритм обнаружения циклов в ориентированном графе

396

Каков наиболее эффективный алгоритм обнаружения всех циклов в ориентированном графе?

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

Peauters
источник
13
Вы говорите, что хотите обнаружить все циклы, но ваш вариант использования предполагает, что было бы достаточно определить, есть ли какие-либо циклы.
Стив Джессоп
29
Было бы лучше обнаружить все циклы, чтобы их можно было исправить за один раз, а не проверять, исправлять, проверять, исправлять и т. Д.
Peauters
2
Вам следует прочитать статью Дональда Б. Джонсона «Нахождение всех элементарных цепей ориентированного графа». Он найдет только элементарные цепи, но этого должно быть достаточно для вашего случая. И вот моя реализация Java этого алгоритма, готовая к использованию: github.com/1123/johnson
user152468
Запустите DFS с дополнительной модификацией для алгоритма: отметьте каждый узел, который вы посетили. если вы посещаете уже посещенный узел, то у вас есть цикл. когда вы отступаете от пути, снимите отметку с посещаемых узлов.
Хешам Яссин
2
@HeshamYassin, если вы посещаете уже посещенный узел, это не обязательно означает, что есть петля. Пожалуйста, прочитайте мой комментарий cs.stackexchange.com/questions/9676/… .
Максим Дмитриев

Ответы:

193

Алгоритм сильно связанных компонент Тарьяна имеет O(|E| + |V|)временную сложность.

Другие алгоритмы см. В разделе Сильно связанные компоненты в Википедии.

Ака
источник
70
Как поиск сильно связанных компонентов говорит вам о циклах, которые существуют в графе?
Питер
4
Может быть, кто-то может подтвердить, но алгоритм Тарьяна не поддерживает циклы узлов, указывающих непосредственно на себя, как A-> A.
Седрик Гиймет
24
@ Чедрик Верно, не напрямую. Это не недостаток алгоритма Тарьяна, а то, как он используется для этого вопроса. Тарьян не находит циклы напрямую , он находит сильно связанные компоненты. Конечно, любой SCC с размером больше 1 подразумевает цикл. Нециклические компоненты сами имеют одноэлементную SCC. Проблема заключается в том, что самоконтроль также войдет в SCC сам по себе. Таким образом, вам нужна отдельная проверка для самоконтроля, что довольно тривиально.
mgiuca
13
(все сильно связанные компоненты в графе)! = (все циклы в графе)
optimusfrenk
4
@ аку: три цвета DFS также имеет то же время выполнения O(|E| + |V|). Используя кодирование белого (никогда не посещаемого), серого (текущий узел посещен, но все достижимые узлы еще не посещены) и черного (все доступные узлы посещаются вместе с текущим) кодирования цвета, если серый узел находит другой серый узел, то мы ' ве цикл. Почти то, что есть в книге алгоритмов Кормена. Хотите знать, имеет ли «алгоритм Тарьяна» какую-либо выгоду по сравнению с DFS!
К.Гатак
73

Учитывая, что это график работ, я подозреваю, что в какой-то момент вы собираетесь отсортировать их по предлагаемому порядку выполнения.

Если это так, то реализация топологической сортировки может в любом случае обнаружить циклы. UNIX, tsortбезусловно, делает. Я думаю, что, вероятно, поэтому более эффективно определять циклы одновременно с сортировкой, а не на отдельном этапе.

Таким образом, вопрос может звучать так: «Как мне наиболее эффективно использовать сортировку», а не «Как мне наиболее эффективно обнаруживать петли». На что ответ, вероятно, «использовать библиотеку», но не в том, что следующая статья в Википедии:

http://en.wikipedia.org/wiki/Topological_sorting

имеет псевдокод для одного алгоритма и краткое описание другого от Тарьяна. Оба имеют O(|V| + |E|)временную сложность.

Стив Джессоп
источник
Топологическая сортировка может обнаруживать циклы, поскольку она основывается на алгоритме поиска в глубину, но вам требуется дополнительная бухгалтерия для фактического обнаружения циклов. Смотрите правильный ответ Курта Пика.
Люк Хатчисон
33

Простейший способ сделать это - сделать первый проход по глубине (DFT) графа .

Если у графа есть nвершины, это O(n)алгоритм временной сложности. Поскольку вам, возможно, придется выполнять ДПФ, начиная с каждой вершины, общая сложность становится равной O(n^2).

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

nbro
источник
21
Это было бы верно для «регулярного» графа, но неверно для ориентированного графа. Например, рассмотрим «диаграмму зависимостей алмаза» с четырьмя узлами: A с ребрами, указывающими на B и C, каждый из которых имеет ребро, указывающее на D. Ваш DFT-обход этой диаграммы из A неверно заключит, что «цикл» был фактически цикл - хотя есть цикл, это не цикл, потому что его нельзя пройти, следуя стрелкам.
Питер
9
@peter, не могли бы вы объяснить, как DFT из A неверно решит, что цикл существует?
Дипак,
10
@Deepak - На самом деле, я неправильно прочитал ответ от "Phys Wizard": где он написал "в стеке" я думал, "уже найден". Действительно, было бы достаточно (для обнаружения направленного цикла) проверить наличие дубликатов «в стеке» во время выполнения ДПФ. Одно голосование за каждого из вас.
Питер
2
Почему вы говорите, что сложность времени заключается в том O(n), что вы предлагаете проверить стек, чтобы увидеть, содержит ли он уже посещенный узел? Сканирование стека увеличивает время O(n)выполнения, поскольку необходимо сканировать стек на каждом новом узле. Вы можете достичь, O(n)если отметите посещенные узлы
Джеймс Вежба
Как сказал Питер, для ориентированных графов это неполно. Смотрите правильный ответ Курта Пика.
Люк Хатчисон
32

Согласно лемме 22.11 Кормена и др., Введение в алгоритмы (CLRS):

Ориентированный граф G ацикличен тогда и только тогда, когда поиск G в глубину не дает обратных ребер.

Это было упомянуто в нескольких ответах; здесь я также приведу пример кода, основанного на главе 22 CLRS. Пример графика показан ниже.

введите описание изображения здесь

Псевдокод CLRS для поиска в глубину гласит:

введите описание изображения здесь

В примере на рисунке 22.4 в CLRS график состоит из двух деревьев DFS: одно состоит из узлов u , v , x и y , а другое - из узлов w и z . Каждое дерево содержит один задний край: один от x до v и другой от z до z (самоконтроль).

Ключ реализации является то , что задний край встречается , когда в DFS-VISITфункции, в то время как итерация соседей vиз u, узел встречается с GRAYцветом.

Следующий код Python - это адаптация псевдокода CLRS с ifдобавленным предложением, которое обнаруживает циклы:

import collections


class Graph(object):
    def __init__(self, edges):
        self.edges = edges
        self.adj = Graph._build_adjacency_list(edges)

    @staticmethod
    def _build_adjacency_list(edges):
        adj = collections.defaultdict(list)
        for edge in edges:
            adj[edge[0]].append(edge[1])
        return adj


def dfs(G):
    discovered = set()
    finished = set()

    for u in G.adj:
        if u not in discovered and u not in finished:
            discovered, finished = dfs_visit(G, u, discovered, finished)


def dfs_visit(G, u, discovered, finished):
    discovered.add(u)

    for v in G.adj[u]:
        # Detect cycles
        if v in discovered:
            print(f"Cycle detected: found a back edge from {u} to {v}.")

        # Recurse into DFS tree
        if v not in finished:
            dfs_visit(G, v, discovered, finished)

    discovered.remove(u)
    finished.add(u)

    return discovered, finished


if __name__ == "__main__":
    G = Graph([
        ('u', 'v'),
        ('u', 'x'),
        ('v', 'y'),
        ('w', 'y'),
        ('w', 'z'),
        ('x', 'v'),
        ('y', 'x'),
        ('z', 'z')])

    dfs(G)

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

Когда этот скрипт выполняется, он печатает следующий вывод:

Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.

Это именно задние края в примере в CLRS Рисунок 22.4.

Курт Пик
источник
29

Начните с DFS: цикл существует тогда и только тогда, когда во время DFS обнаруживается обратная сторона . Это доказано в результате теории белого пути.

Аджай Гарг
источник
3
Да, я думаю, что то же самое, но этого недостаточно, я публикую свой путь cs.stackexchange.com/questions/7216/find-the-simple-cycles-in-a-directed-graph
jonaprieto
Правда. Аджай Гарг рассказывает только о том, как найти «цикл», что является частичным ответом на этот вопрос. Ваша ссылка говорит о поиске всех циклов в соответствии с заданным вопросом, но, опять же, похоже, что он использует тот же подход, что и Ajay Garg, но также делает все возможные dfs-деревья.
Манохар Редди Поредди
Это неполно для ориентированных графов. Смотрите правильный ответ Курта Пика.
Люк Хатчисон
26

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

По сути, алгоритм раскраски графа обходит граф DFS (поиск в глубину вначале, что означает, что он полностью исследует путь, прежде чем исследовать другой путь). Когда он находит задний край, он помечает график как содержащий цикл.

Для более подробного объяснения алгоритма раскраски графа, пожалуйста, прочитайте эту статью: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/

Также я предоставляю реализацию раскраски графов в JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js

Армин Примади
источник
8

Если вы не можете добавить «посещенное» свойство к узлам, используйте набор (или карту) и просто добавьте все посещенные узлы в набор, если они уже не находятся в наборе. Используйте уникальный ключ или адрес объектов в качестве «ключа».

Это также дает вам информацию о «корневом» узле циклической зависимости, которая пригодится, когда пользователь должен будет решить проблему.

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

Хотя это может показаться сложным O (N * M), вы должны помнить, что стек имеет очень ограниченную глубину (поэтому N мала) и что M становится меньше с каждой зависимостью, которую вы можете отметить как «выполненная» плюс вы можете остановить поиск, когда найдете лист (поэтому вам не нужно проверять каждый узел -> M тоже будет маленьким).

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

Если вам нужен режим «только тест», просто добавьте флаг «пробного запуска», который отключает выполнение реальных заданий.

Аарон Дигулла
источник
7

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

Юйвэнь
источник
1
Истинно, если в качестве размера входных данных принимается количество узлов. Вы также можете описать сложность среды выполнения с точки зрения количества ребер или даже циклов или комбинации этих мер. Алгоритм «Нахождение всех элементарных цепей ориентированного графа» Дональда Б. Джонсона имеет полиномиальное время работы, заданное O ((n + e) ​​(c + 1)), где n - количество узлов, e - количество ребер. и c количество элементарных цепей графа. А вот моя реализация этого алгоритма на Java: github.com/1123/johnson .
user152468 14.02.15
4

Я реализовал эту проблему в SML (императивное программирование). Вот схема. Найдите все узлы, которые имеют степень или степень 0. Такие узлы не могут быть частью цикла (поэтому удалите их). Затем удалите все входящие или исходящие ребра из таких узлов. Рекурсивно применить этот процесс к результирующему графу. Если в конце у вас не осталось ни одного узла или ребра, у графа нет циклов, иначе есть.

Rpant
источник
2

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

Стив
источник
4
Это не имеет смысла. Если в графе есть циклы, топологическая сортировка отсутствует, что означает, что любой правильный алгоритм топологической сортировки будет прерван.
Слёске 30.09.09
4
из Википедии: Многие алгоритмы топологической сортировки также обнаруживают циклы, поскольку они являются препятствиями для существования топологического порядка.
Олег Михеев
1
@OlegMikheev Да, но Стив говорит: «Если это число меньше общего числа вершин в DAG, у вас есть цикл», что не имеет смысла.
nbro
@ nbro Держу пари, они имеют в виду вариант алгоритма топологической сортировки, который прерывается, когда топологическая сортировка не существует (и тогда они не посещают все вершины).
Маартин
Если вы выполните топологическую сортировку на графике с циклом, вы получите заказ с наименьшим количеством плохих ребер (номер заказа> номер заказа соседа). Но после сортировки легко обнаружить те плохие ребра, которые приводят к обнаружению графа с циклом
UGP
2

/mathpro/16393/finding-a-cycle-of-fixed-length Мне нравится это решение лучше всего специально для 4 длины :)

Также физик говорит, что ты должен сделать O (V ^ 2). Я считаю, что нам нужно только O (V) / O (V + E). Если граф подключен, DFS посетит все узлы. Если у графа есть связанные подграфы, то каждый раз, когда мы запускаем DFS на вершине этого подграфа, мы найдем связанные вершины и не будем рассматривать их для следующего запуска DFS. Поэтому возможность запуска для каждой вершины неверна.

amitgoswami
источник
1

Если DFS находит ребро, которое указывает на уже посещенную вершину, у вас есть цикл там.

mafonya
источник
1
Сбой на 1,2,3: 1,2; 1,3; 2,3;
шумный кот
4
@JakeGreene Посмотрите здесь: i.imgur.com/tEkM5xy.png Достаточно просто для понимания. Допустим, вы начинаете с 0. Затем вы идете к узлу 1, путей больше нет, рекурсия возвращается назад. Теперь вы посещаете узел 2, который имеет ребро к вершине 1, которая уже была посещена. По вашему мнению, у вас был бы цикл - а у вас его действительно нет
шумный кот
3
@kittyPL Этот график не содержит цикл. Из Википедии: «Направленный цикл в ориентированном графе - это последовательность вершин, начинающихся и заканчивающихся в одной и той же вершине, так что для каждых двух последовательных вершин цикла существует ребро, направленное от более ранней вершины к более поздней». Вы должны быть в состоянии следовать по пути из V, который ведет обратно к V в течение направленного цикла. Решение мафонии работает для данной проблемы
Джейк Грин
2
@JakeGreene Конечно, нет. Используя свой алгоритм и, начиная с 1, вы все равно обнаружите цикл ... Этот алгоритм просто плохой ... Обычно бывает достаточно идти назад, когда вы сталкиваетесь с посещенной вершиной.
шумный кот
6
@kittyPL DFS работает для обнаружения циклов с данного начального узла. Но при выполнении DFS вы должны раскрасить посещенные узлы, чтобы отличить край от края. При первом посещении вершины она становится серой, а затем, когда все ее ребра пройдены, вы становитесь черными. Если при выполнении DFS вы попали в серую вершину, то эта вершина является предком (то есть: у вас есть цикл). Если вершина чёрная, то это просто ребро.
Кирра
0

Как вы сказали, у вас есть набор заданий, его нужно выполнять в определенном порядке. Topological sortс учетом необходимого вам порядка для планирования заданий (или для проблем с зависимостями, если это так direct acyclic graph). Запустите dfsи сохраните список, и начните добавлять узел в начале списка, и если вы встретили узел, который уже посещен. Затем вы нашли цикл в данном графике.

Бхагвати Малав
источник
-11

Если график удовлетворяет этому свойству

|e| > |v| - 1

тогда граф содержит хотя бы по циклу.

дхармендра сингх
источник
10
Это может быть верно для неориентированных графов, но, конечно, не для ориентированных графов.
Ганс-Петер Стёрр
6
Контрпримером будет A-> B, B-> C, A-> C.
user152468
Не все вершины имеют ребра.
Дебанжан Дхар