python - 功能广度优先搜索

Question

函数深度优先搜索在有向无环图中非常有用。

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

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

有解决这个问题的聪明方法吗？还是我必须使用已访问列表，或者，上帝保佑，可变状态？

Answer 1

一种选择是使用归纳图，这是一种表示和使用任意图结构的函数式方法。它们由 Haskell 的 fgl 提供。 库并在 "Inductive Graphs and Funtional Graph Algorithms" 中描述由 Martin Erwig 撰写。

如需更温和的介绍(附插图!)，请参阅我的博文 Generating Mazes with Inductive Graphs .

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

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

与列表相比，这种方法的主要缺点是图没有一种自然的分解方式:同一个图可以用多种方式构建。上面的 map 代码将访问所有顶点，但顺序是任意的(依赖于实现)。

为了克服这个问题，我们添加了另一个构造:一个接受特定节点的 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 上，而是将它们放在 返回:

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

是的，这就是我们所需要的!当我们在图上递归时，我们不需要做任何特别的事情来跟踪我们访问过的节点，就像我们不必跟踪我们访问过的列表单元格一样:每次我们递归时，我们仅获取我们没有看到的图表部分。