Java图数据结构实现航班连接查询与总距离计算教程-java教程-PHP中文网

Java图数据结构实现航班连接查询与总距离计算教程

本教程旨在指导开发者优化java航班网络程序，使其能够根据用户指定的中转城市，准确显示该城市的所有后续连接及其从初始出发地累计的总距离。文章将详细分析并修正现有代码中图遍历逻辑的不足，重点阐述如何正确过滤连接、传递并计算累积距离，以实现清晰、准确的航班信息输出。

在构建航班网络这样的图数据结构应用中，准确地查询并展示特定节点（城市）的连接及其相关属性（距离）是核心功能之一。原始代码在尝试显示中转城市连接时，未能正确地过滤图中的所有连接，并且没有实现从起始城市到中转城市再到后续城市的总距离计算。本文将详细讲解如何通过重构关键方法，解决这些问题，实现一个功能完善的航班连接查询系统。

1. 理解图结构与现有代码概览

在提供的代码中，HWGraph 类负责管理航班网络图，它使用 HashMap<String, ArrayList<Vertex>> graphMap 来存储每个城市及其直接连接的顶点（Vertex）。Vertex 类则简单地存储了目的城市标签（label）和到该目的城市的距离（weight）。HWDriverPrep 是主驱动程序，负责创建图、获取用户输入并调用查询方法。

当前 HWDriverPrep 的 main 方法流程如下：

创建航班图。
打印整个图的连接（通过 printGraph 方法）。
获取用户输入的中转城市。
尝试显示从起始城市（例如“Chicago”）到中转城市（例如“New York”）的连接信息。
调用 showConnections 方法。

问题主要集中在 showConnections 和其辅助方法 connect 上。

立即学习“Java免费学习笔记（深入）”；

2. 核心问题分析：showConnections 与 connect 的不足

原始的 showConnections 方法如下：

private static void showConnections(HWGraph g, Vertex layOverVertex) {
    g.graphMap.forEach(
            (key, value) -> connect(key, value));
}

登录后复制

其辅助方法 connect 如下：

private static void connect(String key, ArrayList<Vertex> value) {
    for(Vertex v : value){
        System.out.println("City: " + v.label + " Distance: " + v.weight);
    }
}

登录后复制

通过对比 printGraph 和 showConnections，我们可以发现它们的核心逻辑几乎相同：都遍历了 g.graphMap 中的所有条目。这意味着 showConnections 并没有根据 layOverVertex 参数进行任何过滤，而是打印了图中所有城市的连接，这显然不符合“显示中转城市连接”的需求。

此外，connect 方法仅打印了当前航段的距离（v.weight），而没有考虑从初始出发城市到中转城市的距离。为了计算总距离，我们需要将这个“初始距离”传递给 connect 方法。

3. 解决方案：重构 showConnections 和 displayLayoverConnections

为了解决上述问题，我们需要进行以下调整：

课游记AI

AI原生学习产品

查看详情

showConnections 方法的职责明确化：它应该根据传入的 layOverVertex 来获取其对应的连接，而不是遍历整个图。同时，需要将从起始城市到中转城市的距离作为参数传递下去。
引入新的辅助方法 displayLayoverConnections：这个方法将负责接收中转城市到起点的距离，并计算每个后续连接的总距离。

3.1 修正 HWDriverPrep 中的调用逻辑

首先，在 HWDriverPrep.main 方法中，我们需要获取从起始城市到中转城市的 Vertex 对象，并从中提取距离。

public class HWDriverPrep {
    public static void main(String[] args) {
        HWGraph g = createGraph();
        // printGraph( g ); // 可选择是否打印整个图

        Set<String> keys = g.getKeys();
        String startCity = "Chicago";
        String layOverCityLabel = getLayOverCity(keys, startCity); // 用户输入的中转城市标签

        // 获取从起始城市到中转城市的Vertex对象，其中包含了该段的距离
        Vertex layOverVertex = g.getThisVertex(startCity, layOverCityLabel);

        if (layOverVertex == null) {
            System.out.println("中转城市 " + layOverCityLabel + " 从 " + startCity + " 无法直达或不存在。");
            return;
        }

        System.out.printf("\n从起始城市:%s 经过中转城市:%s (距离:%d) 的后续连接:\n",
                startCity, layOverVertex.label, layOverVertex.weight);

        // 调用修正后的showConnections，传入图对象、中转城市标签和起点到中转城市的距离
        showConnections(g, layOverVertex.label, layOverVertex.weight);
    }
    // ... 其他不变的方法 ...
}

登录后复制

3.2 重构 showConnections 方法

showConnections 方法现在将接收中转城市的标签和从起点到中转城市的距离。它的任务是获取该中转城市的所有直接连接，并为每个连接调用一个辅助方法来显示详细信息和总距离。

