首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
社区首页 >问答首页 >Sml中的2D映射到图形

Sml中的2D映射到图形
EN

Stack Overflow用户
提问于 2017-05-03 14:08:03
回答 1查看 176关注 0票数 0

我有一个二维图作为文件的输入,逐行保存,然后运行Bfs或Dijkstra来查找从开始(标记为S)到结束(标记为E)的最短路径,保存信息的合适结构是什么?我在c++中的实现是一个图,但我发现在sml中很难做到这一点,因为我不能以两种方式链接节点。

EN

回答 1

Stack Overflow用户

发布于 2017-05-09 10:49:57

您可以使用可变数组来完成此操作。这是一个使用int option数组的极小邻接矩阵实现。顶点ij之间的边由ith行和jth列中的值指定。如果值为None,则没有边;如果值为Some w,则边存在且具有权重w

代码语言:javascript
代码运行次数:0
运行
复制
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之间的区别很小。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/43752272

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档