java - 如何阻止迭代器跳过第一个输入的值？

Question

我正在尝试打印我的“图”程序的深度优先遍历。 DepthFirstTraversal(int v) 方法应该从第一个索引开始，该索引应该是 A。但是，它似乎跳过了这一点。 有什么建议吗？

我尝试将值 v 从 1 更改为 0，但这只是在同一代码之上打印了一个额外的 0。

    import java.util.Arrays;
    import java.util.Iterator;

    public class Graph {
        private boolean[][] edges;
        private int[] labels;
        private int N; //number of vertices;

        //constructor. This constructor will create a matrix of size n by n.
        public Graph(int n) {
            N=n;
            edges = new boolean[n][n];
            labels = new int[n];
        }

        //this method will allow user to add an edge
        public void addEdge(int source, int target) {
            edges[source][target] = true;
        }

        //this method will return the label of the vertex
        public int getLabel(int vertex) {
            return labels[vertex];
        }

        //this method will allow user to remove an edge
        public void removeEdge(int source, int target) {
            edges[source][target] = false;
        }

        //this method will allow user to set a label
        public void setLabels(int vertex, int newLabel) {
            labels[vertex] = newLabel;
        }

        //this method will return the size of the labels array
        public int size() {
            return labels.length;
        }

        //this method will grab the neighbors of the desired vertex
        public int[] neighbors(int vertex) {
            int i;
            int counter = 0;
            int[] result;

            for (i = 0; i < labels.length; i++) {
                if (edges[vertex][i])
                    counter++;
            }
            result = new int[counter];
            counter = 0;
            for (i = 0; i < labels.length; i++) {
                result[counter++] = i;
            }
            return result;
        }

        //this method will print out the vertices starting from the first value
        I tried fixing my code a little, but I ran into another problem.
I do have to use neighbors method and also I cannot use recursion.

public void DepthFirstTraversal(int v) {
        boolean[] visited = new boolean[N];
        Stack<Integer> stack = new Stack<>();
        stack.add(v);

        visited[v]=true;
        while(!stack.isEmpty()){
            int i = stack.pop();
            if (i == 1) {
                System.out.print("A" + "-");
            } else if (i == 2) {
                System.out.print("B" + "-");
            } else if (i == 3) {
                System.out.print("C" + "-");
            } else if (i == 4) {
                System.out.print("D" + "-");
            } else if (i == 5) {
                System.out.print("E" + "-");
            } else if (i == 6) {
                System.out.print("F" + "-");
            } else if (i == 7) {
                System.out.print("G" + "-");
            } else if (i == 8) {
                System.out.print("H" + "-");
            } else if (i == 9) {
                System.out.print("I" + "-");
            }
            System.out.print(labels[i] + " \n");

            int[] neighborsOfI = neighbors(i);
            for(int k=0;k<neighborsOfI.length;k++){
                int neighborTest = neighborsOfI[k];
                if(!visited[neighborTest]){
                    stack.add(neighborTest);
                    visited[neighborTest]=true;
                }
            }
        }
    }
}

public class graphDemo {
    public static void main(String args[]){
        Graph graph = new Graph(10);
        graph.addEdge(1,1);
        graph.addEdge(2,3);
        graph.addEdge(3,5);
        graph.addEdge(4,7);
        graph.addEdge(5,9);
        graph.addEdge(6,2);
        graph.addEdge(7,3);
        graph.addEdge(8,5);
        graph.addEdge(9,8);

        graph.setLabels(1,9);
        graph.setLabels(2,3);
        graph.setLabels(3,5);
        graph.setLabels(4,7);
        graph.setLabels(5,4);
        graph.setLabels(6,8);
        graph.setLabels(7,6);
        graph.setLabels(8,2);
        graph.setLabels(9,1);

        System.out.println("Depth First Traversal from first value: \n");
        graph.DepthFirstTraversal(1);

    }
}

我期望深度优先遍历从 A 开始并遵循深度优先遍历直到图中的最后一个元素，但我输出的是:

从第一个值开始深度优先遍历:

A-1 I-9

Answer 1

Java 是 0 索引的，这意味着数组从索引 0 开始。您创建了一个大小为 10 的数组，但使用了后 9 个条目。我更改了您的输入数据以匹配此数据，但这不是问题。

public class GraphDemo {
    public static void main(String args[]) {
        Graph graph = new Graph(9);
        graph.addEdge(0, 0);
        graph.addEdge(1, 2);
        graph.addEdge(2, 4);
        graph.addEdge(3, 6);
        graph.addEdge(4, 8);
        graph.addEdge(5, 1);
        graph.addEdge(6, 2);
        graph.addEdge(7, 4);
        graph.addEdge(8, 7);

        graph.setLabels(0,9);
        graph.setLabels(1,3);
        graph.setLabels(2,5);
        graph.setLabels(3,7);
        graph.setLabels(4,4);
        graph.setLabels(5,8);
        graph.setLabels(6,6);
        graph.setLabels(7,2);
        graph.setLabels(8,1);

        System.out.println("Depth First Traversal from first value: \n");
        graph.depthFirstTraversal(1);

    }
}

我不确定标签是什么或意味着什么，所以我完全忽略了它们以及迭代这些标签的邻居。这是两种方式的深度优先遍历:

    private void depthFirstTraversal(int v, boolean[] visitedIndexes) {
        if (visitedIndexes[v]) {
            System.out.println("Arrived at index " + v +
                    " with letter " + (char) ('A' + v) +
                    " but we've already been here, so skipping this.");
            return;
        }

        System.out.println("Traversing index " + v +
                " which has label " + labels[v] +
                " and here's some letter " + (char) ('A' + v)
        );
        visitedIndexes[v] = true;

        for (int i = 0; i < n; i++) {
            if (edges[v][i]) {
                depthFirstTraversal(i, visitedIndexes);
            }
        }
    }