问题标签 [breadth-first-search]

我有一个数据集，它是一个大型未加权循环图循环发生在大约 5-6 条路径的循环中。它由大约 8000 个节点组成，每个节点有 1-6 个（通常大约 4-5 个）连接。我正在做单对最短路径计算，并实现了以下代码来进行广度优先搜索。

上面的代码使用 Python 2.6 Queue 模块，getNeighbours() 只是一个子例程，它进行一次 MySQL 调用并将邻居作为元组列表返回，例如 (('foo',),('bar',))。SQL 调用很快。

代码工作正常，但是测试到大约 7 层的深度需要大约 20 秒才能运行（2.5GHz Intel 4GB RAM OS X 10.6）

我欢迎任何关于如何改进此代码的运行时间的评论。

这是2009 年第 1B 轮问题 C“平方数学”中的问题。我知道比赛分析已发布。但是当一个节点可以被多次访问时，我并没有讨论如何实现 BFS。我只能使用 DFS 来实现。（因为上下文隐式保存在递归 DFS 中）。如何使用 BFS 做到这一点？

我听说可以通过 BFS 解决 8-puzzle 问题，但我不明白如何解决。我想知道我需要从这样的板上获得的中间步骤：

到

BFS 搜索的中间步骤是“级别”吗？

顺便说一句，这是基本功课，我不在乎最优性。

首先，这个问题不是这个问题的重复，而是建立在它之上。

以那个问题中的树为例，

你会如何修改你的程序来打印它，

而不是一般的

我基本上是在寻找最有效的方法的直觉——我有一种方法涉及将结果附加到列表中，然后循环遍历它。一种更有效的方法可能是在弹出的每个级别中存储最后一个元素，然后打印出一个新行。

想法？

设置（MySQL）：

这是我上一篇文章的 BFS 解决方案：

挑战，如何实现六度分离的算法？

但它的复杂性是什么？假设完全有n记录。

我对广度优先算法有疑问，我的脚本在 Maya 中生成曲线，定位它们，旋转和缩放它们，以便它们给我树形，我有这些变量

cs=当前状态，

p=父母，

节点=未访问节点列表

lvl=当前深度

maxlvl = 最大深度

问题是我无法确定当前深度，并在那里终止树，它存在而没有访问所有节点

这是我的脚本

先感谢您

我目前有一个包含大约1000 万个节点和3500 万条边的图。现在，完整的图形在程序启动时被加载到内存中。这需要几分钟（毕竟是 Java）并且需要大约半 GB 的 RAM。目前，它运行在具有双核处理器和 4 GB RAM 的机器上。

当使用广度优先搜索来搜索图表时，内存使用量会上升到 1 GB 的峰值，平均需要 10 秒。

我想在几台计算机上部署该程序。除了图形搜索之外的功能确实需要很少的资源。我的目标系统非常微型，只有 512 兆字节的 RAM。

关于如何实现一种方法（可能使用数据库）来搜索该图而不消耗太多内存的任何建议？该程序在访问硬件设备时大部分时间都处于空闲状态，因此上述图表的路径查找最多可能需要大约 5 分钟......

感谢您向我提出的任何想法。

更新：

刚刚找到neo4j。有人知道它是否适合这种巨大的图表吗？

在为我的 Graph 实现实现了大部分常用和需要的功能之后，我意识到有几个功能（删除顶点、搜索顶点和获取顶点）没有“最佳”实现。

我正在为我的 Graph 实现使用带有链接列表的邻接列表，并且我正在一个接一个地搜索一个顶点，直到找到我想要的那个。就像我说的，我意识到我没有使用“最好的”实现。我可以有 10000 个顶点并且需要搜索最后一个顶点，但是那个顶点可以有一个到第一个顶点的链接，这会大大加快速度。但这只是一个假设的情况，它可能会发生也可能不会发生。

那么，您推荐什么算法用于搜索查找？我们的老师主要谈论广度优先和深度优先（还有 Dikjstra 的算法，但那是完全不同的主题）。在这两者之间，你推荐哪一个？

如果我能同时实现这两者就完美了，但我没有时间，我需要拿起一个并在第一阶段截止日期临近时实现它......

我的猜测是，使用深度优先，似乎更容易实现，并且查看它们的工作方式，这似乎是最好的选择。但这实际上取决于输入。

但是你们有什么建议呢？

我们如何检测有向图是否是循环的？我想使用广度优先搜索，但我不确定。有任何想法吗？

假设您想递归地实现二叉树的广度优先搜索。你会怎么做？

是否可以仅使用调用堆栈作为辅助存储？