SML BFS traversal for (int list array) Graph

Question

I want to create a function in SML that does a BFS traversal of an undirected graph e.x Graph = [|[2],[3,4],[1,2],[2]|].

fun bfs (g: graph) (n: vertex): vertex list = 
let
  fun helper (todo: vertex list) (visited: vertex list) =
    case todo of
      [] => []
    | h::t => if (List.exists (fn x => x = h) visited)
              then helper t visited
              else
                let
                  val adj = case List.find (fn (n, _) => n = h) g of
                            NONE => raise Fail "incomplete adjacency list"
                          | SOME (_, adj) => adj
                in
                  h :: (helper (t @ adj) (h::visited))
                end
in
  helper [n] []
end

I found this example but i dont know how to change it to correspond to my type of graph

Answer 1

I would start by factoring out the part of that code which depends on the representation of the graph:

(* returns list of all vertices that are adjacent to h *)
fun getNeighbors g h =
  case List.find (fn (n, _) => n = h) g of
    NONE => raise Fail "incomplete adjacency list"
  | SOME (_, adj) => adj


fun bfs (g: graph) (n: vertex): vertex list = 
let
  fun helper (todo: vertex list) (visited: vertex list) =
    case todo of
      [] => []
    | h::t => if (List.exists (fn x => x = h) visited)
              then helper t visited
              else
                let
                  val adj = getNeighbors g h
                in
                  h :: (helper (t @ adj) (h::visited))
                end
in
  helper [n] []
end

Now you just need to implement a new getNeighbors function for your graph representation. It should return a list of adjacent vertices.