如何在树中检测循环引用? [英] How to detect circular reference in a Tree?

问题描述

我有一个Node类，如下所示:

I have a Node class as follows:

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

我需要按后顺序遍历这棵树，并且我正在使用

I need to traverse this tree in post order and I am using Guava TreeTraverser for for the same.

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

treeTraverser.postOrderTraversal(node);

要注意的是，给定的树有可能具有循环依赖关系(意味着它可以是循环图).什么是检测循环依赖的有效方法?

The catch is that there chances that the given tree could have circular dependencies(means it could be a cyclic graph). What would be an efficient way to detect circular dependencies?

推荐答案

根据定义，树是 acyclic 连通图.因此，没有像树那样具有循环依赖性的东西.

By definition, a tree is an acyclic connected graph. Therefore, there is no such thing as a tree with circular dependencies.

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

You can find cycles in a graph by applying depth-first traversal, and looking for nodes that have been visited the way down. If you visit a node that you have seen during prior steps of DFS, the graph is not a tree.

有关高级循环检测算法，请参见问题与解答.

See this Q&A for advanced cycle detection algorithms.

这篇关于如何在树中检测循环引用?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！