二維地圖到Sml中的圖形

Question

我有一個2D地圖作爲輸入從一個文件，逐行，我想保存它並運行一個Bfs或Dijkstra找到最短路徑從開始（標記爲S）結束（標記爲E），保存信息的適當結構是什麼？我在C++中的實現是使用圖表，但我發現在sml中很難這樣做，因爲我無法以兩種方式鏈接節點。

Answer 1

你可以使用可變數組來做到這一點。這是使用int option數組陣列的極小的鄰接矩陣實現。頂點i和j之間的邊緣由第i行中的值和第j列中的值給出。如果值爲None那麼沒有邊緣，如果值爲Some w比邊緣存在並且具有權重w。

let is_some opt = 
    match opt with 
    | None -> false 
    | _ -> true;; 

let unwrap opt = 
    match opt with 
    | None -> raise (Failure "unwrapped None") 
    | Some x -> x;; 

let add_edge g u v w = 
    let us = Array.get g u in 
    Array.set us v (Some w);; 

let get_edge g u v = 
    let us = Array.get g u in 
    Array.get us v;; 

let make_graph vertices = 
    Array.make_matrix vertices vertices None;; 

let neighbors g u = 
    Array.get g u |> 
    Array.to_list |> 
    List.filter is_some |> 
    List.mapi (fun i o -> (i, unwrap o));; 


let g = make_graph 4;; 
add_edge g 0 1 2;; 
add_edge g 0 2 3;; 
add_edge g 0 3 5;; 
add_edge g 1 2 7;; 
add_edge g 1 3 11;; 
add_edge g 2 3 13;; 
add_edge g 3 0 17;; 
List.iter (fun (v, e) -> Printf.printf "0-(%i)->%i\n" e v) (neighbors g 0);; 

這是在OCaml中，但SML和OCaml之間的差異大部分是輕微的。