我有一个二维图作为文件的输入,逐行保存,然后运行Bfs或Dijkstra来查找从开始(标记为S)到结束(标记为E)的最短路径,保存信息的合适结构是什么?我在c++中的实现是一个图,但我发现在sml中很难做到这一点,因为我不能以两种方式链接节点。
发布于 2017-05-09 10:49:57
您可以使用可变数组来完成此操作。这是一个使用int option
数组的极小邻接矩阵实现。顶点i
和j
之间的边由i
th行和j
th列中的值指定。如果值为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之间的区别很小。
https://stackoverflow.com/questions/43752272
复制相似问题