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.
Insert the following code in a new file, which can be called Main.hs:
Import the required packages:
import Data.Graph import Data.Array ((!))
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) ]Scan the graph breadth-first:
breadth g i = bf [] [i] where bf :: [Int] -> [Int] -> [Int] bf seen forest | null forest = [] | otherwise = forest ++ ...