如何使用广度优先搜索获得2个节点之间的路径？ [英] How to get the path between 2 nodes using Breadth-First Search?

问题描述

我试图在图表中两个节点之间找到一个路径，其边缘是未加权的。

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

>

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

我也看了 Dijkstras算法，但这看起来好像过度杀人，因为一个简单的广度优先搜索几乎可以让我看到整个过程。

如何获取路径在2个节点之间使用宽度优先搜索？

解决方案

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

I am trying to find a path between two nodes in a graph, where the edges are unweighted.

I am using a Breadth First Search, which stops when it finds the target, in order to find the existence of a path, but I am not sure how to get the path itself.

I tried looking at the list of visited nodes, but this did not seem to help. I saw someone answer this question using prolog, but I am a C++ programmer.

I also looked at Dijkstras algorithm, but this seems like over kill, since a simple Breadth-first Search has got me almost the whole way.

How to get the path between 2 nodes using Breadth-First Search?

解决方案

In your node struct, you add a variable called parentNode which is the parent of that node in the path. In the end, you can retrieve the path by traversing from the goal node backward.

这篇关于如何使用广度优先搜索获得2个节点之间的路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！