data-structures - 如何验证树中是否有圆圈？

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 个指针找到圆圈并以不同的间隔推进它们。最终，指针将匹配，指示循环，或者“更快”的指针将到达然后结束。这个问题通常被问到链表，而不是树。