DFSアルゴリズムが右から左へ検索しています

Question

深度優先探索アルゴリズムを書いていますが、ツリーの右側から左に向かって検索しています。私は私のコードからそれがなぜそうしているのかを見ることができますが、左から右に検索するように変更するソリューションを考え出すことはできません。

public class DFS { 

    public LinkedList<Node> search(Node root, Node target) {  
     LinkedList<Node> open = new LinkedList<>(); 
     LinkedList<Node> closed = new LinkedList<>(); 

     open.addLast(root); 
     while (!open.isEmpty()) { 
      Node current = open.removeFirst(); 
      if (current.equals(target)) { 
       closed.addLast(current); 
       return closed; 
      } 
      else { 
       ArrayList<Node> children = current.getChildren(); 
       closed.addLast(current); 
       for (Node child : children) { 
        if (!open.contains(child) && !closed.contains(child)) { 
         open.addFirst(child); 
        } 
       } 
      } 
     } 
     return null; 
    } 
} 

closedは、彼らが訪問された順に訪問したノードのリストです。

Node.getChildren()は、追加された順にノードの子のArrayListを返します。あなたのDFSが本当にあなたの子供を逆転、またはその代わりaddLastのaddFirst、方向に依存している場合は

public class Node { 

    private ArrayList<Node> children; 
    private String name; 

    public Node(String name){ 
     children = new ArrayList<Node>(); 
     this.name = name; 
    } 

    public ArrayList<Node> getChildren(){ 
     return new ArrayList<Node>(children); 
    } 

    public Node addChild(Node child){ 
     children.add(child); 
     return child; 
    } 

    public void removeChild(Node child){ 
     children.remove(child); 
    } 

    public String getName() { 
     return name; 
    } 

    public boolean equals(Node other){ 
     return (this.getName().compareTo(other.getName())==0); 
    } 
} 

Answer 1

シンプル応答する「どのように回避するためには、右から左に」質問です：あなたはとにかく欠陥があるALGO

  ArrayList<Node> children = current.getChildren(); 
      closed.addLast(current); 
      // *** Not like this *** 
      // for (Node child : children) { 
      // if (!open.contains(child) && !closed.contains(child)) { 
      //  open.addFirst(child); 
      // } 
      //} 
      // **** But like this **** 
      for(int i=children.size()-1; i>=0; i--) { 
       Node child=children.get(i); 
       if (!open.contains(child) && !closed.contains(child)) { 
        open.addFirst(child); 
       } 
      } 
      // If you are **absolutely** sure your structure is a 
      // Tree (thus, no cycles) then testing against 
      // open/closed is unnecessary and the code can be simplified: as 
      // open.addAll(0, children); 

：ワインドアップへの規定はありません/に失敗したツリー内の下降パスを破棄結果をお持ちください（あなたはclosedから決して削除されません）。これはあなたの質問の範囲外です。

Answer 2

：ここでEDIT

は、ノードクラスのですか？

Answer 3

GetChildrenメソッド次に、あなたが最初の要素にあなたがメインループを実行するたびにポップそこからスタック「開く」を、持っている

1..nの要素を持っています。

チャイルドをスタックの前にプッシュすると（addFirst）、1..nでn..1で終了します（1を挿入します。最初に挿入します2、最初に挿入します）。 1は2番目など）。

popを最後のインデックスから開くか、または子をスタックの最後にプッシュして、getChildrenがそれを要求した順序で返さない限り動作します。