问题标签 [breadth-first-search]

我正在尝试制作一个迭代器，该迭代器对特定文件夹中的所有文件和文件夹执行广度优先遍历。我已经用深度优先遍历完成了这个，它返回，例如：

等等

现在我正在尝试制作一个程序，该程序将返回广度优先的结果：（或逐级）

对于相同的层次结构。但是，我遇到了一个绊脚石：假设我希望这些以正确的顺序发生（特别是，不是相反的顺序），我找不到任何方法来执行此操作而最终需要 O(n) 内存，其中n是驱动器上文件/文件夹的数量，因为在我看来，我最终需要将整个驱动器层次结构保留在内存中，而对于 DFS，我可以完全忽略我之前在层次结构中的同一级别。

所以我的问题是：有没有比线性更好的方式来使用内存来遍历文件夹？

这里http://www.python.org/doc/essays/graphs/是 DFS 对吗？

我尝试对“兄弟姐妹”做一些事情，但它不起作用。任何人都可以编写类似于此站点代码的 BFS。

我正在制作一个解决益智游戏的程序，它会在棋盘上找到所有可能的动作，并将所有可能的棋盘放在一个对象中。然后它会为结果板找到所有可能的移动，依此类推。该对象将如下所示：

我可以弄清楚如何从顶层板上添加可能的移动，但我无法弄清楚如何循环遍历第二层中的所有结果板并找出它们可能的移动，然后遍历所有第三层板等等。如何使用广度优先搜索添加可能的移动并遍历对象？

我正在尝试在 c 中实现 bfs

这些是数据结构

这是我的搜索代码

由于某种原因，这个段错误我不知道为什么我的实现是错误的？

我知道标题有点乱，但我不知道如何更好地解释它。

我正在尝试做的事情：

使用在文本文件中找到的图，找到并打印从顶点 A 到顶点 B 的最短路径（最少顶点数）。

注意：使用广度优先搜索，而不是 Dijkstra 的。

我有什么：

一种在图上应用 BFS 的工作算法，但没有实际打印出最短路径的好方法。

我很难将最短路径中的顶点与仅通过算法运行但不在最短路径中的顶点区分开来。

例如：找到0和4之间的最短路径。0连接到1,2和3。1连接到4。我的路径结果是[0,1,2,3,4]而不是[0,1， 4]。

我还没有找到任何提出相同问题的线程，或者任何包含此问题的 BFS 演练，所以我不确定我是否让这变得比现在更难？

编辑：那些可能感兴趣的人的代码（完全不确定我是否要避免圈子？）

编辑 2：更改了将路径存储到堆栈的方式。

变量和方法的一些解释：

v = 原点

w = 目标顶点

g = 图表

vi = 迭代 v 的邻居的普通迭代器

谢谢阅读！

我有一个 BFS 的实现，我在别处得到并稍作修改，但我的输入有问题。
它需要一个图表，并将其视为 '((abc) (bc) (cd)) 但我给它的输入是一个加权图......我知道它对 BFS 没有用，但我使用权重以后再往下走。这个输入看起来像 等等。
'(
(a (b 3) (c 1))
(b (a 3) (d 1))
(c (a 1) (d2) (e 2))
)

我的代码：

我只是不确定我最有可能在哪里修改它以接受新的样式列表，或者制作一个帮助功能来正确格式化它？

连续几天我一直在抨击 Haskell 空间泄漏（自然是堆栈溢出类型）。这令人沮丧，因为我试图直接从 CLR 模仿 BFS 算法，这不是自然递归的。注意：我已经启用了 BangPatterns，并且我在每个可能去的地方都放了一个 bang，试图对这个问题进行分支和绑定，但没有任何效果。我以前曾与空间泄漏作斗争，我不愿意放弃并为此而哭泣寻求帮助，但此时我被卡住了。我喜欢在 Haskell 中编码，并且非常了解函数式编程的禅宗，但调试空间泄漏与在满是图钉的地板上滚来滚去一样有趣。

也就是说，我的问题似乎是典型的“蓄能器”类型的空间泄漏。在下面的代码中，堆栈显然是围绕对 bfs' 的调用而建立的。非常感谢任何空间泄漏的提示。

好的，我有一个 BFS 的 Lisp 实现，我正在尝试将其转换为爬山搜索。

这是我的 BFS 代码的样子：

现在，我知道我需要扩展似乎最接近目标状态的节点，而不是像在 BFS 中那样总是扩展左节点。
我使用的图表如下所示：

我有一个转换函数可以使它与上述 BFS 实现一起工作，但现在我需要使用这种图形格式将其转换为爬山。

我只是不确定从哪里开始，并且一直在尝试无济于事。我知道我主要需要更改expand-queue函数以扩展最近的节点，但我似乎无法制作一个函数来确定哪个节点最近。

谢谢您的帮助！

我正在尝试Seq[X]使用相当昂贵的递归算法重构当前生成 a 的组件，以便它生成 a Stream[X]，因此X可以按需加载/计算 's ，并且生产者不必事先尝试猜测如何为了满足消费者，它必须做很多挖掘工作。

根据我的阅读，这是“展开”的理想用途，所以这就是我一直试图采取的路线。

这是我的unfold函数，源自David Pollak 的示例，该函数已经过某位莫里斯先生的审查：

这里有一棵小树可以试试我们的运气：

最后，这是我使用展开的广度优先遍历的失败尝试：

谁能给我一些关于如何修复（或重写）我的遍历逻辑以便返回所有节点的提示？谢谢！

我已经尝试过；搜索和搜索，但无法真正找到解决我问题的算法。我想枚举一棵树中的所有路径，（不仅仅是简单的路径）那些以叶节点开始和结束的路径（虽然这是一个简单的约束）。

例如，对于一棵树；

我希望能够生成以下路径：

我想就是这样。

我尝试了以下解决方案使用深度优先搜索查找所有简单路径的复杂性？. 但是，这只能找到简单的路径，因此无法找到诸如 4-2-5-2-1-3-6 之类的路径。

有什么方法可以指导我，或者任何算法？