本教程旨在指导开发者如何在java中处理航班图数据，实现从指定起始城市经过中转城市，计算并展示中转城市的所有直接连接及其到最终目的地的累计总距离。文章将详细阐述如何优化图遍历逻辑，确保只显示与中转城市直接相连的节点，并正确累加行程距离，从而生成清晰、准确的航班连接信息。
1. 概述与问题背景
在构建航班管理系统时，一个常见的需求是根据用户选择的中转城市，显示该中转城市的所有后续连接，并计算从起始城市到这些后续目的地的总距离。例如，从芝加哥（Chicago）出发，中转纽约（New York），需要显示纽约到奥兰多（Orlando）的连接，并计算芝加哥->纽约->奥兰多的总距离。
原始代码中，showConnections 方法的实现存在两个主要问题：
- 未正确筛选中转城市连接：它遍历了图中的所有城市及其连接，而不是仅仅显示用户指定中转城市的连接。
- 未累加总距离：它只显示了中转城市到下一个目的地的单段距离，而没有将起始城市到中转城市的距离计入总和。
本教程将通过修改现有代码，解决这些问题，实现精确的连接筛选和距离计算。
2. 图数据结构回顾
在提供的代码中，航班网络使用 HWGraph 类表示，它是一个基于邻接列表的图。
立即学习“Java免费学习笔记（深入）”；
- HWGraph 内部使用 HashMap
> graphMap 来存储图结构。其中，String 是城市名称（作为图的节点），ArrayList 存储了该城市所有直接相连的城市及其对应的飞行距离（作为边的权重）。 - Vertex 类是一个简单的结构，包含 label（城市名称）和 weight（到该城市的距离）。
HWGraph.java 关键方法：
- addVertex(String label): 添加一个城市节点。
- addEdge(String label1, Vertex v): 添加一条从 label1 到 v.label 的有向边，权重为 v.weight。
- getConnections(String label): 获取给定城市的所有直接连接（即其邻居节点列表）。
- getThisVertex(String startCity, String destCity): 从 startCity 的连接中查找 destCity 对应的 Vertex 对象，用于获取从 startCity 到 destCity 的直飞距离。
3. 问题分析与解决方案
3.1 识别原始代码中的缺陷
我们首先审视原始的 HWDriverPrep.java 中的 showConnections 和 connect 方法：
// HWDriverPrep.java (Original)
private static void showConnections(HWGraph g, Vertex layOverVertex) {
// 问题1：这里遍历了整个图的graphMap，而不是只关注layOverVertex的连接
g.graphMap.forEach(
(key, value) -> connect(key, value));
}
private static void connect(String key, ArrayList value) {
// 问题2：这里只打印了单段距离，没有考虑从起始城市到中转城市的距离
for(Vertex v : value){
System.out.println("City: " + v.label + " Distance: " + v.weight);
}
} 可以看到，showConnections 方法没有利用传入的 layOverVertex 参数来筛选连接，而是对 graphMap 中的每一个 key（城市）都调用了 connect 方法。这导致了所有城市的连接都被打印出来。同时，connect 方法只打印了当前航段的距离，无法计算从起始城市到中转城市再到下一目的地的总距离。
3.2 优化思路
为了解决上述问题，我们需要进行以下调整：
- 精确获取中转城市连接：在 showConnections 方法中，不再遍历整个图，而是直接使用 layOverVertex.label 调用 g.getConnections() 方法来获取中转城市的所有直接连接。
- 传递并累加距离：showConnections 方法需要接收一个额外的参数，即从起始城市到中转城市的距离。然后，在遍历中转城市的连接时，将这个距离与当前航段的距离相加，得到最终的总距离。
- 简化辅助方法：原有的 connect 方法可以被废弃或其逻辑直接融入 showConnections 中，因为它不再需要遍历整个图的键值对。
4. 代码实现与优化
我们将主要修改 HWDriverPrep.java 中的 main 方法和 showConnections 方法。
4.1 修改 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 keys = g.getKeys();
String startCity = "Chicago"; // 示例起始城市
// 获取用户输入的中转城市
String layOverCityLabel = getLayOverCity( keys, startCity);
// 获取从起始城市到中转城市的Vertex对象，其中包含了该段的距离
Vertex layOverVertex = g.getThisVertex(startCity, layOverCityLabel);
if (layOverVertex != null) {
System.out.printf("\n从起始城市: %s 经中转城市: %s (距离: %d) 的后续连接及总距离:\n",
startCity, layOverVertex.label, layOverVertex.weight);
// 调用优化后的showConnections方法，传入中转城市Vertex和从起始城市到中转城市的距离
showConnections(g, layOverVertex, layOverVertex.weight);
} else {
System.out.printf("\n无法找到从 %s 到中转城市 %s 的连接，或中转城市不存在。\n", startCity, layOverCityLabel);
}
}
// 辅助方法：打印整个图的连接 (保持不变，用于调试)
private static void printGraph(HWGraph g) {
g.graphMap.forEach(
(key, value) -> show(key, value));
}
// 辅助方法：显示单个城市的连接 (保持不变)
private static void show(String key, ArrayList value) {
System.out.println("显示城市 " + key + " 的连接 --------");
for(Vertex v : value){
System.out.println(" -> 城市: " + v.label + ", 距离: " + v.weight);
}
}
// 辅助方法：获取用户输入的中转城市 (保持不变)
private static String getLayOverCity(Set keys, String startCity) {
Scanner s = new Scanner(System.in);
String oStr = "";
String cm = "";
for(String item: keys)
{
oStr += cm + item;
cm = ", ";
}
System.out.printf("请选择一个中转城市 (%s): ",oStr);
String retItem = s.nextLine();
return retItem;
}
/**
* 显示中转城市的所有连接，并计算从起始城市到最终目的地的总距离。
* @param g 航班图对象
* @param layOverVertex 中转城市对应的Vertex对象，其中包含了中转城市的标签和从起始城市到中转城市的距离。
* @param distanceToLayover 从起始城市到中转城市的距离。
*/
private static void showConnections(HWGraph g, Vertex layOverVertex, int distanceToLayover) {
// 获取中转城市的所有直接连接
ArrayList connectionsFromLayover = g.getConnections(layOverVertex.label);
if (connectionsFromLayover != null && !connectionsFromLayover.isEmpty()) {
System.out.println("中转城市 " + layOverVertex.label + " 的后续连接:");
for (Vertex connectedCity : connectionsFromLayover) {
// 计算从起始城市到最终目的地的总距离
int totalDistance = distanceToLayover + connectedCity.weight;
System.out.printf(" -> 目的地: %s (航段距离: %d, 总距离: %d)\n",
connectedCity.label, connectedCity.weight, totalDistance);
}
} else {
System.out.println("中转城市 " + layOverVertex.label + " 没有找到后续连接。");
}
}
// 废弃或删除原有的connect方法，因为它不再适用
// private static void connect(String key, ArrayList value) { ... }
// 创建图数据 (保持不变)
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");
// --- now add connections
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;
}
} 4.2 Vertex.java 和 HWGraph.java (保持不变)
这两个文件不需要修改，它们提供了图的基本数据结构和操作。
Vertex.java:
public class Vertex {
String label;
int weight;
public Vertex(String label, int weight) {
this.label = label;
this.weight = weight;
}
}HWGraph.java:
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Set;
public class HWGraph {
public HashMap> graphMap = new HashMap<>();
public void addVertex( String label ){
ArrayList items = new ArrayList<>();
graphMap.put( label, items);
}
public void removeVertex( String label ){
// 实现删除顶点逻辑，如果需要
}
public void addEdge( String label1, Vertex v){
// 注意：这是一个有向图的添加边方式
// 如果需要无向图，则需要同时添加从v.label到label1的边
graphMap.get(label1).add(v);
}
ArrayList getConnections( String label){
return graphMap.get(label);
}
Set getKeys( ){
Set keys = graphMap.keySet();
return keys;
}
Vertex getThisVertex( String startCity, String destCity){
ArrayList destCities = this.getConnections( startCity);
if (destCities == null) { // 如果起始城市没有连接，或者起始城市不存在
return null;
}
for( Vertex v : destCities){
if ( v.label.equalsIgnoreCase(destCity)){
return v;
}
}
return null; // 如果在起始城市的连接中没有找到目标城市
}
} 5. 运行示例与输出
假设起始城市为 Chicago，用户输入中转城市为 New York。
用户交互：
请选择一个中转城市 (Chicago, Dallas, Atlanta, New York, Houston, Orlando): New York
程序输出：
从起始城市: Chicago 经中转城市: New York (距离: 790) 的后续连接及总距离: 中转城市 New York 的后续连接: -> 目的地: Houston (航段距离: 1647, 总距离: 2437) -> 目的地: Orlando (航段距离: 1080, 总距离: 1870)
解释：
- Chicago 到 New York 的距离是 790。
- New York 到 Houston 的距离是 1647，总距离为 790 + 1647 = 2437。
- New York 到 Orlando 的距离是 1080，总距离为 790 + 1080 = 1870。
这与预期的输出（例如 Chicago -> New York -> Orlando is 790+1080 = 1870）完全一致。
6. 注意事项与总结
- 错误处理：在 main 方法中，我们添加了对 layOverVertex 是否为 null 的检查。如果用户输入的中转城市无效，或者从起始城市无法直达中转城市，getThisVertex 将返回 null，程序会给出相应的提示。
- 图的类型：当前实现的是有向图（addEdge 只添加一个方向的边）。如果需要无向图，addEdge 方法需要修改为在两个方向都添加边。
- 路径查找：本教程仅解决了显示中转城市直接连接的问题。如果需要查找从起始城市到任意目的地的完整路径（可能包含多个中转），则需要实现更复杂的图算法，如Dijkstra算法或广度优先搜索（BFS）。
- 代码可读性：通过将核心逻辑集中到 showConnections 方法中，并明确其参数的含义，代码的可读性和维护性得到了显著提升。
通过上述优化，我们成功地解决了在Java中处理航班中转连接和总距离计算的问题，使得程序能够根据用户需求，准确地展示特定中转城市的后续航班信息及其累计总距离。
