次のコードは、A、AEC、AEBCDを返さないのはなぜですか？

Question

私は、アルゴリズムが繰り返し深化検索アルゴリズムのように動作するように、私はループで何回も実行するDepth Limited Searchアルゴリズムを持っています メソッドを明示的に呼び出すときにのみコードが返されますが、それをループで呼び出す。

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(""); 
    } 
} 
} 

そして、ここに私のグラフのクラスがあります：

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

理由は2つある。

まず、それぞれのchecked値はNodeがdls(int limit)後trueに設定されている訪問と呼ばれ、方法の後続の呼び出しにそう残ります。最初にcheckedをfalseに戻すように設定する必要があります。

第2に、depthはクラスメンバー変数/フィールドであり、毎回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--; 
     } 
    } 
}