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

发布于 2024-08-26 08:00:51 字数 47 浏览 8 评论 0原文

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

夏夜暖风 2024-09-02 08:00:51

我相信，您真正需要的是一种拓扑排序算法，如下所述：

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

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

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

回复收藏 0 原文

浪漫人生路 2024-09-02 08:00:51

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

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

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

回复收藏 0 原文

北城挽邺 2024-09-02 08:00:51

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

Use DFS to search if any path is cyclic

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

回复收藏 0 原文

古镇旧梦 2024-09-02 08:00:51

方法：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时尝试为节点分配级别编号时，你都知道有向图有一个循环..

方法2：
使用 3 种颜色。白色、灰色、黑色。仅将白色节点着色为白色节点，当您沿着 DFS 向下时将白色节点着色为灰色，当递归展开时将灰色节点着色为黑色（所有子节点均已处理）。如果尚未处理所有子节点并且您遇到灰色节点，那就是一个循环。
例如：在上面的直接图中开始全白色。
颜色 A、B、D、F、G 为白灰色。 G 是叶子，所以所有孩子都将其颜色处理为灰色到黑色。递归展开到 F（所有子进程都已处理），将其涂成黑色。现在你到达D，D有未处理的孩子，所以E颜色为灰色，G已经颜色为黑色，所以不要再往下走。 E 也有到 D 的边，所以当仍在处理 D（D 仍然是灰色）时，您会发现一条回到 D（灰色节点）的边，检测到循环。

回复收藏 0 原文