Java中BFS算法如何通过prev数组回溯还原原始路径

核心原理 #

prev数组的存储逻辑是prev[i] = j代表节点i的前驱是j，源点的前驱会被初始化为无效值（通常用-1表示）。路径还原需要从目标节点反向回溯到源节点，再反转结果得到正向路径。

具体步骤 #

• 先判断目标节点是否等于源节点，若是直接返回仅包含源节点的路径
• 从目标节点开始，依次将当前节点加入临时路径列表，再将当前节点替换为它的前驱prev[当前节点]
• 循环直到当前节点为无效值（-1）停止
• 检查临时路径的最后一个元素是否为源节点：
  • 若是：反转临时列表，得到从源点到目标点的正向路径
  • 若不是：说明源点到目标点无可达路径，返回空列表即可

Java 示例代码 #

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class BFSPathRestore {
    /**
     * 从prev数组还原源点到目标点的路径
     * @param prev 前驱数组，prev[i]是节点i的前驱，源点的prev值为-1
     * @param source 源点编号
     * @param target 目标点编号
     * @return 源点到目标点的路径，不可达返回空列表
     */
    public List<Integer> restorePath(int[] prev, int source, int target) {
        List<Integer> path = new ArrayList<>();
        // 目标和源是同一个节点的情况
        if (source == target) {
            path.add(source);
            return path;
        }
        // 从目标反向回溯
        int cur = target;
        while (cur != -1) {
            path.add(cur);
            cur = prev[cur];
        }
        // 反转得到正向路径
        Collections.reverse(path);
        // 校验路径起点是否是源点，不是则说明不可达
        if (path.get(0) != source) {
            return new ArrayList<>();
        }
        return path;
    }

    // 测试示例
    public static void main(String[] args) {
        BFSPathRestore demo = new BFSPathRestore();
        // 假设prev数组：节点0是源点，路径0→1→3→5，0→2→4
        int[] prev = {-1, 0, 0, 1, 2, 3};
        int source = 0;
        int target = 5;
        List<Integer> path = demo.restorePath(prev, source, target);
        // 输出路径：[0, 1, 3, 5]
        System.out.println(path);
    }
}

补充说明 #

如果你的节点不是整数编号，可以把prev数组替换为HashMap<节点类型, 节点类型>来存储前驱映射，回溯逻辑完全一致，只需要调整判断无效值的逻辑即可。

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