Traversing a graph breadth-first

Using breadth-first search, one can traverse a graph to view the nodes in the desired order. In an infinite graph, a depth-first traversal may never return back to the starting node. One of the most notable examples of a breadth-first traversal algorithm is finding the shortest path between two nodes.

In this recipe, we will print out the breadth-first traversal of the nodes in a graph.

How to do it...

Insert the following code in a new file, which can be called Main.hs:

1. Import the required packages:

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

2. Construct the graph from a list of edges:

   graph :: Graph
   graph = buildG bounds edges
     where  bounds = (1,7)
            edges = [ (1,2), (1,5)
                    , (2,3), (2,4) 
                    , (5,6), (5,7) 
                    , (3,1) ]

3. Scan the graph breadth-first:

   breadth g i = bf [] [i]
     where bf :: [Int] -> [Int] -> [Int]
           bf seen forest | null forest = []
                          | otherwise   = forest ++ 
        ...