与えられた深さまでの幅広い最初のグラフのトラバースを実装する

Question

私はあるノードから別のノードへのパスの数を返しますが、与えられた数のノードだけを通した幅の最初のグラフトラバーサルを実装しようとしています。

例えば、ノードA、B、C、D、Eのリストが与えられている場合、AからDに到達できる異なるパスの数を知りたければ、パスに2つ以上のストップ。 A-B-D、A-E-Dは許容されると考えられるが、A-B-E-Dは非常に多くの停止点であるため、答えは2経路となる。

私はこのアルゴリズムを実装しようとしていますが、どのようにして深さを追跡することができないのか分かりません。

ここに私のコードはこれまでに書いてあります。問題は、searchNumPaths（）メソッドにあります。

public class PathSearch{ 
private int maxSearches; 
private int pathCount; 
private int numPaths; 
private String node; 
private ArrayList<ArrayList<String>> path; 
ArrayList<Node> visited; 

public PathSearch(int maxSearches, int pathCount) { 
    node = ""; 
    this.maxSearches = maxSearches; 
    this.pathCount = pathCount; 
    path = new ArrayList<ArrayList<String>>(); 
    visited = new ArrayList<Node>(); 
} 

public int searchNumPaths(HashMap<String, Node> graph, Node startLocation, String endLocation, Queue<String> queue) { 
    //queue.add(startLocation.getLocation()); 
    while(!queue.isEmpty()) { 
     node = queue.remove(); 
     System.out.println("\n" + node +"\n"); 
     for (Edge realPath: graph.get(node).getNeighbors()) { 
       node = realPath.getEndLocation(); 
       System.out.println(node); 
       queue.add(node); 
       if (node.equals(endLocation)) { 
        numPaths++; 
       } 
     } 
     pathCount++; 
     if (pathCount>6){ 
      break; 
     } 
     for (int i = 0; i<queue.size(); i++) { 
      searchNumPaths(graph, graph.get(queue.peek()), endLocation, queue); 
      queue.remove(); 
     } 

    } 
    return numPaths; 
} 

public static void main(String[] args) throws IOException { 
    Train train = new Train(); 
    Graph graph = new Graph(train.readFile("input.txt")); 
    LinkedList<String> queue = new LinkedList<String>(); 
    queue.add("A"); 
    PathSearch great = new PathSearch(10, 0); 
    HashMap<String, Node> map = graph.returnMap(); 
    Node node = graph.returnMap().get("A"); 
    String nodeTwo = graph.returnMap().get("C").getLocation(); 
    //System.out.println(queue.remove()); 
    System.out.println("Number of paths: " + great.searchNumPaths(map, node, nodeTwo, queue)); 

} 

}

Answer 1

あなたはノードの深さを示す数値と一緒にあなたのキューに入れ、現在の文字列が含まれているQueueNodeクラスを作成することができます。あまりにも深いノードに出会うまで検索を続けることができます。このような何か（TはあなたのケースでStringです）：

public class QueueNode<T> { 

    T value; 
    int depth; 

    public QueueNode(T value, int depth) { 
     this.value = value; 
     this.depth = depth; 
    } 

    // And so on.. Getters etc. 

} 

新しいQueueNodeオブジェクトを作成するときに、あなただけの現在のノードの深さよりも大きいものに深さを設定することができます。

これを行うことにより、あなたは（queue.remove()の呼び出し後）ごsearchNumPaths関数に次のようなものを追加することができます。

if (node.getDepth() > maxDepth) { 
    return numPaths; 
} 

注意をそのあなたのキューは、深さの増加に伴って、ノードを返すことが保証され、こののみ動作する場合。幅優先検索の場合は常にそうですが、それをA-star検索などに変更する場合は、この仮定が破られます。