dfs is:exact

A spanning forest of the part of the graph reachable from the listed vertices, obtained from a depth-first search of the graph starting at each of the listed vertices in order.

Depth-first search.

Return the list vertices visited by the depth-first search in a graph, starting from the given seed vertices. Adjacent vertices are explored in the increasing order. Complexity: O((L + m) * log n) time and O(n) space, where L is the number of seed vertices.

dfs empty      vs    == []
dfs (edge 1 1) [1]   == [1]
dfs (edge 1 2) [0]   == []
dfs (edge 1 2) [1]   == [1,2]
dfs (edge 1 2) [2]   == [2]
dfs (edge 1 2) [1,2] == [1,2]
dfs (edge 1 2) [2,1] == [2,1]
dfs x          []    == []

and [ hasVertex v x | v <- dfs x vs ]       == True
dfs (3 * (1 + 4) * (1 + 5)) [1,4]           == [1,5,4]
dfs (circuit [1..5] + circuit [5,4..1]) [3] == [3,2,1,5,4]

Return the list vertices visited by the depth-first search in a graph, starting from the given seed vertices. Adjacent vertices are explored in the increasing order according to their Ord instance. Complexity: O((L + m) * log n) time and O(n) space, where L is the number of seed vertices.

dfs empty      vs    == []
dfs (edge 1 1) [1]   == [1]
dfs (edge 1 2) [0]   == []
dfs (edge 1 2) [1]   == [1,2]
dfs (edge 1 2) [2]   == [2]
dfs (edge 1 2) [1,2] == [1,2]
dfs (edge 1 2) [2,1] == [2,1]
dfs x          []    == []

and [ hasVertex v x | v <- dfs x vs ]       == True
dfs (3 * (1 + 4) * (1 + 5)) [1,4]           == [1,5,4]
dfs (circuit [1..5] + circuit [5,4..1]) [3] == [3,2,1,5,4]

Compute the list of vertices visited by the depth-first search in a graph, when searching from each of the given vertices in order.

dfs == Algebra.Graph.AdjacencyMap.dfs . toAdjacencyMap

Compute the list of vertices visited by the depth-first search in a graph, when searching from each of the given vertices in order. In the following examples we will use the helper function:

(%) :: Ord a => (GraphKL a -> b) -> AdjacencyMap a -> b
f % x = f (fromAdjacencyMap x)

for greater clarity.

dfs % edge 1 1 $ [1]   == [1]
dfs % edge 1 2 $ [0]   == []
dfs % edge 1 2 $ [1]   == [1,2]
dfs % edge 1 2 $ [2]   == [2]
dfs % edge 1 2 $ [1,2] == [1,2]
dfs % edge 1 2 $ [2,1] == [2,1]
dfs % x        $ []    == []

dfs % (3 * (1 + 4) * (1 + 5)) $ [1,4]     == [1,5,4]
and [ hasVertex v x | v <- dfs % x $ vs ] == True

dfs next found initial performs a depth-first search over a set of states, starting with initial and generating neighboring states with next. It returns a depth-first path to a state for which found returns True. Returns Nothing if no path is possible.

Example: Simple directed graph search

>>> import qualified Data.Map as Map

>>> graph = Map.fromList [(1, [2, 3]), (2, [4]), (3, [4]), (4, [])]

>>> dfs (graph Map.!) (== 4) 1
Just [3,4]

Iterate a tree in DFS pre-order. (Depth First Search)

Depth-first paths starting at a vertex.

>>> runG example $ \g@G{..} -> fmap3 gFromVertex $ dfs g <$> gToVertex 'x'
Right (Just ["xde","xe"])