java - 如何通过图的广度优先搜索获取路径中的所有节点

Question

假设我们有一个像这样的简单图表:

使用深度优先搜索很容易找到从起始节点到结束节点的路径，但在尝试使用广度优先搜索做同样的事情时我陷入了困境。我的代码如下:

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

private List<String> getPathBreadth(Node start, Node destination, HashSet<String> visited, Queue<Node> queue) {
    List<String> path = new ArrayList<String>();
    if (start == destination) {
        path.add(start.name);
        return path;
    }
    visited.add(start.name);
    queue.offer(start);
    while (queue.size() > 0) {
        Node cur = queue.poll();
        for (String friend : cur.friends) {
            if (visited.contains(friend)) {
                continue;
            }
            visited.add(friend);
            if (getNode(friend) == destination) {
                path.add(friend); // I got the final node, I could also add cur, but how do I get the previous nodes along the path
                return path;
            }
            queue.offer(getNode(friend));
        }
    }
    return path;
}

假设我们想要从 John 到 Linda，所以我希望返回类似 [Linda, Robert, John] 或 [Linda, Patrica, John] 的东西，但我现在能做的最好的就是获取最后一个和倒数第二个节点。在本例中，他们是 Linda 和 Robert。如何获取路径上所有先前的节点？

Answer 1

为了使代码可用，请添加Node定义和树(测试数据)。 (参见mcve)。
我认为问题出在这里:

if (getNode(friend) == destination) {
                path.add(friend); 
                return path;
 }

您添加到最后一个路径的唯一节点。尝试:

path.add(friend);     
if (getNode(friend) == destination) {                
     return path; //or better: break;
}

不幸的是，我无法运行并检查它。

附注:
visited.add(friend) 如果此集合尚未包含friend，则返回 true
所以:

if (visited.contains(friend)) {
   continue;
}
visited.add(friend);

可以替换为

 if (! visited.add(friend)) {
     continue;
 }