SML BFS 遍历 for (int list array) Graph

Question

我想在 SML 中创建一个对无向图进行 BFS 遍历的函数 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

我找到了这个示例，但我不知道如何更改它以符合我的图表类型

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 函数。它应该 return 相邻顶点的列表。

SML BFS 遍历 for (int list array) Graph

SML BFS traversal for (int list array) Graph

ml

sml

smlnj