Java递归航班路径查询：移除额外help参数的实现方案

需要实现符合以下签名的Java递归函数，用于找出从出发国到目的国的所有可行航班路径，同时移除原代码中多余的String help参数：

List<List<String>> printAllPathsUtil(String src, String d, List<Flight> localPathList)

原代码中help参数用于存储初始出发国以验证路径起点合法性，我们可以通过重构邻接表结构、调整递归逻辑来移除该参数，同时保证功能正确。

修改方案说明 #

1. 重构邻接表存储：将原有的ArrayList<Flight>改为Map<String, List<Flight>>，按出发地分组存储航班，方便快速获取某一地点的所有后续航班。
2. 移除冗余参数：利用递归的初始状态（localPathList为空）确定初始出发国，无需额外参数传递。
3. 修正路径遍历逻辑：遍历当前出发地的所有航班，通过回溯法探索所有可能路径，确保不遗漏可行路线。
4. 符合函数签名：最终的printAllPathsUtil函数完全匹配指定签名，返回所有路径的字符串列表。

修改后的完整代码 #

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FlightPathFinder {
    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");

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

        List<Flight> localPathList = new ArrayList<>();
        List<List<String>> allPaths = allFlights.printAllPathsUtil("ISRAEL", "ROMANIA", localPathList);
        
        // 打印所有路径的字符串形式
        System.out.println("\n所有路径的字符串列表：");
        for (List<String> path : allPaths) {
            System.out.println(String.join(" -> ", path));
        }
    }
}

class Flight {
    String from;
    String to;

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

    public void print() {
        System.out.print(from + " -> " + to);
    }
}

class AllFlight {
    // 邻接表：key为出发地，value为该出发地的所有航班
    private Map<String, List<Flight>> adj;
    // 存储所有找到的路径（字符串列表形式）
    private List<List<String>> resultPaths;

    public AllFlight() {
        adj = new HashMap<>();
        resultPaths = new ArrayList<>();
    }

    // 添加航班到邻接表
    public void addEdge(Flight flight) {
        adj.computeIfAbsent(flight.from, k -> new ArrayList<>()).add(flight);
    }

    public List<List<String>> printAllPathsUtil(String src, String d, List<Flight> localPathList) {
        // 初始化结果集（仅第一次调用时执行）
        if (resultPaths.isEmpty()) {
            resultPaths = new ArrayList<>();
        }

        // 获取当前出发地的所有航班
        List<Flight> flightsFromSrc = adj.getOrDefault(src, new ArrayList<>());
        
        for (Flight flight : flightsFromSrc) {
            // 将当前航班加入路径
            localPathList.add(flight);

            // 如果当前航班的目的地是目标国，记录这条路径
            if (flight.to.equals(d)) {
                System.out.println("找到可行路径：");
                printPath(localPathList);
                // 将Flight路径转换为字符串列表
                List<String> stringPath = new ArrayList<>();
                stringPath.add(localPathList.get(0).from);
                for (Flight f : localPathList) {
                    stringPath.add(f.to);
                }
                resultPaths.add(new ArrayList<>(stringPath));
            } else {
                // 递归探索后续路径
                printAllPathsUtil(flight.to, d, localPathList);
            }

            // 回溯：移除当前航班，探索其他分支
            localPathList.remove(localPathList.size() - 1);
        }

        return resultPaths;
    }

    private static void printPath(List<Flight> path) {
        for (int i = 0; i < path.size(); i++) {
            Flight v = path.get(i);
            v.print();
            if (i != path.size() - 1) {
                System.out.print(" -> ");
            }
        }
        System.out.println();
    }
}

代码说明 #

• 邻接表优化：使用Map<String, List<Flight>>存储航班，避免遍历整个列表查找航班，提升效率。
• 回溯法遍历：通过添加/移除航班实现回溯，确保探索所有可能的路径分支。
• 路径转换：将Flight类型的路径转换为字符串列表，符合函数返回值要求。
• 无冗余参数：无需help参数，通过递归初始状态和路径本身即可验证起点合法性，所有路径均从指定的src出发。

内容的提问来源于stack exchange，提问作者בז'ה