Problem 87b Solution
breadthFirst : comparable -> Graph comparable -> List comparable
breadthFirst start (nodes, edges) =
List.reverse (breadthFirst_ [start] [] (nodes, edges))
breadthFirst_ : List comparable -> List comparable -> Graph comparable -> List comparable
breadthFirst_ unvisited visited ( nodes, edges ) =
case unvisited of
[] ->
visited
u::us ->
let
nextNodes = unique
<| List.map (Tuple.second)
<| (++) (List.filter (\( a, b ) -> a == u) edges)
<| List.map (\x -> ( Tuple.second x, Tuple.first x ))
<| List.filter (\( a, b ) -> b == u) edges
newNodes = List.sort
<| List.filter (\x -> not (List.member x (u::visited))) nextNodes
in
breadthFirst_ (remove u (newNodes ++ unvisited)) (u::visited) (nodes, edges)
remove : a -> List a -> List a
remove x =
List.filter ((/=) x)
unique : List comparable -> List comparable
unique list =
Set.toList <| Set.fromList list
Back to problem