图遍历-查找和返回最短距离

Question

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

我的程序工作起来就像维基百科页面的psuedo代码

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

因此，我一直在思考如何跟踪所做的步骤数，但我遇到了java的局限性(我对java的工作原理不是很了解)。我最初的想法是创建一些队列，该队列由我创建的存储步骤和节点的数据类型组成，当它遍历图形时，它会跟踪这些步骤。如果达到了目标，只需返回步骤即可。

我不知道如何在java中做到这一点，所以我不得不摆脱这个想法，我转向使用摇摇欲坠的队列=队列的新LinkedList实现。所以基本上我认为这是一个普通的整数队列，我不能得到我的数据类型来使用它。

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

虽然这不起作用，但我有很多问题，我实际上不确定为什么。

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

我的任何想法都接近了吗?我如何才能让它们发挥作用？我相信有一种标准而简单的方法可以做到这一点，但我还不够聪明。

Answer 1

代码会有所帮助。您使用什么数据结构来存储部分或候选解决方案？您说您使用队列来存储要检查的节点，但实际上存储在队列中的对象应该包装一些结构(例如List)，以指示遍历的节点到达要检查的节点。因此，不是将简单的Node存储在队列中，而是需要一些更复杂的对象来提供了解到该点的完整路径所需的信息。一个简单的节点将只有关于它自己和它的子节点的信息。但如果你正在检查节点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);

Answer 2

为了在遍历过程中跟踪距离，最简单的解决方案是添加一个简单的数组(如果顶点不是由整数索引的，则添加一个贴图)。

伪码算法如下：

shortest_path(g, src, dst):
  q = new empty queue
  distances = int array of length order of g
  for i = 0 to order: distances[i] = -1
  distances[src] = 0
  enqueue src in q
  while q is not empty:
    cur = pop next element in q
    if cur is dst: return distances[dst]
    foreach s in successors of cur in g:
      if distances[s] == -1:
        distances[s] = distances[cur] + 1
        enqueue s in q
  return not found

注:图的阶数是顶点的数目

你不需要特殊的数据结构，队列可以只包含顶点的id (可能是整数)。在Java语言中，LinkedList类实现了queue接口，因此它是一个很好的队列候选者。对于距离数组，如果您的顶点由整数标识，则一个整数数组就足够了，否则您需要一种映射。

您也可以使用单独的布尔数组或集合来分离顶点污染(我的algo中的-1 )，但这并不是真正必要的，而且会浪费一些空间。

如果需要路径，也可以使用简单的父数组:对于遍历中存储其父数组的每个顶点，只需在将后续顶点排队时添加parents = cur即可。然后检索路径(以相反的顺序)很简单，如下所示：

path = new empty stack
cur = dst
while cur != src:
  push cur in path
  cur = parent[cur]
push src in path

这就是…