Каков наиболее эффективный алгоритм обнаружения всех циклов в ориентированном графе?
У меня есть ориентированный граф, представляющий расписание заданий, которые должны быть выполнены, задание - это узел, а зависимость - ребро. Мне нужно обнаружить случай ошибки цикла в этом графе, что приводит к циклическим зависимостям.
algorithm
graph-theory
directed-graph
Peauters
источник
источник
Ответы:
Алгоритм сильно связанных компонент Тарьяна имеет
O(|E| + |V|)
временную сложность.Другие алгоритмы см. В разделе Сильно связанные компоненты в Википедии.
источник
O(|E| + |V|)
. Используя кодирование белого (никогда не посещаемого), серого (текущий узел посещен, но все достижимые узлы еще не посещены) и черного (все доступные узлы посещаются вместе с текущим) кодирования цвета, если серый узел находит другой серый узел, то мы ' ве цикл. Почти то, что есть в книге алгоритмов Кормена. Хотите знать, имеет ли «алгоритм Тарьяна» какую-либо выгоду по сравнению с DFS!Учитывая, что это график работ, я подозреваю, что в какой-то момент вы собираетесь отсортировать их по предлагаемому порядку выполнения.
Если это так, то реализация топологической сортировки может в любом случае обнаружить циклы. UNIX,
tsort
безусловно, делает. Я думаю, что, вероятно, поэтому более эффективно определять циклы одновременно с сортировкой, а не на отдельном этапе.Таким образом, вопрос может звучать так: «Как мне наиболее эффективно использовать сортировку», а не «Как мне наиболее эффективно обнаруживать петли». На что ответ, вероятно, «использовать библиотеку», но не в том, что следующая статья в Википедии:
имеет псевдокод для одного алгоритма и краткое описание другого от Тарьяна. Оба имеют
O(|V| + |E|)
временную сложность.источник
Простейший способ сделать это - сделать первый проход по глубине (DFT) графа .
Если у графа есть
n
вершины, этоO(n)
алгоритм временной сложности. Поскольку вам, возможно, придется выполнять ДПФ, начиная с каждой вершины, общая сложность становится равнойO(n^2)
.Вы должны поддерживать стек, содержащий все вершины в текущем проходе глубины , причем его первый элемент является корневым узлом. Если вы встретите элемент, который уже находится в стеке во время DFT, то у вас есть цикл.
источник
O(n)
, что вы предлагаете проверить стек, чтобы увидеть, содержит ли он уже посещенный узел? Сканирование стека увеличивает времяO(n)
выполнения, поскольку необходимо сканировать стек на каждом новом узле. Вы можете достичь,O(n)
если отметите посещенные узлыСогласно лемме 22.11 Кормена и др., Введение в алгоритмы (CLRS):
Это было упомянуто в нескольких ответах; здесь я также приведу пример кода, основанного на главе 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
добавленным предложением, которое обнаруживает циклы:Обратите внимание, что в этом примере
time
псевдокод в CLRS не фиксируется, потому что мы заинтересованы только в обнаружении циклов. Существует также некоторый шаблонный код для построения представления списка смежности графа из списка ребер.Когда этот скрипт выполняется, он печатает следующий вывод:
Это именно задние края в примере в CLRS Рисунок 22.4.
источник
Начните с DFS: цикл существует тогда и только тогда, когда во время DFS обнаруживается обратная сторона . Это доказано в результате теории белого пути.
источник
На мой взгляд, наиболее понятным алгоритмом обнаружения цикла в ориентированном графе является алгоритм раскраски графа.
По сути, алгоритм раскраски графа обходит граф DFS (поиск в глубину вначале, что означает, что он полностью исследует путь, прежде чем исследовать другой путь). Когда он находит задний край, он помечает график как содержащий цикл.
Для более подробного объяснения алгоритма раскраски графа, пожалуйста, прочитайте эту статью: http://www.geeksforgeeks.org/detect-cycle-direct-graph-using-colors/
Также я предоставляю реализацию раскраски графов в JavaScript https://github.com/dexcodeinc/graph_algorithm.js/blob/master/graph_algorithm.js
источник
Если вы не можете добавить «посещенное» свойство к узлам, используйте набор (или карту) и просто добавьте все посещенные узлы в набор, если они уже не находятся в наборе. Используйте уникальный ключ или адрес объектов в качестве «ключа».
Это также дает вам информацию о «корневом» узле циклической зависимости, которая пригодится, когда пользователь должен будет решить проблему.
Другое решение - попытаться найти следующую зависимость для выполнения. Для этого у вас должен быть какой-то стек, где вы можете вспомнить, где вы сейчас находитесь и что вам нужно делать дальше. Проверьте, есть ли зависимость в этом стеке, прежде чем выполнять ее. Если это так, вы нашли цикл.
Хотя это может показаться сложным O (N * M), вы должны помнить, что стек имеет очень ограниченную глубину (поэтому N мала) и что M становится меньше с каждой зависимостью, которую вы можете отметить как «выполненная» плюс вы можете остановить поиск, когда найдете лист (поэтому вам не нужно проверять каждый узел -> M тоже будет маленьким).
В MetaMake я создал график в виде списка списков, а затем удалял каждый узел, когда выполнял их, что, естественно, сокращало объем поиска. На самом деле мне никогда не приходилось проводить независимую проверку, все это происходило автоматически во время обычного выполнения.
Если вам нужен режим «только тест», просто добавьте флаг «пробного запуска», который отключает выполнение реальных заданий.
источник
Не существует алгоритма, который мог бы найти все циклы в ориентированном графе за полиномиальное время. Предположим, у ориентированного графа есть n узлов, и каждая пара узлов имеет связи друг с другом, что означает, что у вас есть полный граф. Таким образом, любое непустое подмножество этих n узлов указывает цикл, и существует 2 ^ n-1 число таких подмножеств. Так что никакого алгоритма полиномиального времени не существует. Итак, предположим, что у вас есть эффективный (не глупый) алгоритм, который может сообщить вам количество направленных циклов в графе, вы можете сначала найти сильные связанные компоненты, а затем применить свой алгоритм к этим связанным компонентам. Поскольку циклы существуют только внутри компонентов, а не между ними.
источник
Я реализовал эту проблему в SML (императивное программирование). Вот схема. Найдите все узлы, которые имеют степень или степень 0. Такие узлы не могут быть частью цикла (поэтому удалите их). Затем удалите все входящие или исходящие ребра из таких узлов. Рекурсивно применить этот процесс к результирующему графу. Если в конце у вас не осталось ни одного узла или ребра, у графа нет циклов, иначе есть.
источник
То, как я это делаю, - это топологическая сортировка, подсчитывающая количество посещенных вершин. Если это число меньше общего числа вершин в группе обеспечения доступности баз данных, у вас есть цикл.
источник
/mathpro/16393/finding-a-cycle-of-fixed-length Мне нравится это решение лучше всего специально для 4 длины :)
Также физик говорит, что ты должен сделать O (V ^ 2). Я считаю, что нам нужно только O (V) / O (V + E). Если граф подключен, DFS посетит все узлы. Если у графа есть связанные подграфы, то каждый раз, когда мы запускаем DFS на вершине этого подграфа, мы найдем связанные вершины и не будем рассматривать их для следующего запуска DFS. Поэтому возможность запуска для каждой вершины неверна.
источник
Если DFS находит ребро, которое указывает на уже посещенную вершину, у вас есть цикл там.
источник
Как вы сказали, у вас есть набор заданий, его нужно выполнять в определенном порядке.
Topological sort
с учетом необходимого вам порядка для планирования заданий (или для проблем с зависимостями, если это такdirect acyclic graph
). Запуститеdfs
и сохраните список, и начните добавлять узел в начале списка, и если вы встретили узел, который уже посещен. Затем вы нашли цикл в данном графике.источник
Если график удовлетворяет этому свойству
тогда граф содержит хотя бы по циклу.
источник