所以问题很简单。给定一个图（我希望图的结构在这个问题中并不重要），我该如何对其进行 BFS 呢？
我最近问了一个关于生成列表的问题，其中每个元素都将许多元素附加到其末尾。希望答案应该能让我创建一个执行 BFS 所需的队列。但是搜索还需要另一个关键组件，它将节点标记为已访问，因此我们不会再次遍历它们。这也不需要对算法的执行产生任何开销。既不标记也不阅读。
既然 Haskell 不允许我改变状态，我该怎么做呢？
（我并不是在寻找一种将我的命令式代码转换为 Haskell 的方法。惯用的 Haskell 解决方案会很棒。）
正如评论中提到的，正确的方法是将图与标记其节点分开。您需要使用某种集合容器。您基本上可以采取两种方法：
- 使用功能集。尽管每次修改都会创建一个新版本，但功能数据结构的设计使得只有很小的一部分实际上发生了变化，而大部分原始版本是共享的。插入/查找操作需要O(log n)对于这样的结构。但HashSet http://hackage.haskell.org/package/unordered-containers-0.2.3.3/docs/Data-HashSet.html from 无序容器针对速度进行了优化，并且对数的底很大，因此对于大多数用途来说，该因子就像常数。
- Use the ST http://www.haskell.org/haskellwiki/Monad/ST单子（另见这个问题 https://stackoverflow.com/q/12468622/1333025）。在 monad 内部，您可以使用可变数据结构，而结果仍然是引用透明的。然后你可以使用例如基于ST的哈希表 http://hackage.haskell.org/package/hashtables-1.1.2.1/docs/Data-HashTable-ST-Basic.html来自哈希表包裹。这可以让你摆脱log n在恒定时间内对哈希表进行分解和操作。但还有其他缺点，例如您的遍历必须是纯粹的。如果在其他一些 monad 中工作，您将无法将其与 ST 操作交错。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
