Какой алгоритм является наиболее эффективным для обнаружения всех циклов в направленном графе?
У меня есть направленный граф, представляющий расписание заданий, которые должны быть выполнены, причем задание - это узел, а зависимость - ребро. Мне нужно обнаружить ошибочный случай цикла в этом графе, приводящий к циклическим зависимостям.
алгоритм сильно связных компонент Тарьяна имеет временную сложность O(|E| + |V|)
.
Другие алгоритмы см. в разделе Сильно связанные компоненты в Википедии.
Учитывая, что это расписание заданий, я подозреваю, что в какой-то момент вы собираетесь сортировать их в предполагаемом порядке выполнения.
Если это так, то реализация топологической сортировки в любом случае может обнаружить циклы. UNIX tsort
определенно обнаруживает. Я думаю, что, вероятно, более эффективно обнаруживать циклы одновременно с сортировкой, а не на отдельном этапе.
Поэтому вопрос может звучать так: "как мне наиболее эффективно выполнить сортировку", а не "как мне наиболее эффективно обнаружить циклы". На этот вопрос можно ответить "использовать библиотеку", но в противном случае можно воспользоваться следующей статьей Википедии:
есть псевдокод одного алгоритма, и краткое описание другого алгоритма от Tarjan. Оба имеют временную сложность O(|V| + |E|)
.
Начните с ДПП: существует цикл, если, и только если back-краю было обнаружено в ходе DFS. Это доказано в результате Белый-путь про.
Самый простой способ сделать это-do глубине первого обхода (ДПФ) из graph.
Если граф имеет П вершин, Это О(N) алгоритм временная сложность. Поскольку вы, возможно, придется делать ДПФ, начиная с каждой вершины, сложность становится o(п^2)
.
Вы должны поддерживать stack, содержащий все вершины в текущую глубину traversal, с ее первым элементом является корневой узел. Если Вы зашли на элемент, который уже находится в стеке при ДПФ, то у вас есть цикл.
На мой взгляд, наиболее понятный алгоритм обнаружения цикла в ориентированном графе график-раскраски-алгоритм.
В принципе, алгоритм раскраски графа прогулки графа таким образом, поиск в глубину (глубину поиска, что означает, что он полностью исследует пути, прежде чем исследовать другой путь). Когда он находит заднюю кромку, он отмечает граф, содержащий петли.
Подробное объяснение алгоритма раскраски графа, пожалуйста, прочитайте эту статью: 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 я создал граф в виде списка списков, а затем удалял каждый узел по мере их выполнения, что естественным образом сократило объем поиска. Мне никогда не приходилось выполнять независимую проверку, все происходило автоматически во время обычного выполнения.
Если вам нужен режим "только тест", просто добавьте флаг "dry-run", который отключает выполнение реальных заданий.
Согласно Лемме 22.11 из Кормен и др., Introduction в Algorithms (среды CLR):
ориентированный граф G ациклический, если и только если поиск в глубину Г дает никаких задних кромок.
Об этом уже упоминалось в нескольких ответы; вот я'МР предоставляем пример кода на основе главы 22 из среды CLR. Пример диаграммы показана ниже.
Среды CLR' псевдо-код для глубины поиск по первому гласит:
В Примере на рис. 22.4 среды CLR, график состоит из двух деревьев ДПП: одна, состоящая из узлов а, ал, объяснили, и y, и других узлов w и z. Каждое дерево содержит один задний край: один из объяснили до меня, и еще от z z к (само-петля).
Ключ реализации заключается в том, что задняя кромка возникает, когда в ДПП функцию, в то время как итерация по соседям в
О у
, узел сталкивался с посеревшие.
Следующий код Python является адаптацией среды CLR' псевдокод С если
добавлена статья, которая определяет циклы:
в
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)
Обратите внимание, что в этом примере "время" в среды CLR' псевдокод не захватили, потому что мы'повторно только заинтересованы в выявлении циклов. Существует также некоторые шаблонный код для создания списка смежности представление графа списком ребер.
Когда этот скрипт запускается, он выводит следующий результат:
Cycle detected: found a back edge from x to v.
Cycle detected: found a back edge from z to z.
Это именно задней кромки в Примере среды CLR рис. 22.4.
Не существует алгоритма, который может найти все циклы в ориентированном графе за полиномиальное время. Предположим, ориентированный граф имеет n вершин, и каждая пара узлов имеет связи друг с другом, что означает, у вас есть полный граф. Так что любое непустое подмножество из N узлов указывает на цикл и есть 2^Н-1 число таких подмножеств. Так что никакой полиномиальный алгоритм существует. Итак, предположим, у вас есть эффективный (не тупые) алгоритм, который может сказать вам, сколько направленных циклов в графе, вы можете сначала найти сильные компоненты связности, то, применяя свой алгоритм на этих компонент связности. Так как циклы существуют только в компонентах, а не между ними.
Если ДПП находит краю, что указывает на уже посещенных вершин, у вас есть цикл.
Я реализовал эту задачу в СМЛ ( императивное Программирование) . Вот наброски . Найти все узлы, которые имеют indegree или входной блок из 0 . Такие узлы не могут быть частью цикла ( так удалить их ) . Далее удалить все входящие или исходящие ребра из таких узлов. Рекурсивно применить этот процесс на получившийся график. Если в конце вы не остались с какого-либо узла или ребра , то граф не имеет циклов , то он имеет.
https://mathoverflow.net/questions/16393/finding-a-cycle-of-fixed-length мне нравится это решение самое лучшее специально для 4 длины:)
Также мастера уфн говорит Не О(П^2). Я считаю, что нам нужны только o(В)/О(В+Е). Если граф связный, то ДПП будет посетить все узлы. Если график имеет связанных подграфов, то каждый раз, когда мы запускаем DFS на вершину этого подчиненного график мы найдем Соединенных вершин и не должны рассматривать эти для следующего выполнения ДПП. Поэтому возможность выполнения для каждой вершины-это неправильно.
Как вы сказали, у вас есть набор заданий, это необходимо выполнить в определенном порядке. Топологическая сортировка
дал вам требуется заказать для планирования заданий(или за проблемы с зависимостями, если это прямой ациклический граф). Запустить
СДС` и вести список, и начать добавлять узел в начало списка, а если вы столкнулись с узла, который уже посетил. Тогда вы нашли цикла в заданном графе.
Если граф удовлетворяет эту собственность
|e| > |v| - 1
тогда граф содержит, по крайней мере на цикл.