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

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

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

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

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

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

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

Solution2:алгоритм Тарьяна для проверки сильного подключенного компонента.

Solution3: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)

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

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

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

• для графа с одним корневым узлом вы отправляете этот узел и пустой hashset
• для графа, имеющего несколько корневых узлов, вы обертываете это в 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 узла возвращается, мы устанавливаем его соответствующий маркер обратно в 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-style ~ 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);
}