我正在研究一个图问题，其中给定了一个源节点，并且需要找到所有其他节点直到固定距离，其中节点之间的每条边都有统一的成本。因此，我使用标准 FIFO 队列技术实现了广度优先搜索，但是在固定距离处停止 BFS 会给我带来问题。
如果我使用的是 DFS，我可以通过每个递归调用传入当前深度，但我不能在这里这样做。我也无法修改图形的节点以保留额外的参数（距离）。有什么建议或参考吗？
问问题
964 次
3 回答
3
只需使用两个队列并在它们之间来回反弹。每次从一个切换到另一个时，将深度计数加一。
详细说明...
维护一个“活动”队列和一个“非活动”队列。
从活动队列中弹出一个节点。将其邻居添加到非活动队列。重复直到活动队列为空。然后交换队列。
这保持了如果到活动队列中d所有节点的距离是，则到非活动队列中所有节点的距离是不变的d+1。很容易跟踪并在需要时停止。
于 2013-03-08T21:14:15.093 回答
2
您可以将深度传递给您放入队列的值。您还可以保留一个单独的数组来存储您到达每个节点的深度。
于 2013-03-08T21:16:15.673 回答
1
将您传递的顶点及其与 BFS 源的距离封装在一起。
另一种可能性是只标记队列中的顶点；通常，图的框架允许您为图的元素分配权重，这是一种可以用于您的目的的机制。
最后一种可能性是在完全处理 BFS 的一个级别的边界之后将实际上不在图中的标记顶点插入队列中，以便您知道新级别的 BFS 深度何时开始。这将使您的队列看起来像v u w x y MARKER s t j l k所有这些都是图的顶点，除了MARKER.
于 2013-03-08T21:17:55.367 回答