diff options
Diffstat (limited to '80-89/87.hs')
-rw-r--r-- | 80-89/87.hs | 18 |
1 files changed, 18 insertions, 0 deletions
diff --git a/80-89/87.hs b/80-89/87.hs new file mode 100644 index 0000000..0c119e3 --- /dev/null +++ b/80-89/87.hs @@ -0,0 +1,18 @@ +import Data.List (partition, foldl') + +data Graph a = Graph [a] [(a, a)] deriving (Show, Eq) + +depthFirst :: Eq a => Graph a -> a -> [a] + +depthFirst (Graph v e) s = fst $ dfs s [] + where adjust u (a, b) + | a == u = [b] + | b == u = [a] + | otherwise = [] + dfs u vis + | u `elem` vis = ([], vis) + | otherwise = let vs = (e >>= (adjust u)) in + foldl' (\(s, vis') v -> + let (s', vis'') = dfs v vis' in + (s ++ s', vis'')) + ([u], u:vis) vs |