26

我们如何检测有向图是否是循环的？我想使用广度优先搜索，但我不确定。有任何想法吗？

4

6 回答 6

16

我相信你真正需要的是一种拓扑排序算法，就像这里描述的那样：

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

如果有向图有环，则算法将失败。

到目前为止，我看到的评论/回复似乎忽略了这样一个事实，即在有向图中，从节点 X 到节点 Y 的方式可能不止一种，而图中没有任何（有向）循环。

于 2010-03-29T17:11:22.903 回答
13

通常使用深度优先搜索来代替。我不知道 BFS 是否容易适用。

在DFS中，按访问顺序构建生成树。如果访问了树中节点的祖先（即创建了后边），则我们检测到一个循环。

有关更详细的说明，请参阅http://www.cs.nyu.edu/courses/summer04/G22.1170-001/6a-Graphs-More.pdf 。

于 2010-03-26T17:25:37.447 回答
2

使用 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;
  }
于 2014-08-15T00:43:45.047 回答
1

方法：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 的边（一个灰色节点），一个循环被检测到。

于 2012-04-06T21:19:49.230 回答
0

在给定图上测试拓扑排序将引导您找到解决方案。如果 topsort 的算法，即边应该总是以一种方式定向失败，那么这意味着图包含循环。

于 2013-12-11T01:51:21.653 回答
-1

另一个简单的解决方案是标记和扫描方法。基本上，对于树中的每个节点，您将其标记为“已访问”，然后转到它的子节点。如果您曾经看到设置了“visted”标志的节点，您就会知道这是一个循环。

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

于 2010-03-26T17:40:28.880 回答