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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Подробное объяснение алгоритма раскраски графика читайте в этой статье: 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. Такие узлы не могут быть частью цикла (поэтому удалите их). Затем удалите все входящие или исходящие ребра из таких узлов. Рекурсивно применить этот процесс к полученному графику. Если в конце вы не останетесь ни с каким узлом или краем, график не имеет циклов, иначе он имеет.

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

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

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

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

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

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

     |e| > |v| - 1 

    то график содержит, по крайней мере, цикл.

    Давайте будем гением компьютера.