首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >多重航班图的Java广度优先搜索

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

Stack Overflow用户
提问于 2018-06-04 05:44:06
回答 1查看 511关注 0票数 1

我有一个以城市为节点,以类Flight为边的图。每个航班都有起飞时间、到达时间、航班号和航班运营的一系列天数。多条边可以连接每对节点,使图形成为多重图。我需要回答这个问题:在给定的一天中,有哪些航班可以从Place1到Place2,并且可以转机?

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

代码语言:javascript
复制
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,这样我就可以在给定的一天成功打印出两个城市之间所有可能的旅行?

EN

回答 1

Stack Overflow用户

发布于 2018-06-04 06:37:10

重要的是要理解,对于您的路径搜索算法而言,您的数据并不完全形成一个多重图。这是因为可以从给定节点遍历的出站边取决于到达该节点所遍历的入站边。这就是为什么需要为DFS使用isTransferable()方法的原因。

相反,您可以更好地将其描述为普通图的紧凑表示,其中节点表示(城市、到达航班、航班日期)三元组。或者因为每个航班只有一个目的地,所以每个节点的特征数据实际上只是到达航班和日期。或者,如果你把它分割成每天的单独图表,那么你剩下的就是每个节点的特征数据--到达航班。

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

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/50671248

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档