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

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

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

 Maksim Dmitriev15 янв. 2017 г., 18:40
@HeshamYassin, если вы посещаете уже посещенный узел, это не обязательно означает, что есть петля. Пожалуйста, прочитайте мой комментарийcs.stackexchange.com/questions/9676/....
 user15246814 февр. 2015 г., 10:17
Вам следует прочитать статью Дональда Б. Джонсона «Нахождение всех элементарных цепей ориентированного графа». Он найдет только элементарные цепи, но этого должно быть достаточно для вашего случая. И вот моя реализация Java этого алгоритма готова к использованию:github.com/1123/johnson
 Steve Jessop04 нояб. 2008 г., 12:37
Вы говорите, что хотите обнаружить все циклы, но ваш вариант использования предполагает, что было бы достаточно определить, есть ли какие-либо циклы.
 Peauters04 нояб. 2008 г., 13:04
Было бы лучше обнаружить все циклы, чтобы их можно было исправить за один раз, а не проверять, исправлять, проверять, исправлять и т. Д.
 Don Hatch04 февр. 2019 г., 23:40
@Pneauters нет, не обязательно было бы лучше обнаруживать все циклы. Рассмотрим случай, когда их экспоненциальное число.
 Don Hatch04 февр. 2019 г., 23:37
Ваше первое предложение противоречит вашему последнему предложению; пожалуйста исправьте. Если вы действительно хотите обнаружитьвсе циклы (первое предложение), ваш выходной размер в наихудшем случае и время выполнения будут экспоненциальными по отношению к вашему входному размеру. Если вы действительно хотите просто обнаружить случай ошибкилюбой цикл (последнее предложение), вы можете сделать это во времени, который является линейным по размеру ввода. Я бы порекомендовал последнее.
 Hesham Yassin07 мая 2016 г., 11:32
Запустите DFS с дополнительной модификацией для алгоритма: отметьте каждый узел, который вы посетили. если вы посещаете уже посещенный узел, то у вас есть цикл. когда вы отступаете от пути, снимите отметку с посещаемых узлов.

Ответы на вопрос(14)

задний край обнаружен во время DFS, Это доказано в результате теории белого пути.

 jonaprieto06 дек. 2012 г., 22:58
Да, я думаю то же самое, но этого недостаточно, я выкладываю свой путь cs.stackexchange.com/questions/7216/find-the-simple-cycles-in-a-directed-graph
 Manohar Reddy Poreddy11 сент. 2016 г., 08:39
Правда. Аджай Гарг рассказывает только о том, как найти «цикл», что является частичным ответом на этот вопрос. Ваша ссылка говорит о поиске всех циклов в соответствии с заданным вопросом, но, опять же, похоже, что он использует тот же подход, что и Ajay Garg, но также делает все возможные dfs-деревья.

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

 noisy cat04 февр. 2014 г., 10:19
Сбой на 1,2,3: 1,2; 1,3; 2,3;
 noisy cat10 февр. 2014 г., 15:10
@JakeGreene Конечно, нет. Используя свой алгоритм и, начиная с 1, вы все равно обнаружите цикл ... Этот алгоритм просто плохой ... Обычно бывает достаточно идти назад, когда вы сталкиваетесь с посещенной вершиной.
 Kyrra25 дек. 2014 г., 05:29
@kittyPL DFS работает для обнаружения циклов с данного начального узла. Но при выполнении DFS вы должны раскрасить посещенные узлы, чтобы отличить край от края. При первом посещении вершины она становится серой, а затем вы становитесь черной после того, как все ее ребра пройдены. Если при выполнении DFS вы попали в серую вершину, то эта вершина является предком (то есть: у вас есть цикл). Если вершина чёрная, то это просто ребро.
 Jake Greene10 февр. 2014 г., 07:00
@kittyPL Этот график не содержит цикл. Из Википедии: «Направленный цикл в ориентированном графе - это последовательность вершин, начинающихся и заканчивающихся в одной и той же вершине, так что для каждых двух последовательных вершин цикла существует ребро, направленное от более ранней вершины к более поздней». Вы должны быть в состоянии следовать по пути из V, который ведет обратно к V в течение направленного цикла. решение мафони работает на данную проблему
 Jake Greene05 февр. 2014 г., 02:24
@kittyPL вы можете объяснить, почему это дело не удается? Либо 1) Это ориентированный граф, поэтому цикл не был сформирован, либо 2) DFS пошла бы 1 -> 2 (используя 1,2), 2 -> 3 (используя 2,3), 3 -> 1 (используя 1 , 3)
 noisy cat10 февр. 2014 г., 02:25
@JakeGreene Посмотрите здесь: i.imgur.com/tEkM5xy.png Достаточно просто для понимания. Допустим, вы начинаете с 0. Затем вы идете к узлу 1, путей больше нет, рекурсия возвращается назад. Теперь вы посещаете узел 2, который имеет ребро к вершине 1, которая уже была посещена. По вашему мнению, у вас был бы цикл, а у вас его нет
 Pavel18 сент. 2015 г., 17:07
@kittyPLm это неплохой алгоритм, если вы отслеживаете узлы, которые находятся в стеке рекурсивных вызовов.

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

 maaartinus11 сент. 2017 г., 22:25
@nbro Держу пари, они имеют в виду вариант алгоритма топологической сортировки, который прерывается, когда топологическая сортировка не существует (и тогда они не посещают все вершины).
 Oleg Mikheev20 янв. 2013 г., 02:59
из википедии:Многие алгоритмы топологической сортировки также обнаруживают циклы, поскольку они являются препятствиями для существования топологического порядка.
 nbro29 июл. 2015 г., 00:24
