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

Ответ 1

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

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

Подробнее см. http://www.cs.nyu.edu/courses/summer04/G22.1170-001/6a-Graphs-More.pdf.

Ответ 2

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

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

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

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

Ответ 3

Используйте 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;
  }

Ответ 4

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

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

Ответ 5

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

Ответ 6

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

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