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

Question

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

Answer 1

Я бы попытался до sort the graph topologically, и если вы не можете, у вас есть циклы.

Answer 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 

Это timecomplexity O (N + M) или O (N^2)

Answer 3

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

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

Как отмечает Rutger Prins, если ваш график не подключен, вам нужно повторить поиск по каждому подключенному компоненту.

В качестве ссылки Tarjan's strongly connected component algorithm тесно связан. Это также поможет вам найти циклы, а не просто сообщить, существуют ли они.

Answer 4

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

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

Answer 5

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

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

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

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

• при проверке циклов ниже любого заданного узла, просто передать этот узел вместе с пустым HashSet

  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 6

Вот мой рубиновый implem peel off leaf node algorithm.

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 

Answer 7

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

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

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

Answer 8

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

Answer 9

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

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