search - 如何使用广度优先搜索获取两个节点之间的路径？

Question

我想找一个 图中两个节点之间的路径 ，其中边是 未加权 .

我正在使用广度优先搜索，它在找到目标时停止，以便找到路径的存在，但我不确定如何获取路径本身。

我尝试查看访问过的节点列表，但这似乎没有帮助。
我看到有人用 prolog 回答这个问题，但我是 C++ 程序员。

我也看了Dijkstras algorithm ，但这似乎有点过头了，因为一个简单的广度优先搜索几乎让我受益匪浅。

如何使用广度优先搜索获取两个节点之间的路径？

Answer 1

在您的节点结构中，添加一个名为 parentNode 的变量。这是路径中该节点的父节点。最后，您可以通过从目标节点向后遍历来检索路径。