주어진 깊이까지 너비 우선 그래프 너비를 구현하십시오.

Question

하나의 노드에서 다른 노드로의 경로 수를 반환하는 너비의 첫 번째 그래프 탐색을 구현하려고하지만 주어진 노드 수를 통해서만 시도합니다.

예를 들어 노드 A, B, C, D, E의 목록이 주어진다면 A부터 D까지 얻을 수있는 여러 경로의 수를 알고 싶지만 경로에는 2 개 이상의 정류장이없는 경우에만 . A-B-D, A-E-D는 합격으로 간주되지만 A-B-E-D는 너무 많은 정류장이므로 응답은 2 경로가됩니다.

이 알고리즘을 구현하려고하지만 깊이를 추적 할 수있는 방법이 확실하지 않아 내 검색이 n 레벨만큼 깊게 진행됩니다.

여기 내 코드는 지금까지 작성했습니다. 문제는 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; 
} 

주를 당신의 큐 깊이가 증가함에 따라 노드를 반환 보장이 비로소 작동합니다. 폭 넓은 우선 검색의 경우 항상 그렇지만,이를 별표 검색이나 나중에 변경하려는 경우이 가정은 깨집니다.