固定停止距离的广度优先搜索
我正在研究一个图问题，其中给定了一个源节点，需要找到距离固定的所有其他节点，其中节点之间的每条边都有一个统一的代价。因此，我使用标准FIFO队列技术实现了广度优先搜索，但在固定距离停止BFS会给我带来问题。
如果我使用DFS，我可以在每次递归调用时传递当前深度，但是在这里我不能这样做。我也不能修改图中的节点来保留一个额外的参数(距离)。有什么建议或者参考吗？
共有3个答案
封装传递到一起的顶点及其与BFS源的距离。
另一种可能性是只标记队列中的顶点；通常图的框架允许您为图的元素分配权重，这是一种可以用于您的目的的机制。
最后一种可能是在一个级别的BFS的边界已完全处理后，将一个实际上不在图中的标记顶点插入队列，以便您知道何时开始新的BFS深度级别。这将使您的队列看起来像＜code＞v u w x y MARKER s t j l k
您可以将深度传递给您放在队列中的值。您还可以保留一个单独的数组来存储您到达每个节点的深度。
只需使用两个队列，并在它们之间来回跳转。每次从一个切换到另一个时，将深度计数增加一。
详细说明...
维护一个“活动”队列和一个“非活动”队列。
从活动队列中弹出一个节点。将其邻居添加到非活动队列中。重复此操作，直到活动队列为空。然后交换队列。
这保持不变，即如果到活动队列中的所有节点的距离为d，则到非活动队列中所有节点的间距为d1。很容易跟踪并在需要时停止。
-
主要内容：深度优先搜索（简称“深搜”或DFS）,广度优先搜索,总结前边介绍了有关图的 4 种存储方式，本节介绍如何对存储的图中的顶点进行遍历。常用的遍历方式有两种： 深度优先搜索和 广度优先搜索。 深度优先搜索（简称“深搜”或DFS） 图 1 无向图 深度优先搜索的过程类似于树的先序遍历，首先从例子中体会深度优先搜索。例如图 1 是一个无向图，采用深度优先算法遍历这个图的过程为： 首先任意找一个未被遍历过的顶点，例如从 V1 开始，由于 V1 率先访问过了，所以
-
我正在研究BFS算法，我有一个关于如何将相邻节点插入队列的问题。 例如，假设我们正在处理一个无向图，我们希望执行BFS来输出图的内容，那么我们如何知道在从队列中取出一个初始节点后，相邻节点以什么顺序插入到队列中呢？还有，有没有办法修改邻居节点插入队列的方式？ 任何帮助都将不胜感激，谢谢。
-
本文向大家介绍什么是广度优先搜索？相关面试题，主要包含被问及什么是广度优先搜索？时的应答技巧和注意事项，需要的朋友参考一下 类似树的按层遍历，其过程为：首先访问初始点Vi，并将其标记为已访问过，接着访问Vi的所有未被访问过可到达的邻接点Vi1、Vi2……Vit，并均标记为已访问过，然后再按照Vi1、Vi2……Vit的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依此类推，直到图
-
在继续使用其他图算法之前，让我们分析广度优先搜索算法的运行时性能。首先要观察的是，对于图中的每个顶点 $$|V|$$ 最多执行一次 while 循环。因为一个顶点必须是白色，才能被检查和添加到队列。这给出了用于 while 循环的 $$O(V)$$。嵌套在 while 内部的 for 循环对于图中的每个边执行最多一次，$$|E|$$。原因是每个顶点最多被出列一次，并且仅当节点 u 出队时，我们才检
-
通过构建图，我们现在可以将注意力转向我们将使用的算法来找到字梯问题的最短解。我们将使用的图算法称为“宽度优先搜索”算法。宽度优先搜索（BFS）是用于搜索图的最简单的算法之一。它也作为几个其他重要的图算法的原型，我们将在以后研究。 给定图 G 和起始顶点 s，广度优先搜索通过探索图中的边以找到 G 中的所有顶点，其中存在从 s 开始的路径。通过广度优先搜索，它找到和 s 相距 k 的所有顶点，然后找
-
我正在尝试在有向图上实现BFS。我完全确定我的算法是正确的，但是，下面的代码段返回错误： 图表。CPP文件: 以及在以下方面的实际BFS实施： 因此，除了源节点之外，队列中的其他节点都给出了错误的邻接列表。虽然队列顺序运行良好，但队列中的节点给出了错误的邻接。 我不确定为什么会发生这种情况，虽然我怀疑这是由于按值复制节点而不是引用。 这是我在很长一段时间后的CPP计划，所以如果我错过了什么，请启发