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

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

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

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

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

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

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

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

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

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

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

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

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

Вы можете использовать инверсию цикла поиска из моего ответа здесь https://stackoverflow.com/a/60196714/1763149

def is_acyclic(graph):
    return not has_cycle(graph)

Вот моя реализация в псевдокоде:

bool Acyclacity_Test
   InitColor() //Sets to WHITE every vertex
   while there is a node v in V:
      if (v.color == WHITE) then
         tmp = Aux_Acy(v);
         if ( not tmp ) return false
   return true
END

bool Aux_Acy(u)
   u.color = GREY
   for each node v in Adj(u)
       if(v.color == GREY) return false
       else if(v.color == WHITE) tmp = Aux_Acy(v)
       if(!tmp) return false;
   u.color = BLACK
   return true
END