{- | Description: Depth-first graph traversal Copyright: Copyright (C) 2021 Yoo Chung License: GPL-3.0-or-later Maintainer: dev@chungyc.org Part of Ninety-Nine Haskell "Problems". Some solutions are in "Solutions.P87". -} module Problems.P87 (depthFirst) where import Problems.Graphs import qualified Solutions.P87 as Solution -- $setup -- >>> import Problems.Graphs -- >>> import Problems.P80 -- | Write a function that generates a depth-first order graph traversal sequence. -- The starting point should be specified, -- and the output should be a list of nodes that are reachable from this starting point in depth-first order. -- -- === Examples -- -- >>> let xs = depthFirst (toG $ Paths [[1,2,3,4,5], [2,4], [6,7]]) 1 -- >>> xs `elem` [[1,2,3,4,5], [1,2,4,5,3], [1,2,4,3,5]] -- True depthFirst :: G -> Vertex -> [Vertex] depthFirst :: G -> Vertex -> [Vertex] depthFirst = G -> Vertex -> [Vertex] Solution.depthFirst