如何检测树中的循环引用？

Question

我有一个Node类如下:

public class Node{
    Object data;
    List<Node> children;
}

我需要按照邮政顺序遍历这棵树,并且我使用的是Guava TreeTraverser.

    TreeTraverser<Node> treeTraverser = new TreeTraverser<Node>() {
                @Override
                public Iterable<Node> children(Node node) {
                    return node.children;
                }
            };

treeTraverser.postOrderTraversal(node);

问题在于,给定树可能具有循环依赖性(意味着它可能是循环图).什么是检测循环依赖的有效方法？

Answer 1

根据定义,树是非循环连接图.因此,没有具有循环依赖性的树.

您可以通过应用深度优先遍历并查找已经访问过的节点来查找图形中的循环.如果您访问在DFS的先前步骤中看到的节点,则该图形不是树.

有关高级循环检测算法,请参阅此问答.