我有一个树结构,非常像 DOM。
我需要调试它并从循环引用中清除它( child 是 parent 的 parent )。
我记得有一个算法,不记得名字了。
是什么名字。
最佳答案
使用任何方便的算法遍历树;深度优先搜索通常是一个很好的选择。跟踪您访问的每个节点。如果你两次访问一个节点,你有一个潜在的循环,你可以通过删除导致重新访问的节点的链接来打破这个特定的循环。但它可能只是一个连接,使树成为有向无环图 (DAG)。 (见下图。)
如果您接受 DAG 但不接受循环,那么您需要区分这两种情况。最简单的方法是为每个节点维护两个标志而不是一个:visited
和completed
。在 DFS 上,您在访问子节点之前将节点标记为已访问,并在访问子节点后标记为已完成。 (如果它是叶子,就给它两个标记。)现在,当你第一次访问一个节点时有三种可能性:
没有标记。不用担心。
访问但未完成:循环
访问并完成:无环金刚石
最后一个案例看起来像这样:
root
/ \
/ \
/ \
a b
/ \ / \
/ \ / \
/ \/ \
c join d
关于algorithm - 如何在树中查找循环引用,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28502403/