cle*_*ine 14 search graph path breadth-first-search
我试图在图形中的两个节点之间找到路径,其中边缘未加权.
我正在使用广度优先搜索,它在找到目标时停止,以便找到路径的存在,但我不确定如何获取路径本身.
我试着查看访问过的节点列表,但这似乎没有帮助.我看到有人用prolog回答这个问题,但我是一名C++程序员.
我也看了一下Dijkstras algorithm,但这似乎过度杀人,因为简单的广度优先搜索让我几乎全程.
如何使用广度优先搜索获得2个节点之间的路径？
小智 23
在节点结构中,添加一个名为parentNodepath 的变量,该变量是路径中该节点的父节点.最后,您可以通过向后遍历目标节点来检索路径.