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

StackOverflow https://stackoverflow.com/questions/583876

Вопрос

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

Это было полезно?

Решение

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

Другие советы

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

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

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

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

Лемма 22.11 о книге Introduction to Algorithms (Второе издание) гласит:

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

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

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

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

Решение, предоставленное 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)

Я знаю, что это старая тема, но для будущих поисковиков я создал реализацию 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;
}

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

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

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 для узла, мы устанавливаем его соответствующий элемент в Маркерный массив как истинный, так что когда когда -либо встречается уже посещаемый узел, мы проверяем, является ли его соответствующий элемент в массиве маркеров правдой, если он правда, то его один из узлов, которые позволяют себе (отсюда и цикл) и хитрость Когда возвращается DFS узела, мы устанавливаем его соответствующий маркер обратно на False, так что, если мы посетили его снова по другому маршруту, мы не одурачим.

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

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

Только что задал этот вопрос в интервью 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);
}
Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top