为什么下面的代码 return A、AEC、AEBCD 没有？

Question

我有一个深度受限搜索算法，我在一个循环中多次运行这样该算法就可以像迭代深化搜索算法一样工作，为什么代码 return 只有当我显式调用该方法而不是当我在循环中调用它时才得到期望的结果。

public class DepthLimited {

public static void main(String[] args) {
    Graph graph = new Graph();
    graph.addNode('A');    // Since A is the first vertex so it takes the index 0  
    graph.addNode('E');    // B is the second one so it takes index 1
    graph.addNode('B');    // index 2
    graph.addNode('C');    // index 3
    graph.addNode('D');    // index 4

    graph.addEdge(0, 1);     // This indicates the relation between the vertices A and E
    graph.addEdge(1, 2);     // This indicates the relation between the vertices E and B
    graph.addEdge(0, 3);     // This indicates the relation between the vertices A and C
    graph.addEdge(3, 4);     // This indicates the relation between the vertices C and D

 //        System.out.print("Sequence: ");
 //        graph.dls(2);
 //        System.out.println("");

    graph.dls(2); // produces AEBCD when called like this, before any other similar calls i.e graph.dls(1)

    for (int i = 0; i <= 2; i++) {
        graph.dls(i);  // when i is 2 the method only returns A instead of AEBCD
        System.out.println("");
    }
}
}

这是我的图表 class:

public class Graph {

private final int MAX_NODES = 20;      //maximum number of nodes
private Node[] listOfNodes;        // list of nodes
private int neighbourMatrix[][];      // every node with its children
private int noOfNodes;              // current number of nodes
private Stack stack;

private int depth = 0;


public Graph() {
    listOfNodes = new Node[MAX_NODES];
    neighbourMatrix = new int[MAX_NODES][MAX_NODES];
    stack = new Stack();
}

public void addNode(char name) {
    listOfNodes[noOfNodes++] = new Node(name);        //create a new node and add it to the array of nodes
}

public void addEdge(int start, int end) {                //creates a bidirectional relation between
    neighbourMatrix[start][end] = 1;                     //the two nodes (start and end)
    neighbourMatrix[end][start] = 1;                     // 1 is used to indicate the existence of a relation between
}                                                        //two node because by default neighbourMatrix contains only 0s.

public void display(int node) {
    System.out.print(listOfNodes[node].name);          //prints the name of a node
}

public void dls(int limit) {                                 // begin at node 0 which is the root of the tree

    listOfNodes[0].checked = true;  // mark it
    display(0);                 // display it
    stack.push(0);                 // push it to the stack
    depth++;

    while (!stack.isEmpty()) // until stack empty,
    {
        int node = getUnvisitedChild(stack.peek());
        if (depth <= limit) {
            // get an unvisited child of the node that is at the top of the stack

            if (node == -1) // if the node had no unvisited child, then pop the node from the stack
            {
                stack.pop();
                depth--;
            } else // if the node has unvisited child         
            {
                listOfNodes[node].checked = true;  // mark it
                display(node);                 // display it
                stack.push(node);                 // push it to the stack
                depth++;
            }
        } else {
            stack.pop();
            depth--;
        }
    }
}

public int getUnvisitedChild(int v) // returns an unvisited child of the node v 
{
    for (int j = 0; j < noOfNodes; j++) {
        if (neighbourMatrix[v][j] == 1 && listOfNodes[j].checked == false) {
            return j;               //returns the index of the child
        }
    }
    return -1;              //otherwise it returns -1
}
}

Answer 1

原因有两个。

首先，在调用 dls(int limit) 之后，每个访问过的 Node 的 checked 值都设置为 true，并且在后续对该方法的调用中将保持不变。您首先需要将它们设置为将 checked 设置回 false。

其次，depth 是 class 成员 variable/field，并且不会每次都重置为 0。该变量应该是方法的局部变量。

我建议您不要将它们是否被访问存储为 Node 的属性，而是引入本地 Set（例如 HashSet ) 存储访问过的节点；或者在您的情况下，整数值表示已访问 Node 对象的索引。

例如，快速破解您的解决方案：

public void dls(int limit) {
    Set<Integer> visited = new HashSet<>();
    int start = 0;
    stack.push(start);
    display(start);
    int depth = 1;
    while (!stack.isEmpty()) {
        int current = stack.peek();
        visited.add(current);
        int next = -1;
        for (int adj = 0; adj < noOfNodes; adj++) {
            if (neighbourMatrix[current][adj] == 1 && !visited.contains(adj)) {
                next = adj;
            }
        }
        if (depth <= limit) {
            if (next == -1) {
                stack.pop();
                depth--;
            } else {
                stack.push(next);
                display(next);
                depth++;
            }
        } else {
            stack.pop();
            depth--;
        }
    }
}

为什么下面的代码 return A、AEC、AEBCD 没有？

Why doesn't the following code return A, AEC, AEBCD?

java

search

depth-first-search