深さのJavaでの最初の検索 - 親ノードに戻る方法？

Question

私はJavaで深みのある最初の検索を再帰的にやろうとしています。現時点では、コードは私のグラフをうまく走りますが、ルートを見つけるためにバックトラックすることはありません。私は精神的なブロックのビットを正直に持っています。親ノードに戻る最良の方法は何でしょうか？ここで

私のコードは、これまでのところです：

private final Map<Character, Node> mNodes; 
private final List<Edge> mEdges; 

public DepthFirstSearch(Graph graph){ 
    mNodes = graph.getNodes(); 
    mEdges = new ArrayList<>(graph.getEdges()); 
    for(Node node : mNodes.values()){ 
     node.setVisited(false); 
    } 
} 

public void depthFirstSearch(Node source){ 
    source.setVisited(true); 
    List<Node> neighbours = source.getNeighbours(mEdges); 
    for(Node node : neighbours){ 
      if(!node.isVisited()){ 
       System.out.println(node.getName()); 
       depthFirstSearch(node); 
      } 
     } 
    } 

そしてgetNeighbourコード：イェーガーのアイデアを試すため

public List<Node> getNeighbours(List<Edge> edges) { 
     List<Node> neighbours = new ArrayList<>(); 
     for(Edge edge : edges){ 
      if(edge.getFrom().equals(this)){ 
       neighbours.add(edge.getTo()); 
      } 
     } 
     return neighbours; 
    } 

追加コード：

public void depthFirstSearch(Node source){ 
     source.setVisited(true); 
     List<Edge> neighbours = source.getNeighbouringEdges(mEdges); 
     for(Edge edge : neighbours){ 
       if(!edge.getTo().isVisited()){ 
        System.out.println(edge.getTo().getName()); 
        depthFirstSearch(edge.getTo()); 
       }else{ 
        depthFirstSearch(edge.getFrom()); 
       } 
      } 
     } 

Answer 1

推測：あなたは「取得しています"隣人のmEdgesサラウンドのフィールドのようですクラスです。

ほとんどの場合、各ノードにはのエッジがあり、訪問時にはエッジが必要です。

Answer 2

通常、ルートノードには子ノードがあります。それぞれの子供は自分の子供を持つことができます。だから、むしろだろう：私はメンバーvisitedの必要性を持っていない

public void depthFirstSearch(Node source) 
{ 
    for(Node node : source.getChildren()) 
    { 
     System.out.println(node.getName()); 
     depthFirstSearch(node); 
     // and right here you get your back tracking implicitly: 
     System.out.println("back at " + node.getName()); 
    } 
} 

注意を...

編集：

今、あなたはあなたのデータ構造を提供することを、私に聞かせて別の方法を提案する：

class Node 
{ 
    // all that you have so far... 

    private char mId; 
    private List<Node> mChildren = new ArrayList<Node>(); 

    public char getId() 
    { 
     return mId; 
    } 
    public List<Node> getChildren() 
    { 
     return Collections.unmodifiableList(children); 
    } 

    // appropriate methods to add new children 
} 

idがマップのキーを置き換えます。次に、どこかで始めるには、ルートNode mRootがあります。これはツリーを実装する典型的な方法です。

子ノードから直接移動したい場合があります。次に、ノードクラスにprivate Node parent;がさらに必要です（子リストをプライベートリストに追加するときはすぐにthisに設定され、削除されるときはnullに設定されます）。ただし、これをバックトラックに使用することはありません。そのため、上記の深度最初の検索は変更されません。