如何用递归函数在航班图中找出所有从起点到终点的路径（无需额外参数）

本文介绍如何设计一个纯递归的 java 方法，不依赖额外传参（如起始源点 `help`），而是通过类成员变量保存初始源点，从而正确遍历并返回所有从 `src` 到 `dest` 的航班路径。

在原始实现中，printAllPathsUtil(String help, String src, String d, List localPathList) 多余地将起始国家 help 作为参数逐层传递。这不仅违背了递归函数“自描述性”的设计原则，还导致逻辑混乱（如误删边、清空列表等副作用操作）。真正的递归路径搜索应聚焦于：当前所在节点（src）、目标节点（d）、已走路径（localPathList）以及全局不变的起点信息（用于路径合法性校验）。

解决方案是：将初始源点 src 提升为类的私有字段 origin，在首次调用前初始化，后续所有递归调用直接访问该字段，无需再传参。同时，必须修正原算法中的关键缺陷：

• ❌ 错误：用 f.stream().filter(...).findFirst() 随意取一条出边 —— 这会遗漏其他分支，无法枚举“所有路径”；
• ❌ 错误：f.remove(0) 和 localPathList.clear() 属于破坏性操作，污染共享状态，导致不可复现结果；
• ✅ 正确做法：对每个满足 flight.from.equals(src) 的航班，分支递归，并使用回溯（add → 递归 → remove）维护路径独立性。

以下是重构后的完整、健壮、可运行的实现：

import java.util.*;

class Flight {
    String from, to;
    Flight(String from, String to) {
        this.from = from;
        this.to = to;
    }
    @Override
    public String toString() {
        return from + " → " + to;
    }
}

class AllFlights {
    private final List flights = new ArrayList<>();
    private String origin; // ✅ 类成员：记录初始源点，替代 'help' 参数

    public void addEdge(Flight flight) {
        flights.add(flight);
    }

    // 主入口：初始化 origin 并启动递归
    public List> printAllPathsUtil(String src, String dest) {
        this.origin = src; // ✅ 仅在此处赋值一次
        List> result = new ArrayList<>();
        List path = new ArrayList<>();
        dfs(src, dest, path, result);
        return result;
    }

    // ✅ 纯递归核心：无 help 参数，使用 this.origin 校验路径起点
    private void dfs(String current, String dest, List path, List> result) {
        // 终止条件：到达目的地
        if (current.equals(dest)) {
            // 构建字符串路径：[from1, to1, to2, ..., toN]
            List stringPath = new ArrayList<>();
            stringPath.add(origin); // 起点
            for (Flight f : path) {
                stringPath.add(f.to);
            }
            result.add(new ArrayList<>(stringPath));
            return;
        }

        // 遍历所有从 current 出发的航班（DFS 分支）
        for (Flight flight : flights) {
            if (flight.from.equals(current)) {
                path.add(flight); // 选择
                dfs(flight.to, dest, path, result); // 探索
                path.remove(path.size() - 1); // 撤销（回溯）
    
        }
        }
    }
}

// 使用示例
class FlightDemo {
    public static void main(String[] args) {
        Flight f1 = new Flight("ISRAEL", "ROMANIA");
        Flight f2 = new Flight("ISRAEL", "HOLAND");
        Flight f3 = new Flight("ISRAEL", "LONDON");
        Flight f4 = new Flight("ISRAEL", "U.S.A");
        Flight f5 = new Flight("HOLAND", "LONDON");
        Flight f6 = new Flight("LONDON", "ROMANIA");

        AllFlights allFlights = new AllFlights();
        allFlights.addEdge(f1);
        allFlights.addEdge(f2);
        allFlights.addEdge(f3);
        allFlights.addEdge(f4);
        allFlights.addEdge(f5);
        allFlights.addEdge(f6);

        // ✅ 调用无额外参数的接口
        List> paths = allFlights.printAllPathsUtil("ISRAEL", "ROMANIA");

        System.out.println("Found " + paths.size() + " path(s):");
        for (int i = 0; i < paths.size(); i++) {
            System.out.println((i + 1) + ". " + String.join(" → ", paths.get(i)));
        }
    }
}

输出示例：

Found 3 path(s):  
1. ISRAEL → ROMANIA  
2. ISRAEL → HOLAND → LONDON → ROMANIA  
3. ISRAEL → LONDON → ROMANIA  

✅ 关键改进总结：

• 移除冗余参数 help，改用类成员 origin 保证起点信息全局可见且不可变；
• 使用标准 DFS + 回溯，确保穷举所有路径（而非随机单路径）；
• 路径构建清晰：以 origin 开头，依次追加每段航班的 to，形|成人|类可读的字符串序列；
• 无副作用操作（不修改 flights 列表、不全局清空路径），线程安全基础更扎实。

此设计符合递归函数“职责单一、参数精简、状态内聚”的最佳实践，可直接集成至图遍历工具类中。