Haskell にあるリスト (linked-list, cons-list) は実質そのままスタックとして用いることができる. そして深さ優先探索 (DFS) はスタックに次訪れる状態を入れることで書けるのでとても相性がよく、Haskell で DFS は簡単である. この双対となるのが幅優先探索 (BFS) であり、これはキューに次訪れる状態を入れて持てば簡単に書ける. Haskell で BFS する方法として以前には余再帰を書いた taglibro/2014/06/16 のが、もう余再帰がなんだかわからんし、このコードも読めないので二度と書ける自信がない.
そういえばキューというのはスタック２つで表現できる. その実現方法は簡単で適当にググれば出てくる (例: スタック２つでキューを作る ).
これ使えば難しい概念を使わなくても BFS も簡単に書けることに気づいた.
data Tree = Leaf | Node Int Tree Tree deriving Show
-- ダミーデータとして完全2分木を使う
nibun :: Int -> Tree
nibun n = nibun_sub n 0
where
nibun_sub 0 i = Leaf
nibun_sub n i = Node i (nibun_sub (n - 1) (2 * i + 1)) (nibun_sub (n - 1) (2 * i + 2))
-- まずはスタック一つで深さ優先探索
-- 訪れたノードを返すことにする
dfs :: Tree -> [Int]
dfs tr = dfs_sub tr [] []
where
dfs_sub Leaf [] order = reverse order
dfs_sub Leaf (x:xs) order = dfs_sub x xs order
dfs_sub (Node val left right) stack order = dfs_sub left (right:stack) (val:order)
-- 次はスタック2つをもたせる
-- 1つ目が push 用で二つ目が pop 用 （一番最後のリストは訪れた順を保存して最後に返す用）
bfs :: Tree -> [Int]
bfs tr = bfs_sub tr [] [] []
where
bfs_sub tr q@(x:xs) [] order = bfs_sub tr [] (reverse q) order -- queue
bfs_sub Leaf [] [] order = reverse order
bfs_sub Leaf queue_left (x:xs) order = bfs_sub x queue_left xs order
bfs_sub (Node val left right) [] [] order = bfs_sub left [] [right] (val:order)
bfs_sub (Node val left right) queue_left (x:xs) order = bfs_sub x (left:right:queue_left) xs (val:order)
main :: IO ()
main = do
print $ tr
print $ dfs tr
print $ bfs tr
where
tr = nibun 3