（int列表数组）图形的SML BFS遍历

Question

我想在SML中创建一个函数，对无向图e.x Graph = [|[2],[3,4],[1,2],[2]|]进行BFS遍历。

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

我找到了这个示例，但是我不知道如何更改它以使其与我的图形类型相对应

Answer 1

我将首先剔除取决于图形表示形式的代码部分：

(* 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

现在，您只需为图形表示实现新的getNeighbors函数。它应该返回相邻顶点的列表。