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

Question

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

Answer 1

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

Answer 2

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

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

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

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

Answer 3

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

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

Answer 4

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

Решение2 : Алгоритм Тарьяна для проверки Сильно подключенного компонента.

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

Answer 5

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

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, поэтому, если мы посетим его снова с другого маршрута, мы не будем обмануты.

Answer 6

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

Answer 7

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

Answer 8

Решение, данное 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)

Answer 9

Только что задал этот вопрос в интервью Google.

Топологическая сортировка

Вы можете попытаться отсортировать топологически, а это O (V + E), где V - количество вершин, а E - количество ребер. Ориентированный граф ацикличен тогда и только тогда, когда это возможно.

Рекурсивное удаление листьев

Рекурсивно удаляйте конечные узлы, пока не останется ни одного, и если осталось более одного узла, у вас будет цикл. Если я не ошибаюсь, это O (V ^ 2 + VE).

DFS-стиль ~ O (n + m)

Однако эффективный алгоритм DFS-esque, наихудший случай 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);
}

Answer 10

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

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