如何检测有向图是否有环？

Question

如何检测有向图是否包含环？我考虑使用宽度优先搜索，但不确定。您有什么想法吗？

- iva123

---

可能是重复的问题：如何检查有向图是否为无环图？ - Ciro Santilli OurBigBook.com

我刚在相关的StackOverflow帖子上发布了一个Scala通用FP解决方案：https://dev59.com/ZVvUa4cB1Zd3GeqPrThg#36144158 - chaotic3quilibrium

请查看我的答案：https://dev59.com/G7joa4cB1Zd3GeqPDr_a#60196714 - Marcin Raczyński

Answer 1

我相信您真正需要的是像这里描述的拓扑排序算法：

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

如果有一个循环图，则该算法将失败。

迄今为止我看到的评论/回复似乎忽略了一个事实，在一个定向图中，可能会有多种方法从节点X到达节点Y，而不会在图中存在任何（定向）循环。

- Peter

Answer 2

通常使用深度优先搜索，而不是广度优先搜索。在DFS中，按访问顺序构建生成树。如果访问了节点的祖先（即创建了一条反向边），那么我们就检测到了一个环。请参阅http://www.cs.nyu.edu/courses/summer04/G22.1170-001/6a-Graphs-More.pdf以获取更详细的解释。

- kennytm

---

BFS或DFS在这个问题上具有相同的复杂度（运行时间）和适用性（相同的结果）。唯一不同的是节点的访问顺序。 - darlinton

在链接页面上最后一句话是基于边和顶点数量的拓扑语句：“如果图G没有循环，则可能的最大边数为|V|-1。”这适用于无向图，但不适用于有向图，正如原始问题中所指示的那样。对于有向图，“钻石继承”图提供了一个反例（4个节点和4条边构成了一个“环”，但不是可以通过跟随箭头遍历的“循环”）。 - Peter

如果上一个评论不够清晰，我的意思是：对于无向图，被接受的答案已足够，但对于有向图（正如问题所指定的），该答案是错误的。 - Peter

@Peter：之前的链接可能是错误的，但是我描述的概念即使是针对有向图也是正确的。我已经把术语阐述得更清晰，并提供了更好的来源。 - kennytm

@darlinton：但是使用BFS做这件事有些过度，因为同样的事情可以通过更简单的DFS实现。 - Lazer

引用：CLRS算法导论第三版604-610页。 - Nathan

Answer 3

使用深度优先搜索来查找是否存在环形路径。

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

- Abhijeet Kushe

---

你根本没有定义函数isCyclic。 - Hopeful Llama

这段代码在输入4 -> 1->2->3时失败了。如果从节点1开始进行探索，它会出错。 - Sayat Satybald

找到了解决方法：Set<Node<T>> initPath = new HashSet<>(); 应该放在for循环内部。 - Sayat Satybald

Answer 4

方法：1
如何使用无分配级别来检测循环。例如：考虑下面的图形。A->(B,C) B->D D->(E,F) E,F->(G) E->D 当您执行DFS并访问节点时（根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（一个灰色节点）的边，这就是一个环。

- Abhishek

Answer 5

测试给定图的拓扑排序将引导您找到解决方案。如果拓扑排序算法，即边应始终单向指向的规则失败，则意味着该图包含循环。

- kdperspective

Answer 6

另一个简单的解决方案是标记-清除法。基本上，对于树中的每个节点，您将其标记为“已访问”，然后继续移动到其子节点。如果您看到一个带有“已访问”标志的节点，则知道存在循环。

如果无法修改图以包括“已访问”位，则可以改用一组节点指针。要将节点标记为已访问，请将指向它的指针放入集合中。如果指针已经在集合中，则存在循环。

- Rakis

---

这个解决方案与KennyTM提供的类似，但对于这个问题来说更好。问题是要识别循环，因此标记-清除是一个很好的方法。像KennyTM建议的那样构建生成树是一种更复杂的解决问题的方式，因为你使用了生成树的概念。最终，它几乎都是相同的。 - darlinton

@Rakis：它会把 http://en.wikipedia.org/wiki/File:Diamond_inheritance.svg 错误地识别为一个循环吗？ - kennytm

@KennyTM：是的，会的。而且无论你使用深度优先搜索还是广度优先搜索来探索图中的节点，你都会得到相同的错误答案。仅仅跟踪已访问的节点不足以识别循环。因此，我会扣除Rakis的回答一分（但我的声望太微薄了，无法这样做）。 - Peter

啊，确实是这样。我想我当时考虑的是树而不是实际的图。然而，我相信在那种情况下仍然可以使用相同的一般方法，通过跟踪访问的边缘而不是访问的节点。使用一组（from_node_id，to_node_id）对将检测到多次穿越相同的边缘。 - Rakis

正确的解决方案包含标记-清除算法，但需要三种颜色。将未访问的节点标记为白色，正在访问的节点标记为灰色，以及根据完全访问子图确定的节点标记为黑色。请参阅http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm。 - Nathan