16 lines
421 B
Haskell
16 lines
421 B
Haskell
module Bfs where
|
|
|
|
import qualified Data.Map as M
|
|
|
|
type Neighs a = a -> [a]
|
|
|
|
bfs :: Ord k => Neighs k -> [(k, Int)] -> M.Map k Int -> M.Map k Int
|
|
bfs f [] visited = visited
|
|
bfs f ((q, dist):qs) visited = if new
|
|
then bfs f queue' visited'
|
|
else bfs f qs visited
|
|
where
|
|
new = M.notMember q visited
|
|
neighs = f q
|
|
visited' = M.insert q dist visited
|
|
queue' = qs ++ map(,dist+1) neighs |