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

Обычно вместо этого используется поиск в глубину. Я не знаю, легко ли применить BFS.

В DFS остовное дерево строится в порядке посещения. Если посещается предок узла в дереве (т. Е. Создается задний край), то мы обнаруживаем цикл.

См. http://www.cs.nyu.edu/courses/summer04/G22.1170-001/6a-Graphs-More.pdf для более подробного объяснения.

Я считаю, что вам действительно нужен алгоритм топологической сортировки, подобный описанному здесь:

http://en.wikipedia.org/wiki/Topological_sorting

Если у ориентированного графа есть цикл, алгоритм не сработает.

Комментарии / ответы, которые я видел до сих пор, похоже, упускают тот факт, что в направленном графе может быть более одного способа перейти от узла X к узлу Y без какого-либо (направленного ) циклов в графе.

Используйте DFS для поиска, если какой-либо путь циклический

class Node<T> { T value; List<Node<T>> adjacent;  }

class Graph<T>{

    List<Node<T>> nodes;

   public boolean isCyclicRec()
   {

      for (Node<T> node : nodes)
      {
            Set<Node<T>> initPath = new HashSet<>();
            if (isCyclicRec(node, initPath))
            {
              return true;
            }
      }
      return false;
   }

   private boolean isCyclicRec(Node<T> currNode, Set<Node<T>> path)
   {
      if (path.contains(currNode))
      {
        return true;
      }
      else
      {
        path.add(currNode);
        for (Node<T> node : currNode.adjacent)
        {
            if (isCyclicRec(node, path))
            {
                return true;
            }
            else
            {
                path.remove(node);
            }
        }
      }
      return false;
  }

подход: 1
как насчет уровня без назначения для обнаружения цикла. например: рассмотрите приведенный ниже график. A -> (B, C) B-> D D -> (E, F) E, F -> (G) E-> D Когда вы выполняете запуск DFS, назначаете уровень no посещенному узлу (корень A = 0). номер уровня узла = родительский + 1. Итак, A = 0, B = 1, D = 2, F = 3, G = 4, тогда рекурсия достигает D, поэтому E = 3. Не отмечайте уровень для G (G уже уровень, не назначенный, который больше, чем E). Теперь E также имеет преимущество перед D. Таким образом, при выравнивании D должен получить уровень №4. Но D уже имеет назначенный «более низкий уровень». к нему из 2. Таким образом, каждый раз, когда вы пытаетесь назначить номер уровня узлу при выполнении DFS, для которого уже установлен номер более низкого уровня, вы знаете, что у ориентированного графа есть цикл ..

подход2: используйте 3 цвета. белый, серый, черный. закрашивать только белые узлы, белые узлы - в серый при спуске по DFS, окрашивать серые узлы в черный при развертывании рекурсии (обрабатываются все дочерние элементы). если не все дочерние элементы еще обработаны, и вы попали в серый узел, это цикл. например: все белое начало в прямом графике выше. цвета A, B, D, F, G - бело-серые. G - это лист, поэтому все дети изменили цвет от серого до черного. рекурсия разворачивается до F (все дочерние элементы обработаны), раскрасьте его в черный цвет. теперь вы дойдете до D, у D есть необработанные дочерние элементы, поэтому цвет E серый, G уже окрашен в черный цвет, поэтому не спускайтесь дальше. E также имеет край к D, поэтому, продолжая обрабатывать D (D все еще серый), вы обнаруживаете край обратно к D (серый узел), цикл обнаруживается.

Тестирование топологической сортировки по заданному графу приведет вас к решению. Если алгоритм топсортировки, то есть ребра всегда должны быть направлены в одну сторону, не работает, это означает, что в графе есть циклы.

Еще одно простое решение - это метод «отметки и зачистки». По сути, для каждого узла в дереве вы помечаете его как «посещенный», а затем переходите к его дочерним элементам. Если вы когда-нибудь увидите узел с установленным флагом «visted», вы знаете, что существует цикл.

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