algorithm - 如何在树中查找循环引用

Question

我有一个树结构，非常像 DOM。
我需要调试它并从循环引用中清除它( child 是 parent 的 parent )。
我记得有一个算法，不记得名字了。
是什么名字。

Answer 1

使用任何方便的算法遍历树；深度优先搜索通常是一个很好的选择。跟踪您访问的每个节点。如果你两次访问一个节点，你有一个潜在的循环，你可以通过删除导致重新访问的节点的链接来打破这个特定的循环。但它可能只是一个连接，使树成为有向无环图 (DAG)。 (见下图。)

如果您接受 DAG 但不接受循环，那么您需要区分这两种情况。最简单的方法是为每个节点维护两个标志而不是一个:visited 和completed。在 DFS 上，您在访问子节点之前将节点标记为已访问，并在访问子节点后标记为已完成。 (如果它是叶子，就给它两个标记。)现在，当你第一次访问一个节点时有三种可能性:

1. 没有标记。不用担心。

2. 访问但未完成:循环

3. 访问并完成:无环金刚石

最后一个案例看起来像这样:

           root
            / \
           /   \
          /     \
          a      b
         / \    / \
        /   \  /   \
       /     \/     \
      c     join     d