Как проверить, является ли ориентированный граф ацикличным? А как называется алгоритм? Буду признателен за ссылку.
82
Как проверить, является ли ориентированный граф ацикличным? А как называется алгоритм? Буду признателен за ссылку.
Ответы:
Я бы попробовал отсортировать граф топологически , а если нет, то у него есть циклы.
источник
Делая простой в глубину-поиска является не достаточно хорош , чтобы найти цикл. В DFS можно посещать узел несколько раз без цикла. В зависимости от того, с чего вы начали, вы также можете не просмотреть весь график.
Проверить наличие циклов в связном компоненте графа можно следующим образом. Найдите узел, у которого есть только выходящие ребра. Если такого узла нет, значит, есть цикл. Запустите DFS на этом узле. При обходе каждого ребра проверьте, указывает ли оно назад на узел, уже находящийся в вашем стеке. Это указывает на наличие цикла. Если такого ребра нет, значит, в этом связном компоненте нет циклов.
Как указывает Рутгер Принс, если ваш граф не связан, вам нужно повторить поиск для каждого связного компонента.
Для справки : сильно связанный компонентный алгоритм Тарьяна тесно связан. Это также поможет вам найти циклы, а не только сообщить, существуют ли они.
источник
Лемма 22.11 из книги
Introduction to Algorithms
(второе издание) утверждает, что:источник
Решение1:Алгоритм Кана для проверки цикла . Основная идея: поддерживать очередь, в которую будет добавлен узел с нулевой входной степенью. Затем снимайте узел один за другим, пока очередь не станет пустой. Проверьте, существуют ли внутренние ребра узла.
Решение2 : алгоритм Тарьяна для проверки компонента сильной связности.
Решение 3 : DFS . Используйте целочисленный массив, чтобы пометить текущий статус узла: т.е. 0 - означает, что этот узел ранее не посещался. -1 - означает, что этот узел был посещен, и его дочерние узлы посещаются. 1 - означает, что этот узел был посещен и готово. Итак, если статус узла равен -1 при выполнении DFS, это означает, что должен существовать цикл.
источник
Решение, данное ShuggyCoUk, является неполным, поскольку оно может не проверять все узлы.
Это имеет временную сложность O (n + m) или O (n ^ 2)
источник
m = O(n^2)
поскольку у полного графа ровноm=n^2
ребер. Так вотO(n+m) = O(n + n^2) = O(n^2)
.Я знаю, что это старая тема, но для будущих искателей вот созданная мной реализация C # (не утверждаю, что она наиболее эффективна!). Он предназначен для использования простого целого числа для идентификации каждого узла. Вы можете украсить это, как хотите, при условии, что ваши хэши объекта узла и равны правильно.
Для очень глубоких графов это может иметь большие накладные расходы, поскольку он создает хэш-набор на каждом узле по глубине (они уничтожаются по ширине).
Вы вводите узел, из которого хотите выполнить поиск, и путь к этому узлу.
При проверке циклов ниже любого заданного узла просто передайте этот узел вместе с пустым хеш-набором
источник
При выполнении DFS не должно быть никакого заднего края. Следите за уже посещенными узлами при выполнении DFS, если вы встретите край между текущим узлом и существующим узлом, тогда у графика есть цикл.
источник
вот быстрый код, чтобы узнать, есть ли у графика циклы:
Идея такая: обычный алгоритм dfs с массивом для отслеживания посещенных узлов и дополнительным массивом, который служит маркером для узлов, которые привели к текущему узлу, так что когда бы мы ни выполняли dfs для узла мы устанавливаем соответствующий ему элемент в массиве маркеров как истинный, так что, когда когда-либо встречался уже посещенный узел, мы проверяли, истинен ли соответствующий ему элемент в массиве маркеров, если он истинен, то это один из узлов, который позволяет cycle), и фокус в том, что всякий раз, когда dfs узла возвращает, мы устанавливаем его соответствующий маркер обратно в false, чтобы, если мы снова посетили его с другого маршрута, нас не обманули.
источник
Только что задал этот вопрос в интервью Google.
Топологическая сортировка
Вы можете попытаться отсортировать топологически, то есть O (V + E), где V - количество вершин, а E - количество ребер. Ориентированный граф ацикличен тогда и только тогда, когда это возможно.
Рекурсивное удаление листа
Рекурсивно удаляют листовые узлы до тех пор, пока не останется ни одного узла, и если осталось более одного узла, у вас будет цикл. Если я не ошибаюсь, это O (V ^ 2 + VE).
DFS-стиль ~ O (n + m)
Однако эффективный алгоритм DFS в худшем случае O (V + E):
function isAcyclic (root) { const previous = new Set(); function DFS (node) { previous.add(node); let isAcyclic = true; for (let child of children) { if (previous.has(node) || DFS(child)) { isAcyclic = false; break; } } previous.delete(node); return isAcyclic; } return DFS(root); }
источник
Вот моя рубиновая реализация алгоритма отслаивания листового узла .
источник
Вы можете использовать инверсию цикла поиска из моего ответа здесь https://stackoverflow.com/a/60196714/1763149
def is_acyclic(graph): return not has_cycle(graph)
источник