首先遍历图的宽度，标记Haskell中的访问节点 [英] Traversing a graph breadth first, marking visited nodes in Haskell

问题描述

所以问题很简单。给出一个图（我希望图的结构在这个问题中并不重要），我该如何去做一个BFS呢？

I'最近我问了一个关于如何生成一个列表的问题，其中每个元素在其末尾添加了许多元素。答案应该希望让我做一个我需要做BFS的队列。但是还有一个关键组件是搜索需要的，它将节点标记为已访问过的，所以我们不会再重复它们。这也不需要执行算法的开销。无论是标记还是阅读。

由于Haskell不会让我改变状态，我会怎么做？

（我没有寻找将命令式代码翻译成Haskell的方法，一种惯用的Haskell解决方案将会很棒。）

>正如评论中所提到的，一种正确的方法是将图形与标记节点分开。你需要使用某种集合容器。基本上可以采取两种方法：

1. 使用功能集。虽然每次修改都会创建一个新版本，但是功能数据结构的设计使得只有很小的一部分实际发生了变化，并且大部分原始数据都是共享的。插入/查找操作对这些结构采用 O（log n）。但是从 HashSet 无序容器针对速度进行了优化，对数基数很大，因此对于大多数用途而言，该因子就像是常量。 使用 ST monad（另请参阅这个问题）。在monad里面你可以使用可变数据结构，而结果仍然是透明的。然后，您可以使用例如 ST-来自 hashtables 包的基于数据库的哈希表。这允许您摆脱 log n 因子并在常量时间对哈希表执行操作。但是还有其他的缺点，例如你的遍历必须是纯粹的。如果在其他monad中工作，您将无法将其与ST操作交错使用。

So the question is simple. Given a graph (I hope that the structure of the graph doesn't matter much in this problem), how do I go about doing a BFS on it?

I've recently asked a question about generating a list where each element appends many elements to the end of it. The answer should hopefully let me make a queue I need to do the BFS. But there's another key component that a search needs and it's marking the nodes as visited so we don't go over them again. This also needs to have no overhead on the execution of the algorithm. Neither marking or reading.

Since Haskell doesn't let me change state, how would I go about doing that?

(I'm not looking for a way to translate my imperative code to Haskell. An idiomatic Haskell solution would be great.)

解决方案

As mentioned in the comments, a proper approach is to separate your graph from marking its nodes. You need to use some kind of a set container. There are basically two approaches you can take:

1. Use a functional set. Although at every modification a new version is created, functional data structures are designed so that only a very small part actually changes and most of the original one is shared. Insert/lookup operations take O(log n) for such structures. But HashSet from unordered-containers is optimized for speed and the base of the logarithm is large, so for most purposes the factor is like constant.
2. Use the ST monad (see also this question). Inside the monad you can use mutable data structures, while the result will be still referentially transparent. Then you can use for example ST-based hash tables from the hashtables package. This allows you to get rid of the log n factor and do operations on hash tables in constant time. But there are other drawbacks, for example that your traversal must be pure. If works within some other monad, you won't be able to interleave it with ST operations.

这篇关于首先遍历图的宽度，标记Haskell中的访问节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！