graph - 有效地找到有向图中两个节点之间的某个路径上的所有节点

Question

我目前正在尝试找出一种有效的方法来查找有向图中两个节点（例如和）之间的某个路径上的所有节点。XY

我的第一个想法是从 X 运行 BFS，从 Y 运行 BFS，并获取访问节点的交集。请注意，我不需要枚举 X 和 Y 之间的所有路径，只需找到位于从 X 到 Y 的路径上的所有节点。

我的问题是，有没有更优化的方法来做到这一点？

Answer 1

可以通过获得更好的运行时间或使用更少的内存或找到一个好的解决方案来进行优化（有时局部最大值是可以的）。

您可以查看A* 搜索，看看这是否适用于您的问题。如果您可以应用它，您将节省内存并缩短运行时间。