public class HWDriverPrep {
    // ... 其他方法 ...

    /**
     * 显示指定中转城市的所有后续连接及其总距离。
     *
     * @param g                  航班图对象。
     * @param layOverCityLabel   中转城市的标签。
     * @param distanceToLayover  从起始城市到中转城市的距离。
     */
    private static void showConnections(HWGraph g, String layOverCityLabel, int distanceToLayover) {
        // 获取中转城市的所有直接连接
        ArrayList<Vertex> connections = g.getConnections(layOverCityLabel);

        if (connections == null || connections.isEmpty()) {
            System.out.println("中转城市 " + layOverCityLabel + " 没有后续连接。");
            return;
        }

        for (Vertex connection : connections) {
            // 调用辅助方法显示每个连接的详细信息，包括总距离
            displayLayoverConnectionDetails(layOverCityLabel, connection, distanceToLayover);
        }
    }

    /**
     * 显示单个后续连接的详细信息，包括总距离。
     *
     * @param fromCityLabel      当前出发城市（即中转城市）的标签。
     * @param toVertex           连接到的目的顶点（包含目的城市标签和该段距离）。
     * @param initialDistance    从起始城市到当前出发城市（中转城市）的距离。
     */
    private static void displayLayoverConnectionDetails(String fromCityLabel, Vertex toVertex, int initialDistance) {
        int totalDistance = initialDistance + toVertex.weight;
        System.out.printf("  %s -> %s (距离: %d), 总距离: %d\n",
                fromCityLabel, toVertex.label, toVertex.weight, totalDistance);
    }

    // ... 其他方法 ...
}

登录后复制

关键改进点：

showConnections 不再遍历整个 graphMap，而是通过 g.getConnections(layOverCityLabel) 精确获取中转城市的出度边。
引入了 distanceToLayover 参数，用于传递从起点到中转城市的距离。
displayLayoverConnectionDetails 方法负责格式化输出，并计算 initialDistance + toVertex.weight 得到总距离。

4. 完整的 HWDriverPrep.java 示例

import java.util.ArrayList;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class HWDriverPrep {
    public static void main(String[] args) {
        HWGraph g = createGraph();
        printGraph( g ); // 打印整个图的连接，用于调试或概览

        Set<String> keys = g.getKeys();
        String startCity = "Chicago"; // 假设起始城市为芝加哥

        // 获取用户输入的中转城市标签
        String layOverCityLabel = getLayOverCity(keys, startCity);

        // 获取从起始城市到中转城市的Vertex对象，其中包含了该段的距离
        // 注意：这里假设起始城市到中转城市是直达的，如果需要多段中转，逻辑会更复杂
        Vertex layOverVertex = g.getThisVertex(startCity, layOverCityLabel);

        if (layOverVertex == null) {
            System.out.println("错误：中转城市 '" + layOverCityLabel + "' 从 '" + startCity + "' 无法直达或不存在。");
            return;
        }

        System.out.printf("\n--- 从起始城市: %s 经过中转城市: %s (第一段距离: %d) 的后续连接 ---\n",
                startCity, layOverVertex.label, layOverVertex.weight);

        // 调用修正后的showConnections，传入图对象、中转城市标签和起点到中转城市的距离
        showConnections(g, layOverVertex.label, layOverVertex.weight);
    }

    /**
     * 打印整个图的所有连接。
     * @param g 航班图对象。
     */
    private static void printGraph(HWGraph g) {
        System.out.println("--- 整个航班网络连接 ---");
        g.graphMap.forEach(
                (key, value) -> {
                    System.out.println("出发城市: " + key + "--------");
                    for(Vertex v : value){
                        System.out.println("  目的地: " + v.label + ", 距离: " + v.weight);
                    }
                });
        System.out.println("----------------------\n");
    }

    /**
     * 获取用户输入的中转城市。
     * @param keys 所有可用城市的集合。
     * @param startCity 起始城市（用于提示）。
     * @return 用户输入的中转城市标签。
     */
    private static String getLayOverCity(Set<String> keys, String startCity) {
        Scanner s = new Scanner(System.in);
        StringBuilder availableCities = new StringBuilder();
        String separator = "";
        for(String item : keys) {
            availableCities.append(separator).append(item);
            separator = ", ";
        }

        System.out.printf("请选择一个中转城市 (%s): ", availableCities.toString());
        String retItem = s.nextLine();
        return retItem;
    }

    /**
     * 显示指定中转城市的所有后续连接及其总距离。
     *
     * @param g                  航班图对象。
     * @param layOverCityLabel   中转城市的标签。
     * @param distanceToLayover  从起始城市到中转城市的距离。
     */
    private static void showConnections(HWGraph g, String layOverCityLabel, int distanceToLayover) {
        // 获取中转城市的所有直接连接
        ArrayList<Vertex> connections = g.getConnections(layOverCityLabel);

        if (connections == null || connections.isEmpty()) {
            System.out.println("中转城市 '" + layOverCityLabel + "' 没有后续连接。");
            return;
        }

        for (Vertex connection : connections) {
            // 调用辅助方法显示每个连接的详细信息，包括总距离
            displayLayoverConnectionDetails(layOverCityLabel, connection, distanceToLayover);
        }
    }

    /**
     * 显示单个后续连接的详细信息，包括总距离。
     *
     * @param fromCityLabel      当前出发城市（即中转城市）的标签。
     * @param toVertex           连接到的目的顶点（包含目的城市标签和该段距离）。
     * @param initialDistance    从起始城市到当前出发城市（中转城市）的距离。
     */
    private static void displayLayoverConnectionDetails(String fromCityLabel, Vertex toVertex, int initialDistance) {
        int totalDistance = initialDistance + toVertex.weight;
        System.out.printf("  %s -> %s (本段距离: %d), 总距离 (从起始城市): %d\n",
                fromCityLabel, toVertex.label, toVertex.weight, totalDistance);
    }

    /**
     * 创建并初始化航班图。
     * @return 初始化后的HWGraph对象。
     */
    private static HWGraph createGraph() {
        HWGraph g = new HWGraph();
        g.addVertex("Chicago");
        g.addVertex("Dallas");
        g.addVertex("Atlanta");
        g.addVertex("New York");
        g.addVertex("Houston");
        g.addVertex("Orlando");

        // --- 添加连接
        g.addEdge("Chicago",new Vertex("Dallas",968));
        g.addEdge("Chicago",new Vertex("Atlanta",718));
        g.addEdge("Chicago",new Vertex("New York",790));

        g.addEdge("Dallas",new Vertex("Houston",239));
        g.addEdge("Dallas", new Vertex("Orlando",1120));

        g.addEdge("Houston", new Vertex("Orlando",967));

        g.addEdge("Atlanta", new Vertex("Dallas",781));
        g.addEdge("Atlanta", new Vertex("New York",870));
        g.addEdge("Atlanta", new Vertex("Orlando",438));

        g.addEdge("New York", new Vertex("Houston",1647));
        g.addEdge("New York", new Vertex("Orlando",1080));

        return g;
    }
}

