1

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

我的程序像维基百科页面伪代码一样工作

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

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

我不知道如何在 java 中完成这项工作，所以我不得不摆脱这个想法，我继续使用那个不稳定的 Queue = 队列的新 LinkedList 实现。所以基本上我认为这是一个普通的整数队列，我无法使用我的数据类型来使用它。

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

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

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

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

4

2 回答 2

0

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

为了在遍历过程中跟踪距离，最简单的解决方案是添加一个简单的数组（如果顶点没有按整数索引，则添加一个地图）。

这是伪代码算法：

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 接口，因此它是您队列的理想选择。对于距离数组，如果您的顶点由整数标识，则整数数组就足够了，否则您需要一种地图。

您还可以使用单独的布尔数组或集合来分隔顶点污染（我的算法中的 -1），但这并不是必需的，并且会浪费一些空间。

如果你想要路径，你也可以用一个简单的父数组来做到这一点：对于每个顶点，你将其父节点存储在遍历中，只需在将后继者入队时添加 parent[s] = cur。然后检索路径（以相反的顺序）很简单，如下所示：

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

你来了……</p>

于 2017-07-22T18:31:57.673 回答