Как проверить, является ли ориентированный граф ацикличным?

82

Как проверить, является ли ориентированный граф ацикличным? А как называется алгоритм? Буду признателен за ссылку.

Nes1983
источник
Еще один случай в пользу способа «исправить» неправильные ответы на SO.
Sparr,
2
Так что, ммм, меня больше всего интересует время, необходимое, чтобы его найти. Итак, мне просто нужен абстрактный алгоритм.
nes1983,
вы должны пройти все ребра и проверить все вершины так, чтобы нижняя граница была O (| V | + | E |). DFS и BFS имеют одинаковую сложность, но DFS легче кодировать, если у вас есть рекурсия, так как она управляет стеком за вас ...
ShuggyCoUk,
DFS не такой сложный. Рассмотрим граф с узлами {1 .. N} и ребрами вида {(a, b) | а <б}. Этот график ациклический, и все же DFS будет O (n!)
FryGuy
1
DFS никогда не бывает O (n!). Он посещает каждый узел один раз и каждое ребро не более двух раз. Итак, O (| V | + | E |) или O (n).
Джей Конрод,

Ответы:

95

Я бы попробовал отсортировать граф топологически , а если нет, то у него есть циклы.

FryGuy
источник
2
Как это не было голосов ?? Он линейен по узлам + ребрам, намного превосходит решения O (n ^ 2)!
Loren Pechtel
5
Во многих случаях DFS (см. Ответ Дж. Конрода) может быть проще, особенно если DFS все равно необходимо выполнить. Но, конечно, это зависит от контекста.
sleske
1
Топологическое упорядочение будет в бесконечном цикле, но оно не скажет нам, где происходит цикл ...
Барадвадж Арьясомаяджула
35

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

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

Как указывает Рутгер Принс, если ваш граф не связан, вам нужно повторить поиск для каждого связного компонента.

Для справки : сильно связанный компонентный алгоритм Тарьяна тесно связан. Это также поможет вам найти циклы, а не только сообщить, существуют ли они.

Джей Конрод
источник
2
Кстати: ребро, которое «указывает на узел, уже находящийся в вашем стеке», по понятным причинам в литературе часто называют «задним ребром». И да, это может быть проще, чем топологическая сортировка графа, особенно если вам все равно нужно сделать DFS.
sleske
Чтобы граф был ацикличным, вы говорите, что каждый компонент связности должен содержать узел только с исходящими ребрами. Можете ли вы порекомендовать алгоритм для поиска компонентов связности (в отличие от компонентов «сильной» связности) ориентированного графа для использования в вашем основном алгоритме?
kostmo
@kostmo, если граф имеет более одного связного компонента, то вы не посетите все узлы в своей первой DFS. Следите за узлами, которые вы посетили, и повторяйте алгоритм с непосещенными узлами, пока не достигнете их всех. По сути, именно так работает алгоритм связанных компонентов.
Джей Конрод,
6
Хотя цель этого ответа верна, ответ сбивает с толку при использовании реализации DFS на основе стека: стек, используемый для реализации DFS, не будет содержать правильных элементов для тестирования. Необходимо добавить дополнительный стек в алгоритм, используемый для отслеживания набора узлов-предков.
Теодор Мердок
У меня есть несколько вопросов по поводу вашего ответа. Я разместил их здесь: stackoverflow.com/questions/37582599/…
Ari
14

Лемма 22.11 из книги Introduction to Algorithms(второе издание) утверждает, что:

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

Филипе Мигель Фонсека
источник
1
По сути, это просто сокращенная версия ответа Джея Конрода :-).
sleske
Одна из задач из той же книги, кажется, предполагает наличие | V | временной алгоритм. Ответ здесь: stackoverflow.com/questions/526331/…
Джастин
9

Решение1Алгоритм Кана для проверки цикла . Основная идея: поддерживать очередь, в которую будет добавлен узел с нулевой входной степенью. Затем снимайте узел один за другим, пока очередь не станет пустой. Проверьте, существуют ли внутренние ребра узла.

Решение2 : алгоритм Тарьяна для проверки компонента сильной связности.

Решение 3 : DFS . Используйте целочисленный массив, чтобы пометить текущий статус узла: т.е. 0 - означает, что этот узел ранее не посещался. -1 - означает, что этот узел был посещен, и его дочерние узлы посещаются. 1 - означает, что этот узел был посещен и готово. Итак, если статус узла равен -1 при выполнении DFS, это означает, что должен существовать цикл.

Крис Су
источник
2

Решение, данное ShuggyCoUk, является неполным, поскольку оно может не проверять все узлы.


