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

Question

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

Answer 1

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

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

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

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

Answer 2

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

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

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

Answer 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;
  }

Answer 4

подход: 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, для которого уже задан номер более низкого уровня, вы знаете, что ориентированный граф имеет цикл.

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

Answer 5

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

Answer 6

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

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