Java航班路径查询程序结果过滤与优化方案咨询

现有代码的问题与过滤修正 #

你的代码核心逻辑是反向从终点往起点回溯，但没有设置正确的终止条件，导致输出了大量未完成的中间路径。要过滤出有效路径，我们需要做这几点调整：

1. 只有当回溯到起点城市时，才认为是一条完整有效路径
2. 把反向的路径反转成起点->...->终点的正确格式
3. 移除递归过程中对中间列表ls的打印，只输出最终有效路径

修改后的getFlights方法如下：

private static void getFlights(List<Flights> flights, String start, String current, String path) {
    // 终止条件：当前城市是起点，说明找到了完整反向路径，反转后输出
    if (current.equals(start)) {
        // 拆分路径并反转
        String[] cities = path.split("-");
        StringBuilder sb = new StringBuilder();
        for (int i = cities.length - 1; i >= 0; i--) {
            sb.append(cities[i]);
            if (i != 0) sb.append(" -> ");
        }
        System.out.println(sb.toString());
        return;
    }

    List<String> prevCities = new ArrayList<>();
    for (Flights f : flights) {
        // 找到能飞到当前城市的出发城市
        if (f.containsDestination(current)) {
            prevCities.add(f.getStart());
        }
    }

    for (String prev : prevCities) {
        // 递归回溯，避免重复循环（示例场景暂时无需额外判断，复杂场景可加已访问集合）
        getFlights(flights, start, prev, path + "-" + prev);
    }
}

同时修改main方法里的调用（原调用逻辑无需改动，但内部逻辑已优化）：

getFlights(flights, start, end, end);

这样就能只输出A -> B -> H和A -> B -> C -> E -> G -> H这两条有效路径了。

更优的实现方案 #

反向回溯虽然能解决问题，但逻辑不够直观，而且容易出现循环路径（比如A->D->A）。更推荐用正向深度优先搜索（DFS），从起点出发，遍历所有可达的城市，记录路径，当到达终点时保存结果，同时通过记录已访问城市避免循环。

优化点：

1. 用Map<String, List<String>>替代自定义Flights类，存储航班映射，更简洁高效
2. 正向DFS遍历，逻辑更符合人类思考路径的习惯
3. 加入已访问集合，防止循环路径（比如A->D->A->D...无限循环）

完整实现代码：

import java.util.*;

public class FlightPathFinder {
    public static void main(String[] args) {
        // 构建航班映射：出发城市 -> 可达的目的地列表
        Map<String, List<String>> flightMap = new HashMap<>();
        flightMap.put("A", Arrays.asList("B", "D"));
        flightMap.put("B", Arrays.asList("C", "D", "H"));
        flightMap.put("D", Arrays.asList("A"));
        flightMap.put("C", Arrays.asList("E"));
        flightMap.put("E", Arrays.asList("F", "G"));
        flightMap.put("G", Arrays.asList("H"));

        String start = "A";
        String end = "H";
        List<String> resultPaths = new ArrayList<>();

        // 启动DFS，初始路径是起点，已访问集合包含起点
        dfs(flightMap, start, end, new ArrayList<>(Collections.singletonList(start)), new HashSet<>(Collections.singleton(start)), resultPaths);

        // 输出结果
        for (String path : resultPaths) {
            System.out.println(path);
        }
    }

    private static void dfs(Map<String, List<String>> flightMap, String current, String end, List<String> currentPath, Set<String> visited, List<String> result) {
        // 如果当前城市是终点，把路径转换成指定格式加入结果
        if (current.equals(end)) {
            result.add(String.join(" -> ", currentPath));
            return;
        }

        // 如果当前城市没有航班，直接返回
        if (!flightMap.containsKey(current)) {
            return;
        }

        // 遍历当前城市的所有目的地
        for (String next : flightMap.get(current)) {
            // 如果未访问过该城市，继续DFS
            if (!visited.contains(next)) {
                visited.add(next);
                currentPath.add(next);
                dfs(flightMap, next, end, currentPath, visited, result);
                // 回溯：移除当前城市，恢复状态
                currentPath.remove(currentPath.size() - 1);
                visited.remove(next);
            }
        }
    }
}

这段代码的优势：

• 逻辑清晰，正向遍历符合人类思考路径的习惯
• 自动处理循环问题（比如A->D->A的循环会被已访问集合拦截）
• 代码更简洁，用标准集合类替代自定义类，维护成本更低

内容的提问来源于stack exchange，提问作者robin