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

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

0 голосов
/ 04 июня 2018

У меня есть граф с городами в качестве узлов и класс 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 на этом графике, чтобы я мог успешно распечатать все возможные поездки между двумя городами в определенный день?

1 Ответ

0 голосов
/ 04 июня 2018

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

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

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

...