如何验证树中是否存在圆？

Question

这是一棵树：

1. 将会有一个根。

2. 每个树节点有零个或多个子节点。

3. 允许两个节点指向同一个子节点。比如说，两个节点 A 节点 B 具有子节点 C。

但是，禁止以下行为：

节点A是节点B的后代，而节点B是节点A的后代。

一种禁止的情况是

节点 A 有一个子节点 C 和节点 D，

节点C和D都有一个子节点E，

节点 E 有 A 的子节点。

问题是，如何最快的确定这个圆呢？

更新:我意识到这是在有向图中找到任何循环。刚才我想出了一个类似于Tarjan算法的解决方案。

感谢您的评论。

Answer 1

做一个 深度优先搜索 穿过树。如果在任何时候您发现回溯堆栈中已经存在一个节点，那么就会出现一个圆圈。

Answer 2

可以使用 2 个指针并以不同的间隔前进来找到圆圈。最终，指针将匹配，指示循环，或者“更快”的指针将到达然后结束。不过，这个问题通常是针对链表而不是树提出的。