登录后复制

Vertex.java 和 HWGraph.java 保持不变，因为它们的核心功能是正确的。

5. 运行示例与输出

假设起始城市为 Chicago，用户输入中转城市为 New York：

输入：

请选择一个中转城市 (Chicago, Dallas, Atlanta, New York, Houston, Orlando): New York

登录后复制

预期输出：

--- 整个航班网络连接 ---
出发城市: Chicago--------
  目的地: Dallas, 距离: 968
  目的地: Atlanta, 距离: 718
  目的地: New York, 距离: 790
出发城市: Dallas--------
  目的地: Houston, 距离: 239
  目的地: Orlando, 距离: 1120
出发城市: Atlanta--------
  目的地: Dallas, 距离: 781
  目的地: New York, 距离: 870
  目的地: Orlando, 距离: 438
出发城市: New York--------
  目的地: Houston, 距离: 1647
  目的地: Orlando, 距离: 1080
出发城市: Houston--------
  目的地: Orlando, 距离: 967
出发城市: Orlando--------
----------------------

--- 从起始城市: Chicago 经过中转城市: New York (第一段距离: 790) 的后续连接 ---
  New York -> Houston (本段距离: 1647), 总距离 (从起始城市): 2437
  New York -> Orlando (本段距离: 1080), 总距离 (从起始城市): 1870

登录后复制

6. 注意事项与总结

参数传递的重要性：在图遍历或路径计算中，将当前状态（如已累计的距离）作为参数在方法间传递是实现复杂逻辑的关键。
职责单一原则：将 showConnections 的职责限定为获取特定节点的连接，而将计算和格式化输出的职责交给辅助方法 displayLayoverConnectionDetails，可以使代码更清晰、更易于维护。
过滤逻辑：确保你的查询方法只处理相关数据，而不是盲目遍历整个数据结构。这对于性能和结果的准确性都至关重要。
错误处理：在实际应用中，应增加对用户输入和图查询结果的健壮性检查，例如当用户输入的中转城市不存在或无法从起始城市到达时的处理。

通过以上优化，我们成功地解决了原始代码中显示中转城市连接和计算总距离的问题，使得航班查询功能更加准确和专业。

以上就是Java图数据结构实现航班连接查询与总距离计算教程的详细内容，更多请关注php中文网其它相关文章！