java - 使用 BFS 的 2 个节点之间的路径

Question

我编写了一个函数，用于计算是否可以使用 BFS 从源顶点到达目标顶点。现在我需要跟踪我用来到达顶点的路径。我想这应该是一个小调整，我们可以将节点添加到我的路径数组列表中。有人请帮帮我。

public Boolean isReachable(Node destination) {
    ArrayList<Node> visited = new ArrayList<>();
    LinkedList<Node> queue = new LinkedList<>();
    ArrayList<Node> path = new ArrayList<>();
    queue.add(this);

    while (queue.size() != 0) {
        Node source = queue.poll();

        for (Node node : source.adjacentNodes) {
            if (node.equals(destination))
                return true;

            if (!visited.contains(node)) {
                visited.add(node);
                queue.add(node);
            }

        }
    }
    return false;
}

Answer 1

您缺少 BFS 的两个部分。 BFS 用于查找节点之间的路径，但它也会尝试查找最短路径(但仅限于已搜索的节点)，因此通常会涉及成本值。由于您只关心节点是否已连接，因此您不需要此成本值。

缺少的第二部分是跟踪从队列中通向当前节点的父节点。请参阅此处编写的伪代码:https://en.wikipedia.org/wiki/Breadth-first_search请注意他们对 n.parent 和 n.distance 的使用。

在另一个数据结构中跟踪当前节点的父节点引用，或在 Node 对象内添加指向父节点的指针。然后，一旦当前节点等于目标节点，您就可以沿着父节点指针向后到达起始节点。这将为您提供从结束节点到开始节点的完整路径。

如果您想要从开始到结束的路径，您需要迭代父节点并将对它们的引用存储在列表或其他内容中，并在完成后反转列表。