具有固定停止距离的宽度优先搜索

Question

我正在查看一个图形问题，其中给出了一个源节点，并且需要查找距离固定的所有其他节点，其中节点之间的每个边都具有统一的成本。因此，我使用标准的FIFO队列技术实现了宽度优先的搜索，但是以固定距离停止BFS会导致问题。

如果我使用DFS，我可以在每个递归调用中传递当前深度，但是我不能在这里做到这一点。我无法修改图的节点以保留额外的参数（距离）。任何建议或参考？

Answer 1

只需使用两个队列并在它们之间来回跳动。每次你从一个切换到另一个时，你的深度计数加1。

要精心...

保持“活动”队列和“无效”的队列。

从活动队列中弹出一个节点。将其邻居添加到不活动的队列中。重复，直到活动队列为空。然后交换队列。

这保持不变，即如果到活动队列中所有节点的距离为d，则到非活动队列中所有节点的距离为d+1。足够容易跟踪和停止，当你想要的。

Answer 2

您可以将深度传递给您放入队列中的值。您还可以保留一个单独的阵列来存储您到达每个节点的深度。

Answer 3

将您传递的顶点与距离BFS源的距离一起进行封装。

另一种可能性是只标记队列中的顶点;通常用于图表的框架允许您为图表的元素分配权重，这是您可以用于您的目的的一种机制。

最后一种可能性是在BFS的一个层次的边界已经完全处理之后，将实际上不在图中的标记顶点插入队列中，以便知道何时开始新的BFS深度级别。这将使你的队列看起来像v u w x y MARKER s t j l k，所有这些都是图的顶点，除了MARKER。