java - 图遍历——查找并返回最短距离

Question

我在一个程序中使用广度优先搜索，该程序试图查找并返回未加权有向图上两个节点之间的最短路径。

我的程序的工作方式类似于维基百科页面伪代码

该算法使用队列数据结构来存储遍历图时的中间结果，如下所示: 将根节点入队 将节点出队并检查它 如果在此节点中找到要查找的元素，则退出搜索并返回结果。 否则将尚未发现的任何后继节点(直接子节点)放入队列。 如果队列为空，则图表上的每个节点都已被检查 - 退出搜索并返回“未找到”。 如果队列不为空，则从步骤 2 开始重复。

所以我一直在考虑如何跟踪所做的步骤数，但是我遇到了java的限制(我不太了解java的工作原理)。我最初认为我可以创建一些由我创建的数据类型组成的队列，用于存储步骤和节点，并且当它遍历图形时，它会跟踪步骤。如果达到目标，只需返回步骤即可。

我不知道如何在java中实现这个工作，所以我不得不放弃这个想法，然后我继续使用那个奇怪的 Queue = new LinkedList 队列实现。所以基本上我认为它是一个普通的整数队列，我无法获得我制作的数据类型来使用它。

所以现在我必须找到一种更基本的方法，所以我尝试使用一个简单的计数器，但这不起作用，因为遍历算法在到达最短路径之前会搜索许多路径，所以我有了一个想法。我添加了第二个跟踪步数的队列，并添加了几个计数器。每当将节点添加到第一个队列时，我都会添加到计数器，这意味着我知道我正在检查新节点，因此我距离不远。检查完所有这些后，我可以增加步计数器，并且每当将节点添加到第一个队列时，我都会将步值添加到步队列中。步骤队列的管理方式与节点队列类似，因此当找到目标节点时，相应的步骤应该是要出队的步骤。

但这不起作用，我遇到了很多问题，我实际上不确定为什么。

我在 panic 和沮丧中删除了大部分代码，但如果有人需要我，我将开始尝试重新创建它并将其发布在这里。

我的想法是否接近？我怎样才能让它们发挥作用？我确信有一种标准且简单的方法可以做到这一点，但我不够聪明，看不到。

Answer 1

代码会有帮助。您使用什么数据结构来存储部分或候选解决方案？您说您使用队列来存储要检查的节点，但实际上存储在队列中的对象应该包装一些结构(例如List)，该结构指示遍历的节点以到达要检查的节点。因此，队列中不需要存储简单的节点，而是需要一些更复杂的对象来提供了解到达该点的完整路径所需的信息。一个简单的节点只有关于它自己和它的子节点的信息。但是，如果您正在检查节点 X，您还需要知道如何到达节点 X。仅仅知道节点 X 是不够的，(据我所知)了解到达节点 X 的路径的唯一方法是将路径存储在表示“部分解决方案”或“候选解决方案”的对象中。如果这样做了，那么找到路径的长度就很简单了，因为它只是这个列表(或选择的任何数据结构)的长度。希望我在这里说得有道理。如果没有，请发布代码，我会看一下。

编辑

这些代码有助于说明我的意思(它们绝不是完整的):

public class Solution {
    List<Node> path;
}

Queue<Solution> q;

不是

Queue<Node> q;

编辑2

如果您需要的只是路径的长度，而不是路径本身，那么请尝试如下操作:

public class Solution {
    Node node; // whatever represents a node in you algorithm.
    int len; // the length of the path to this node.
}

// Your queue:
LinkedList<Solution> q;

有了这个，在将候选解决方案(节点)排队之前，您可以执行以下操作:

Solution sol = new Solution();
sol.node = childNodeToEnqueue;
sol.len = parentNode.len + 1;
q.add(sol);