带异常的Java递归函数实现：查找无重复节点的起止ID路径

Hey, 针对你的需求——找出两个节点间所有不重复经过节点的路径，我结合你给出的节点关系和部分代码，整理了完整的实现方案。

首先，先把你的节点邻接关系转换成代码里方便使用的结构，用Map<Integer, List<Integer>>存储：

// 定义节点的邻居关系
private static final Map<Integer, List<Integer>> NEIGHBORS = new HashMap<>();
static {
    NEIGHBORS.put(1, Arrays.asList(2, 5));
    NEIGHBORS.put(2, Arrays.asList(1, 3, 4, 5));
    NEIGHBORS.put(3, Arrays.asList(2, 5));
    NEIGHBORS.put(4, Arrays.asList(2));
    NEIGHBORS.put(5, Arrays.asList(1, 2, 3));
}

接下来完善你提到的递归函数。原函数的思路是对的，但需要补充完整逻辑，而且我们需要一个入口函数来初始化状态并收集所有可行路径（原函数看起来是返回单条路径，而我们需要所有符合条件的路径）：

完整递归实现 #

import java.util.*;

public class PathFinder {
    private static final Map<Integer, List<Integer>> NEIGHBORS = new HashMap<>();
    static {
        NEIGHBORS.put(1, Arrays.asList(2, 5));
        NEIGHBORS.put(2, Arrays.asList(1, 3, 4, 5));
        NEIGHBORS.put(3, Arrays.asList(2, 5));
        NEIGHBORS.put(4, Arrays.asList(2));
        NEIGHBORS.put(5, Arrays.asList(1, 2, 3));
    }

    // 入口函数：初始化已访问列表和结果集合，启动递归
    public static List<List<Integer>> findAllPaths(int start, int end) {
        List<List<Integer>> allPaths = new ArrayList<>();
        searchHops(start, end, new ArrayList<>(), allPaths);
        return allPaths;
    }

    // 递归核心函数：探索路径并收集结果
    private static void searchHops(int from, int to, List<Integer> seen, List<List<Integer>> allPaths) {
        // 标记当前节点为已访问
        seen.add(from);

        try {
            // 到达目标节点，保存当前路径的副本（必须新创建列表，避免后续回溯修改）
            if (from == to) {
                allPaths.add(new ArrayList<>(seen));
                return;
            }

            // 遍历当前节点的所有邻居
            for (int neighbor : NEIGHBORS.get(from)) {
                // 跳过已访问的节点，防止路径中出现重复节点
                if (!seen.contains(neighbor)) {
                    // 递归探索邻居节点
                    searchHops(neighbor, to, seen, allPaths);
                }
            }
        } finally {
            // 回溯：移除当前节点，让它能被其他路径再次访问
            seen.remove(seen.size() - 1);
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> paths = findAllPaths(1, 3);
        System.out.println("所有可行路径：");
        paths.forEach(System.out::println);
        // 输出结果：[1, 2, 3]、[1, 5, 3]
    }
}

关键逻辑说明 #

• 邻接表存储：用Map关联每个节点和它的邻居，让我们能快速获取任意节点的邻居列表。
• 递归与回溯：
  • 每次进入递归，先把当前节点加入seen列表，避免后续重复访问。
  • 如果当前节点就是目标，就把当前路径的副本存入结果集合——这里必须创建新列表，因为seen列表会在回溯时被修改。
  • 遍历邻居时，只对未访问过的节点递归，保证路径无重复节点。
  • 回溯操作：在finally块移除当前节点，确保递归返回后，该节点可以被其他路径使用，这是实现多路径探索的关键。
• 入口函数：负责初始化结果集合和已访问列表，让递归函数可以直接开始工作。

针对你提供的原代码调整 #

你提到的原函数List<Integer> searchHops(int from, int to, List<Integer> seen)更偏向单条路径的查找，而我们需要收集所有符合条件的路径，所以调整为void类型并传入结果集合。如果想保留原函数的返回风格，也可以修改为返回路径列表，但上面的实现更高效，因为避免了重复创建列表。

运行这段代码，就能得到你预期的两条路径，完全满足你的需求。

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