我需要在樹狀結構中找到所有路徑。
我最近定義了深度優先遍歷（或迭代）如下：
dfIterate:: (a -> [a]) -> a -> [[a]]
dfIterate f a = map (a:) ([] : concatMap (dfIterate f) (f a))
它需要一個種子a和一個函式a -> [a]（從每個“ a”，你可以得到多個a's）。結果是從種子開始的路徑串列。它運作良好：
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)))
我嘗試使用第二個引數作為佇列。我知道我離結果還很遠……謝謝
編輯：此鏈接提供了有趣的方法：Breadth-First Search using State monad in Haskell。但是，我的問題是關于找到所有路徑（即[[a]]），而該問題是尋找單一解決方案（即[a]）
uj5u.com熱心網友回復：
先正確，后效率。
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 ])
確實維護一個佇列并將節點逐級添加到其中。
嘗試：
> bfPaths f 1
[[1],[1,2],[1,3],[1,2,4]]
現在，您可以尋找提高效率的方法。
最簡單的改進是反向構建路徑，然后將它們反向回傳，或者僅在輸出時反向（如果必須）。
看起來它也是最好的，因為它允許在構建路徑時最大程度地共享結構（反向），當然在前面添加新值是O(1)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/350116.html
上一篇：如何為資料型別類撰寫函式