Java - поиск в ширину по мультиграфу полетов

Question

У меня есть график с городами в качестве узлов и класса Flight в качестве ребер. У каждого рейса есть время вылета, время прибытия, номер рейса и ряд дней, в течение которых он выполняется. Несколько ребер могут соединить каждую пару узлов, что делает график мультиграфом. Мне нужно ответить на вопрос: каковы доступные рейсы из Place1 в Place2 в данный день, возможны ли трансферы?

Следующие два метода используют поиск в глубину, чтобы найти и напечатать ответ:

public static void printRoutes(String day,String source,String place1, String place2, boolean[] visited, LinkedList<Edge> Route,Grafo g) {

    int index = hash.get(place1);
    visited[index] = true;


    if(place1.equals(place2)) 
        if(isTransferable(day,Route,source))
            writeRoute(Route,source);

    if(place1 != place2) {
        LinkedList<Edge> adjs = g.adjs_no(place1);


        for(Edge a: adjs) {
            if(!visited[hash.get(a.node_final)]) {
                Route.add(a);
                printRoutes(day,source,a.node_final,place2,visited,Route,g);
                Route.remove(a);
            }
        }
    }
    visited[indice] = false;            
}

public static void writeRoute(LinkedList<Edge> Route,String source) {
        System.out.print(source + " -> ");
        for (int i = 0; i < Route.size(); i++) {
            System.out.print(Route.get(i).vertex_final() + " | Flight Number:");
            System.out.print(Route.get(i).flight.flightNumber + " | Departure Time:" + Route.get(i).flight.departureTime);
            System.out.println();
            if(i != Route.size()- 1)System.out.print(Route.get(i).vertex_final() + " -> ");

        }
        System.out.println();
        System.out.println();    
    }

isTransferable проверяет, есть ли промежуток времени между прибытием и отправлением двух рейсов не менее 40 минут.

Я хотел бы ответить на этот вопрос, используя поиск в ширину вместо DFS, чтобы более короткие поездки появлялись первыми. Алгоритм, который я использую для BFS, не работает для мультиграфов. Есть ли способ выполнить BFS на этом графике, чтобы я мог успешно распечатать все возможные поездки между двумя городами в данный день?

Answer 1

Важно понимать, что ваши данные не совсем формируют мультиграф для целей вашего алгоритма поиска маршрута. Это связано с тем, что исходящие ребра, которые можно пройти от данного узла, зависят от того, какой входящий ребро было пройдено для достижения этого узла. Вот почему вам нужен ваш isTransferable() метод для DFS.

Вместо этого то, что у вас есть, было бы лучше охарактеризовать как компактное представление обычного графика, на котором узлы представляют (город, рейс прибытия, дату полета) тройки. Или, поскольку у каждого рейса есть только один пункт назначения, характеристические данные для каждого узла на самом деле представляют собой только дату и дату прибытия рейса. Или, если вы разберете это на отдельные графики для каждого дня, тогда вы останетесь с прибывающим рейсом, являющимся характеристическими данными для каждого узла.

Имея это в виду, вы должны иметь возможность адаптировать обычный алгоритм BFS к вашему представлению данных. Ваш существующий isTransferable() Метод может помочь, но ключ заключается в том, чтобы правильно определить узлы (по входящему рейсу, а не (напрямую) по городу).