def isDAG(nodes V):
    while there is an unvisited node v in V:
        bool cycleFound = dfs(v)
        if cyclefound:
            return false
    return true

Это имеет временную сложность O (n + m) или O (n ^ 2)


источник
мой действительно неверен - я удалил его, так что теперь ваш кажется немного
вырванным
3
O (n + m) <= O (n + n) = O (2n), O (2n)! = O (n ^ 2)
Artru
@Artru O (n ^ 2) при использовании матрицы смежности, O (n + m) при использовании списка смежности для представления графа.
0x450
Гм ... m = O(n^2)поскольку у полного графа ровно m=n^2ребер. Так вот O(n+m) = O(n + n^2) = O(n^2).
Alex Reinking
1

Я знаю, что это старая тема, но для будущих искателей вот созданная мной реализация C # (не утверждаю, что она наиболее эффективна!). Он предназначен для использования простого целого числа для идентификации каждого узла. Вы можете украсить это, как хотите, при условии, что ваши хэши объекта узла и равны правильно.

Для очень глубоких графов это может иметь большие накладные расходы, поскольку он создает хэш-набор на каждом узле по глубине (они уничтожаются по ширине).

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

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

    private bool FindCycle(int node, HashSet<int> path)
    {
    
        if (path.Contains(node))
            return true;
    
        var extendedPath = new HashSet<int>(path) {node};
    
        foreach (var child in GetChildren(node))
        {
            if (FindCycle(child, extendedPath))
                return true;
        }
    
        return false;
    }
    
Мэтью
источник
1

При выполнении DFS не должно быть никакого заднего края. Следите за уже посещенными узлами при выполнении DFS, если вы встретите край между текущим узлом и существующим узлом, тогда у графика есть цикл.

Сантош
источник
1

вот быстрый код, чтобы узнать, есть ли у графика циклы:

func isCyclic(G : Dictionary<Int,Array<Int>>,root : Int , var visited : Array<Bool>,var breadCrumb : Array<Bool>)-> Bool
{

    if(breadCrumb[root] == true)
    {
        return true;
    }

    if(visited[root] == true)
    {
        return false;
    }

    visited[root] = true;

    breadCrumb[root] = true;

    if(G[root] != nil)
    {
        for child : Int in G[root]!
        {
            if(isCyclic(G,root : child,visited : visited,breadCrumb : breadCrumb))
            {
                return true;
            }
        }
    }

    breadCrumb[root] = false;
    return false;
}


let G = [0:[1,2,3],1:[4,5,6],2:[3,7,6],3:[5,7,8],5:[2]];

var visited = [false,false,false,false,false,false,false,false,false];
var breadCrumb = [false,false,false,false,false,false,false,false,false];




var isthereCycles = isCyclic(G,root : 0, visited : visited, breadCrumb : breadCrumb)

Идея такая: обычный алгоритм dfs с массивом для отслеживания посещенных узлов и дополнительным массивом, который служит маркером для узлов, которые привели к текущему узлу, так что когда бы мы ни выполняли dfs для узла мы устанавливаем соответствующий ему элемент в массиве маркеров как истинный, так что, когда когда-либо встречался уже посещенный узел, мы проверяли, истинен ли соответствующий ему элемент в массиве маркеров, если он истинен, то это один из узлов, который позволяет cycle), и фокус в том, что всякий раз, когда dfs узла возвращает, мы устанавливаем его соответствующий маркер обратно в false, чтобы, если мы снова посетили его с другого маршрута, нас не обманули.

м. Eldehairy
источник
1

Только что задал этот вопрос в интервью 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);
}
Том Голден
источник
0

Вот моя рубиновая реализация алгоритма отслаивания листового узла .

def detect_cycles(initial_graph, number_of_iterations=-1)
    # If we keep peeling off leaf nodes, one of two things will happen
    # A) We will eventually peel off all nodes: The graph is acyclic.
    # B) We will get to a point where there is no leaf, yet the graph is not empty: The graph is cyclic.
    graph = initial_graph
    iteration = 0
    loop do
        iteration += 1
        if number_of_iterations > 0 && iteration > number_of_iterations
            raise "prevented infinite loop"
        end

        if graph.nodes.empty?
            #puts "the graph is without cycles"
            return false
        end

        leaf_nodes = graph.nodes.select { |node| node.leaving_edges.empty? }

        if leaf_nodes.empty?
            #puts "the graph contain cycles"
            return true
        end

        nodes2 = graph.nodes.reject { |node| leaf_nodes.member?(node) }
        edges2 = graph.edges.reject { |edge| leaf_nodes.member?(edge.destination) }
        graph = Graph.new(nodes2, edges2)
    end
    raise "should not happen"
end
неоней
источник