Реализация ширины первого обхода графа до заданной глубины

Я пытаюсь реализовать широту первого обхода графа, который возвращает количество путей от одного узла к другому, но только через заданное количество узлов.

Например, приведен список узлов A, B, C, D, E, если я хочу знать количество различных путей, которые я могу получить от A до D, но только если путь имеет не более 2 остановок. A-B-D, A-E-D будет считаться приемлемым, но A-B-E-D будет слишком много остановок, поэтому ответ будет 2 пути.

Я пытаюсь реализовать этот алгоритм, но я не уверен, как я могу отслеживать глубину, так что мой поиск идет только N уровней глубоко.

Вот мой codeI написали до сих пор. Проблема заключается в методе 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));

}

}

1 ответ

  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объектов можно просто установить глубину на единицу больше, чем глубина текущего узла.

    Сделав это, вы можете добавить что-то подобное в свою searchNumPathsфункцию (после вызова queue.remove()):

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

    Обратите внимание, что это работает только в том случае, если ваша очередь гарантированно возвращает узлы с увеличением глубины. Это всегда верно для поиска по ширине, но если вы собираетесь изменить его на A-star search или что-то позже, это предположение нарушается.