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
:
- 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 ...
Get Haskell Data Analysis Cookbook now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.