代码之家  ›  专栏  ›  技术社区  ›  vatsal mevada

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

  •  5
  • vatsal mevada  · 技术社区  · 10 年前

    我有一个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);
    

    问题是给定的树可能有循环依赖关系(意味着它可能是循环图)。什么是检测循环依赖的有效方法?

    2 回复  |  直到 10 年前
        1
  •  16
  •   Community Mohan Dere    9 年前

    根据定义,树是 acyclic 连通图。因此,不存在具有循环依赖关系的树。

    通过应用深度优先遍历并查找向下访问过的节点,可以在图中找到循环。如果访问在DFS的前面步骤中看到的节点,则该图为 不 一棵树。

    看看这个 Q&A 用于高级循环检测算法。

        2
  •  3
  •   nits.kk    10 年前

    简单地说 Tree is a non cyclic data structure 当有循环时,它就会变成 Graph .

    enter image description here

    上面是一个图形示例。您可以使用邻接列表或邻接矩阵表示它。你可以参考 http://krishnalearnings.blogspot.in/2015/11/basics-of-graph-in-computer-science.html 了解图形基础知识。

    在上面的图片中,我们可以将其表示如下(在您的问题中,您使用了一种邻接列表表示法)。

    int[][] graph = {   {0,1,0,0,0,0},
                        {0,0,1,0,0,0},
                        {0,0,0,1,1,0},
                        {0,0,0,0,0,0},
                        {0,0,0,0,0,1},
                        {0,1,0,0,0,0},
                    };
    

    1表示从相应的行编号顶点到列编号顶点的边。

    我们可以编写一个简单的方法来检测循环的存在,也可以打印图形中的任何一个循环。

    static int[] cycleElements;
    static int cycleElementIndex = 0;
    static boolean cycleFound = false;
    static final int NEW = 0;
    static final int PUSHED = 1;
    static final int POPPED = 2;
    public static int findCycle(int[][] graph,int N, int u, int[] states){
        for(int v = 0; v < N; v++){
            if(graph[u][v] == 1){
                if(states[v] == PUSHED){
                    // cycle found
                    cycleFound = true;
                    return v;
                }else if(states[v] == NEW){
                    states[v] = PUSHED;
                    int poppedVertex = findCycle(graph, N, v, states);
                    states[v] = POPPED;
                    if(cycleFound){
                        if(poppedVertex == u){
                            cycleElements[cycleElementIndex++] = v;
                            cycleElements[cycleElementIndex++] = u;
                            cycleFound = false;
                        }else{
                            cycleElements[cycleElementIndex++] = v;
                            return poppedVertex;
                        }
                    }
                }
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        int N = 6;
        int[][] graph = {   {0,1,0,0,0,0},
                            {0,0,1,0,0,0},
                            {0,0,0,1,1,0},
                            {0,0,0,0,0,0},
                            {0,0,0,0,0,1},
                            {0,1,0,0,0,0},
                        };
        cycleElements = new int[N];
        int[] states = new int[N];
        states[0] = PUSHED;
        findCycle(graph,N,0,states);
        for(int i = 0; i < cycleElementIndex; i++){
            System.out.println(cycleElements[i]);
        }
    }
    

    如果愿意的话,可以很容易地将上述方法转换为邻接列表,尽管表示并不重要(与邻接矩阵相比,只有邻接列表可以节省空间)

    推荐文章