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

本文介绍如何在不增加辅助参数的前提下，通过类成员变量保存初始源点，实现递归遍历有向航班图并返回所有合法路径的完整解决方案。

在原始代码中，printAllPathsUtil(String help, String src, String d, List localPathList) 多余地引入了 help 参数用于记录初始出发国（如 "ISRAEL"），但该值在整个递归调用链中恒定不变——这正说明它不属于递归状态变量，而应作为上下文常量提取为类的成员字段。

✅ 正确设计思路：用类状态替代冗余参数

我们将 help（即原始起点）提升为 all_flight 类的私有字段 origin，并在主入口方法（如 printAllPaths）中初始化。递归核心方法 printAllPathsUtil 仅保留真正变化的参数：当前节点 src、目标 d 和当前路径 localPathList。这样既符合函数签名要求，又保持逻辑清晰、无状态污染。

✅ 重构后的完整可运行代码（Java）

import java.util.*;

class Flight {
    String from;
    String to;

    public Flight(String from, String to) {
        this.from = from;
        this.to = to;
    }

    public void print() {
        System.out.println(from + " → " + to);
    }
}

class AllFlight { // 类名遵循 Java 命名规范（PascalCase）
    private final List flights = new ArrayList<>();
    private String origin; // ✅ 关键：用成员变量替代 help 参数

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

    // ✅ 入口方法：初始化 origin 并启动递归
    public List> printAllPaths(String src, String dest) {
        this.origin = src; // 一次性设定起点
        List> result = new ArrayList<>();
        List currentPath = new ArrayList<>();
        dfs(src, dest, currentPath, result);
        return result;
    }

    // ✅ 核心递归方法（无 help 参数！）
    private void dfs(String src, String dest, List currentPath, List> result) {
        // 终止条件：到达目的地
        if (src.equals(dest)) {
            // 构建字符串路径：from→to→...→dest
            List pathStr = new ArrayList<>();
            for (Flight f : currentPath) {
                pathStr.add(f.from);
            }
            pathStr.add(dest); // 补上终点
            result.add(new ArrayList<>(pathStr));
            return;
        }

        // 遍历所有从当前 src 出发的航班
        for (Flight flight : flights) {
            if (flight.from.equals(src)) {
                currentPath.add(flight);
                dfs(flight.to, dest, currentPath, result);
                currentPath.remove(currentPath.size() - 1); // 回溯
            }
        }
    }

    // 辅助：打印所有路径（用于调试）
    public void printAllPathsUtil(String src, String dest) {
        List> paths = printAllPaths(src, dest);
        System.out.println("Found " + paths.size() + " path(s):");
        for (int i = 0; i < paths.size(); i++) {
            System.out.println("Path " + (i + 1) + ": " + paths.get(i));
        }
    }
}

// 主程序示例
public class FlightPathDemo {
    public static void main(String[] args) {
        AllFlight allFlight = new AllFlight();

        allFlight.addEdge(new Flight("ISRAEL", "ROMANIA"));
        allFlight.addEdge(new Flight("ISRAEL", "HOLAND"));
        allFlight.addEdge(new Flight("ISRAEL", "LONDON"));
        allFlight.addEdge(new Flight("ISRAEL", "U.S.A"));
        allFlight.addEdge(new Flight("HOLAND", "LONDON"));
        allFlight.addEdge(new Flight("LONDON", "ROMANIA"));

        // ✅ 调用无额外参数的接口
        allFlight.printAllPathsUtil("ISRAEL", "ROMANIA");
        // 输出示例：
        // Path 1: [ISRAEL, ROMANIA]
        // Path 2: [ISRAEL, HOLAND, LONDON, ROMANIA]
        // Path 3: [ISRAEL, LONDON, ROMANIA]
    }
}

⚠️ 关键注意事项

避免全局/静态状态污染：原代码中使用 static int current 和 f.remove(0) 等操作破坏了数据结构稳定性，新版本完全基于传参与局部状态，线程安全且可重入。
回溯必须严谨：每次递归前 add()，返回前 remove()，确保 currentPath 始终反映当前递归深度的真实路径。
路径构建方式优化：返回的是 List>（如 [["ISRAEL","HOLAND","LONDON","ROMANIA"]]），而非 List，更符合题干“所有可能路径”的语义。
图结构说明：本解法默认航班为有向边，且允许多次访问同一国家（无环检测）。若需防环（如避免 A→B→A），可在 currentPath 中检查 flight.to 是否已存在。