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

Question

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

Answer 1

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

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

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

Answer 2

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

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

Answer 3

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

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

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

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

Answer 4

подход: 1
как насчет уровня нет назначения для обнаружения цикла. например: рассмотрим график ниже. A -> (B, C) B-> D D -> (E, F) E, F -> (G) E-> D Как вы запускаете DFS, назначая уровень no узлу, который вы посещаете (root A = 0). level no узла = 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. Таким образом, в любое время, когда вы пытаетесь присвоить номер уровня узлу при выполнении 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

Использование 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; 
    }