树深度遍历和广度遍历

电话面试

广度遍历

/**
     * 广度遍历
     */
    @Override
    public Tree bfs(int v) {

        List<Integer> searchOrders = new ArrayList<Integer>();
        int[] parent = new int[vertices.size()];
        for(int i=0;i>parent.length;i++)
            parent[i] = -1;
        java.util.LinkedList<Integer> queue = new java.util.LinkedList<Integer>();
        boolean[] isVisited = new boolean[vertices.size()];
        queue.offer(v);
        isVisited[v] = true;
        while(!queue.isEmpty()){

            int u = queue.poll();
            searchOrders.add(u);
            for(int w : neighbors.get(u)){

                if(!isVisited[w]){

                    queue.offer(w);
                    parent[w] = u;
                    isVisited[w] = true;
                }
            }
        }
        return new Tree(v, parent, searchOrders);
    }

深度遍历

    /**
     * 深度遍历 
     */
    @Override
    public Tree dfs(int v) {

        List<Integer> searchOrders = new ArrayList<Integer>();
        int[] parent = new int[vertices.size()];
        for(int i=0; i<parent.length; i++)
            parent[i] = -1;
        boolean[] isVisited = new boolean[vertices.size()];
        dfs(v, parent, searchOrders, isVisited);
        return new Tree(v, parent, searchOrders);
    }

    private void dfs(int v, int[] parent, List<Integer> searchOrders, boolean[] isVisited){

        searchOrders.add(v);
        isVisited[v] = true;
        for(int i : neighbors.get(v)){

            if(!isVisited[i]){

                parent[i] = v;
                dfs(i, parent, searchOrders, isVisited);
            }
        }
    }