多个航班图上的Java广度优先搜索

Question

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();    
    }

我想用广度优先搜索而不是DFS来回答这个问题，这样较短的行程就会首先出现。但是，我对BFS的算法对多图不起作用。有没有一种方法可以在这个图上执行BFS，这样我就可以成功地打印出给定一天两个城市之间所有可能的行程？

Answer 1

重要的是要了解，您的数据并不完全形成一个多图的目的，您的路线搜索算法。这是因为可以从给定节点遍历的出站边取决于通过哪个入站边到达该节点。这就是DFS需要istransferable()方法的原因。

相反，您所拥有的将更好地描述为一个普通图的紧凑表示，其中的节点表示（城市、到达航班、航班日期）三元组。或者因为每个航班都有一个目的地，所以每个节点的特征数据实际上只是到达航班和日期。或者，如果您将这些数据分割成一个单独的图，那么每个节点的特征数据都是到达航班。

考虑到这一点，您应该能够使普通的BFS算法适应您的数据表示。您现有的istransferable()方法可以提供帮助，但关键是适当地标识节点（通过入站航班，而不是（直接）通过城市）。