功能广度优先搜索

Question

函数深度优先搜索在有向无环图中很可爱。

然而，在有循环的图中，我们如何避免无限递归？在过程语言中，我会在点击节点时对其进行标记，但假设我不能这样做。

访问节点的列表是可能的，但会很慢，因为使用一个节点会导致在重复之前对该列表进行线性搜索。比这里的列表更好的数据结构显然会有所帮助，但这不是游戏的目的，因为我正在用 ML 进行编码 - 列表是王，其他任何东西我都必须自己编写。

有办法解决这个问题吗？或者我是否必须使用已访问列表或者（上帝禁止）可变状态？

Answer 1

一个选择是使用归纳图，这是一种表示和处理任意图结构的功能方式。它们由 Haskell 的 fgl 库提供，并在 Martin Erwig 的 “归纳图和函数图算法” 中进行了描述。

有关更温和的介绍（带插图！），请参阅我的博客文章使用归纳图生成迷宫。

归纳图的技巧在于它们可以让您在图上进行模式匹配。使用列表的常见功能习惯用法是将它们分解为头元素和列表的其余部分，然后递归：

map f []     = []
map f (x:xs) = f x : map f xs

归纳图可以让你做同样的事情，但是对于图。您可以将归纳图分解为节点、其边和图的其余部分。

_{（来源：jelv.is）}

这里我们匹配节点

1

及其所有边（以蓝色突出显示），与图的其余部分分开。

这让我们可以为图形编写

map

（用 Haskellish 伪代码可以用模式同义词实现）：

gmap f Empty                     = Empty
gmap f ((in, node, out) :& rest) = f (in, node, out) :& gmap f rest

与列表相比，这种方法的主要缺点是图没有单一的自然分解方式：同一个图可以通过多种方式构建。上面的地图代码将访问所有顶点，但顺序是任意的（取决于实现）。

为了克服这个问题，我们添加了另一个构造：一个采用特定节点的

match

函数。如果该节点在我们的图中，我们就会像上面一样获得成功的匹配；如果不是，则整场比赛失败。

这个构造足以编写 DFS 或 BFS — 其优雅的代码看起来几乎相同！

我们不需要手动将节点标记为已访问，而是只对图的其余部分进行递归除了我们现在看到的节点：在每一步中，我们都在处理原始图的越来越小的部分。如果我们尝试访问已经用 match

 看到的节点，它不会出现在剩余的图中，并且该分支将会失败。这让我们的图形处理代码看起来就像我们在列表上的普通递归函数一样。

这是此类图的 DFS。它将要访问的节点堆栈保留为列表（边界），并以初始边界开始。输出是按顺序遍历的节点列表。 （如果没有一些自定义模式同义词，则无法直接使用库编写此处的确切代码。）

dfs _frontier Empty = []
dfs [] _graph = []
dfs (n:ns) (match n -> Just (ctx, rest)) = -- not visited n
  dfs (neighbors' ctx ++ ns) rest
dfs (n:ns) graph =                         -- visited n
  dfs ns graph

一个非常简单的递归函数。要将其变成广度优先搜索，我们所要做的就是用队列替换堆栈边界：我们不是将邻居放在列表的

front

上，而是将它们放在

back上：

bfs _frontier Empty = []
bfs [] _graph = []
bfs (n:ns) (match n -> Just (ctx, rest)) = -- not visited n
  bfs (ns ++ neighbors' ctx) rest
bfs (n:ns) graph =                         -- visited n
  bfs ns graph

是的，这就是我们所需要的！当我们在图上递归时，我们不必做任何特殊的事情来跟踪我们访问的节点，就像我们不必跟踪我们访问过的列表单元格一样：每次我们递归时，我们'我们只得到了我们

还没有

见过的图表部分。

您必须跟踪您访问的节点。列表并不是 ML 家族中的王者，它们只是寡头之一。您应该只使用一个集合（基于树）来跟踪访问的节点。与改变节点状态相比，这会增加一个对数因子，但干净得多，这并不有趣。如果您对节点了解更多，您可以通过使用不基于树（例如位向量）的集合来消除对数因子。

Answer 2

参见

Answer 3

， 在

Martin Erwig：归纳图和函数图算法中进行了解释。另外，DFS 实现，基于 David King、John Launchbury：在 Haskell 中构建深度优先搜索算法 （给 S.O. 警察的提示：是的，这看起来像是一个仅限链接的答案，但这就是科学的运作方式 - 你必须实际阅读论文，重新输入他们的摘要并不是很有用。）

在函数内部隐藏可变状态是非常好的。如果它不可见，那么它就不存在。我通常为此使用哈希集。但总的来说，如果您的分析指出了这一点，您应该坚持这一点。否则，只需使用设置的数据结构。 OCaml 有一个基于急切平衡的 AVL 树的优秀

Answer 4

Set

。