Advertisement
karlicoss

bfs

Sep 7th, 2012
368
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. bfsaux :: (Ord a) => Set.Set a -> Set.Set a -> Int -> (a -> Set.Set a) -> a -> Maybe Int
  2. bfsaux closed opened current neighbours target
  3.     | opened == Set.empty = Nothing
  4.     | Set.member target opened = Just current
  5.     | otherwise = bfsaux newclosed newopened (current + 1) neighbours target
  6.     where
  7.         newclosed = Set.union closed opened
  8.         newopened = Set.difference (Set.unions $ Set.toList $ Set.map neighbours opened) closed
  9.  
  10. -- neighbours function, start, target
  11. bfs :: (Ord a) => (a -> Set.Set a) -> a -> a -> Maybe Int
  12. bfs neighbours start target = bfsaux Set.empty (Set.singleton start) 0 neighbours target
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement