Обход SML BFS для (int list array) Graph - PullRequest
Новая
       108

Обход SML BFS для (int list array) Graph

0 голосов
/ 28 апреля 2020

Я хочу создать функцию в SML, которая выполняет BFS-обход неориентированного графа, например 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

Я нашел этот пример, но я не знаю, как изменить его, чтобы он соответствовал моему типу графика

1 Ответ

0 голосов
/ 29 апреля 2020

Я бы начал с выделения той части кода, которая зависит от представления графа: 

(* 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 для представления графа. Должен возвращать список смежных вершин.

...