首页 文章

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

提问于
浏览 次
1

我有一个图表，城市作为节点，一个类作为边缘 . 每个航班都有出发时间，到达时间，航班号和航班运营的一系列天数 . 多个边可以连接每对节点，使图形成为多图 . 我需要回答这个问题： What are the available flights from Place1 to Place2 on a given day, with transfers being possible?

以下两种方法使用深度优先搜索来查找和打印答案：

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，以便我可以成功打印某一天两个城市之间的所有可能的旅行？

java depth-first-search breadth-first-search graph-traversal

1 回答

  • 1

    为了您的路径搜索算法，它完全形成一个多图 . 这是因为可以从给定节点遍历的出站边缘取决于遍历到达该节点的入站边缘 . 这就是你为DFS需要 isTransferable() 方法的原因 .

    相反，你所拥有的将更好地表征为普通图的紧凑表示，其中节点表示（城市，到达航班，航班日期）三元组 . 或者由于每个航班只有一个目的地，每个节点的特征数据实际上只是到达航班和日期 . 或者，如果您将其划分为每天的单独图表，那么您的到达航班将成为每个节点的特征数据 .

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

    回复于

相关问题