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.
Start editing a new source file, which we will name Main.hs:
Import the required packages:
import Data.Graph import Data.Array ((!))
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, []) ]Scan the graph depth-first:
depth g i = depth' g [] i depth' g2(gShape, gMapping) seen i = key : concat (map goDeeper adjacent) where goDeeper v = if v `elem` seen then [] else depth' g (i:seen) v adjacent = gShape ! i (_, key, _) = gMapping...