如何在图的广度优先搜索（BFS）中获取路径上的所有节点

这个问题我太熟啦！你现在的BFS代码只能拿到路径最后两个节点，核心原因是没记录每个节点的来路——就像你走到了终点，但忘了自己是怎么一步步过来的，自然没法还原整条路线。

问题根源 #

你当前的代码在找到目标节点时，只能拿到当前的friend和cur节点，但前面的节点信息完全丢失了，因为没有存储每个节点是被哪个节点发现的（也就是前驱节点）。

解决方案：给每个节点记录"前驱" #

我们只需要新增一个前驱映射表（比如Map<String, String>），每次访问新节点时，记录它的父节点（发现它的那个节点）。等找到终点后，从终点往回遍历前驱映射表，就能还原出完整路径，最后再根据需求调整顺序即可。

修改后的完整代码 #

我把原来的递归结构改成了更符合BFS逻辑的迭代版本（递归其实不太适合BFS的层级遍历），同时加入了前驱记录：

import java.util.*;

public class YourGraphClass {
    // 假设你已经有Node类和getNode方法
    private class Node {
        String name;
        List<String> friends;
        // 构造方法等...
    }
    
    private Node getNode(String name) {
        // 你的getNode实现...
        return null;
    }

    public List<String> getPathBreadth(String name1, String name2) {
        Node node1 = getNode(name1);
        Node node2 = getNode(name2);
        
        if (node1 == null || node2 == null) {
            return null;
        }

        // 核心：用Map记录每个节点的前驱节点名字
        Map<String, String> parentMap = new HashMap<>();
        HashSet<String> visited = new HashSet<>();
        Queue<Node> queue = new LinkedList<>();

        // 初始化起点
        visited.add(node1.name);
        queue.offer(node1);
        parentMap.put(node1.name, null); // 起点没有前驱

        boolean found = false;
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            
            // 提前判断当前节点是否是终点
            if (cur == node2) {
                found = true;
                break;
            }

            for (String friendName : cur.friends) {
                if (!visited.contains(friendName)) {
                    visited.add(friendName);
                    Node friendNode = getNode(friendName);
                    // 记录当前节点是friend的前驱
                    parentMap.put(friendName, cur.name);
                    queue.offer(friendNode);

                    // 找到终点后提前退出循环，优化性能
                    if (friendNode == node2) {
                        found = true;
                        queue.clear();
                        break;
                    }
                }
            }
            if (found) break;
        }

        // 没找到路径的情况
        if (!found) {
            return new ArrayList<>();
        }

        // 从终点回溯到起点，构建路径
        List<String> path = new ArrayList<>();
        String currentName = name2;
        while (currentName != null) {
            path.add(currentName);
            currentName = parentMap.get(currentName);
        }

        // 如果你需要起点在前的顺序（比如[John, Robert, Linda]），就打开下面这行
        // Collections.reverse(path);
        
        return path;
    }
}

关键逻辑说明 #

1. 前驱映射表parentMap：每个键是节点名字，值是它的前驱节点名字，相当于给每个节点记下来“我是从哪个节点过来的”。
2. 路径回溯：找到终点后，从name2（比如Linda）开始，通过parentMap依次拿到它的前驱（Robert），再拿到Robert的前驱（John），直到起点，这样就得到了[Linda, Robert, John]的路径。
3. 路径顺序调整：如果需要起点在前的路径，只需要调用Collections.reverse(path)反转列表即可。

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