@OlegMikheev Да, но Стив говорит: «Если это число меньше общего числа вершин в DAG, у вас есть цикл», что не имеет смысла.
 UGP04 февр. 2018 г., 01:02
Если вы выполните топологическую сортировку на графике с циклом, вы получите заказ с наименьшим количеством плохих ребер (номер заказа> номер заказа соседа). Но после сортировки легко обнаружить те плохие ребра, которые приводят к обнаружению графа с циклом.
 sleske30 сент. 2009 г., 17:47
Это не имеет смысла. Если в графе есть циклы, топологическая сортировка отсутствует, что означает, что любой правильный алгоритм топологической сортировки будет прерван.

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

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

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

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

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

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

В примере в CLRS, рисунок 22.4, граф состоит из двух деревьев 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 discovered and 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.

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

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

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

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

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

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

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

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

|e| > |v| - 1

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

 EralpB07 мар. 2014 г., 14:38
Встречный пример?
 Hans-Peter Störr26 мая 2011 г., 11:20
Это может быть верно для неориентированных графов, но, конечно, не для ориентированных графов.
 user15246814 февр. 2015 г., 10:46
Контрпримером будет A-> B, B-> C, A-> C.
 Debanjan Dhar04 нояб. 2016 г., 11:58
Не все вершины имеют ребра.

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

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

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

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

 Deepak26 сент. 2012 г., 14:50
@peter, не могли бы вы объяснить, как DFT из A неверно решит, что цикл существует?
 Peter27 сент. 2012 г., 15:38
@Deepak - На самом деле, я неправильно прочитал ответ от "Phys Wizard": где он написал "в стеке" я думал, "уже найден". Действительно, было бы достаточно (для обнаружения направленного цикла) проверить наличие дубликатов «в стеке» во время выполнения ДПФ. Одно голосование за каждого из вас.
 James Wierzba03 авг. 2016 г., 22:27
Почему вы говорите, что сложность времениO(n) в то время как вы предлагаете проверить стек, чтобы увидеть, содержит ли он уже посещенный узел? Сканирование стека добавляет времяO(n) время выполнения, потому что он должен сканировать стек на каждом новом узле. Вы можете достичьO(n) если вы отметите посещенные узлы
 Peter29 мар. 2010 г., 19:19
Это было бы верно для «обычного» графа, но неверно длянаправленный граф. Например, рассмотрим «диаграмму зависимостей алмаза» с четырьмя узлами: A с ребрами, указывающими на B и C, каждый из которых имеет ребро, указывающее на D. Ваш обход DFT этой диаграммы из A неверно заключит, что «цикл» был фактически цикл - хотя есть цикл, это не цикл, потому что его нельзя пройти, следуя стрелкам.

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

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

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

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

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

 David Gish09 сент. 2016 г., 06:39
Почему у этого был отрицательный голос? Если ничего, ссылка на тему и, возможно, полезно.

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

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

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

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

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

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

Решение Вопроса

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

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

 Peauters04 нояб. 2008 г., 13:21
Спасибо Аку, это должно сработать, и это также будет означать, что я могу показать подграфы, вызывающие проблему.
 mgiuca09 февр. 2011 г., 02:13
@ Чедрик Верно, не напрямую. Это не недостаток алгоритма Тарьяна, а то, как он используется для этого вопроса. Тарьян не находит напрямуюциклы, он находит сильно связанные компоненты. Конечно, любой SCC с размером больше 1 подразумевает цикл. Нециклические компоненты сами имеют одноэлементную SCC. Проблема заключается в том, что самоконтроль также войдет в SCC сам по себе. Таким образом, вам нужна отдельная проверка для самоконтроля, что довольно тривиально.
 Peter29 мар. 2010 г., 19:21
Как поиск сильно связанных компонентов говорит вам о циклах, которые существуют в графе?
 optimusfrenk16 февр. 2015 г., 15:24
(все сильно связанные компоненты в графе)! = (все циклы в графе)
 aku03 апр. 2010 г., 11:39
 KGhatak23 июн. 2017 г., 18:29
@ аку: три цвета DFS также имеет то же время выполненияO(|E| + |V|), Используя цветовое кодирование белого (никогда не посещаемого), серого (текущий узел посещен, но все достижимые узлы еще не посещены) и черного (все посещаемые узлы посещаются вместе с текущим), если серый узел находит другой серый узел, то мы ' ве цикл. Почти то, что есть в книге алгоритмов Кормена. Хотите знать, имеет ли «алгоритм Тарьяна» какую-либо выгоду по сравнению с такой DFS!
 Adam Arold28 мар. 2015 г., 19:06
Пожалуйста, избегайте только ссылок.
 user15246814 февр. 2015 г., 10:22
Как отметил Питер, сильно связанные компоненты не эквивалентны циклам, но могут помочь в эффективном поиске циклов в графе. Для нахождения циклов см. Статью «Поиск всех элементарных циклов ориентированного графа» Дональда Джонсона и мою реализацию в Java:github.com/1123/johnson
 Cédric Guillemette14 сент. 2010 г., 15:05
Может быть, кто-то может подтвердить, но алгоритм Тарьяна не поддерживает циклы узлов, указывающих непосредственно на себя, как A-> A.
 João Almeida03 февр. 2017 г., 11:47
Из Википедии: «Если каждый сильно связный компонент свернут в одну вершину, результирующий граф является ориентированным ациклическим графом, конденсация G. Направленный граф является ациклическим тогда и только тогда, когда у него нет сильно связных подграфов с более чем одной вершиной. потому что направленный цикл является сильно связанным и каждый нетривиальный сильно связанный компонент содержит по крайней мере один направленный цикл ".

Ваш ответ на вопрос