Haskell Data Analysis Cookbook

Traversing a graph depth-first

Using depth-first search, one can traverse a graph to view the nodes in the desired order. Implementing a topological sort, solving mazes, and finding connected components are all examples of useful algorithms that rely on a depth-first traversal of a graph.

How to do it...

Start editing a new source file, which we will name Main.hs:

1. Import the required packages:

   import Data.Graph
   import Data.Array ((!))

2. Construct the graph from the adjacency list:

   graph :: (Graph, Vertex -> (Int, Int, [Int]))
   
   graph = graphFromEdges'  [ (1, 1, [3, 4] )
                            , (2, 2, [3, 4]) 
                            , (3, 3, [4])
                            , (4, 4, []) ]

3. Scan the graph depth-first:

   depth g i = depth' g [] i depth' g2(gShape, gMapping) seen i = key : concat (map goDeeper adjacent) where goDeeper ...