Haskell 中的广度优先遍历

Question

我需要找到树状结构中的所有路径。

我最近定义深度优先遍历（或迭代）如下：

dfIterate:: (a -> [a]) -> a -> [[a]]
dfIterate f a = map (a:) ([] : concatMap (dfIterate f) (f a))

它需要一个种子 a 和一个函数 a -> [a]（从每个“a”，你可以得到多个 a）。结果是从种子开始的路径列表。效果很好：

ghci> let f a = if a == 1 then [2, 3] else if a == 2 then [4] else []
ghci> dfIterate f 1
[[1],[1,2],[1,2,4],[1,3]]

我的函数 dfIterate 正确迭代并向我显示了所有路径。函数f模拟上面的树

但是如何进行“广度优先遍历”呢？这种情况下的结果应该是：[[1],[1,2],[1,3],[1,2,4]]。我的第一次尝试：

bfIterate :: (a -> [a]) -> [a] -> [[a]]
bfIterate _ [] = [[]]
bfIterate f (a:as) = map (a:) (bfIterate f (as ++ (f a)))

我尝试将第二个参数用作队列。我知道我离结果还很远... 谢谢

编辑：link 给出了有趣的方法：。但是，我的问题是关于找到所有路径（即 [[a]]），而该问题是寻找单一解决方案（即 [a]）

Answer 1

正确第一，效率第二。

bfPaths :: (a -> [a]) -> a -> [[a]]
bfPaths step seed  =  go [ (seed, [seed]) ]
 where
 go []  =  []
 go ((s, path) : q) = path :
   go (q ++ [ (x, path ++ [x]) | x <- step s ])

确实在维护一个队列并逐级向其中添加节点。

go的参数是一个列表，用作“先进先出”queue。它包含成对的 (node_value, that_node's_path)。初始节点值为seed，因此其路径为[seed].

在每一步中，队列都被解构为头对 (s, path) 和队列的其余部分 q。然后 path 被 returned，然后是处理 q 其余部分的结果，下一对由 step 函数从这个种子 s，在 q 之后附加：(q ++ [....]).

在每个步骤的列表末尾追加会产生一个队列，而在前面追加会产生“后进先出”stack。

因此，此列表用作“待办事项”列表、“议程”或此隐式图的探索前沿。使用队列，探索是广度优先的；对于堆栈，它是深度优先的。

尝试一下：

> bfPaths f 1
[[1],[1,2],[1,3],[1,2,4]]

现在您可以寻找提高效率的方法。特别是，重复附加单例列表以构建结果列表会导致 quadratic 行为。执行时间将随着输入大小的平方增长。

最简单的改进是反向构建路径，然后 return 将它们反向（或者仅在最终处理时反向，如果必须的话），从而避免二次减速：

bfPathsR :: (a -> [a]) -> a -> [[a]]
bfPathsR step seed  =  go [ (seed, [seed]) ]
 where
 go []  =  []
 go ((s, path) : q) = path :
   go (q ++ [ (x, [x] ++ path) | x <- step s ])

看起来它也是最好的，因为它允许在构建路径（反向）时最大程度地共享结构，当然还可以在 前面添加新值 是 O(1)，因此总体上它将是线性的（执行时间随着输入的大小而增长）。

如果你只想输出完整的路径，即没有连续的路径，你只需在代码中添加这个条件：

bfPathsRC :: (a -> [a]) -> a -> [[a]]
bfPathsRC step seed  =  go [ (seed, [seed]) ]
 where
 go []  =  []
 go ((s, path) : q) = [path | null next] ++
   go (q ++ [ (x, [x] ++ path) | x <- next ])
  where
  next = step s

-- bfPathsRC f 1  =  [[3,1],[4,2,1]]

Haskell 中的广度优先遍历

Breadth First Traversal in Haskell

tree

haskell

breadth-first-search