data-structures - 代表无向图的良好数据结构是什么？

我需要构造一个无向图。我不需要它做任何花哨的事情，但理想情况下它将像这样工作:

structure UDG = UndirectedGraph
val g = UDG.empty
val g = UDG.addEdges(g, n1, [n2, n4, n7]) (* n1 is connected to n2, n4, and n7 *)
val g = UDG.addEdge(g, n2, n3)
UDG.connected(g, n2) (* returns [n1, n3] *)

SML/NJ中是否有一个良好的数据结构来对这些关系进行建模？我应该自己滚吗？

更新

我已经开始尝试自己滚动，但是在尝试对其进行测试时出现类型不匹配错误。我对SML结构和仿函数的经验非常基础，因此我认为我做的事情显然是错误的。我该如何工作？另外，您能帮我将其设置为'a graph吗？从语义上看，这似乎更有意义。

代码

signature ORD_NODE =
sig
  type node
  val compare : node * node -> order
  val format : node -> string
end

signature GRAPH =
sig
  structure Node : ORD_NODE
  type graph
  val empty : graph

  (* val addEdge : graph * Node.node * Node.node -> graph
  *  addEdge (g, x, y) => g with an edge added from x to y. *)
  val addEdge : graph * Node.node * Node.node -> graph

  val format : graph -> string
end

functor UndirectedGraphFn (Node : ORD_NODE) :> GRAPH =
struct
  structure Node = Node
  structure Key = struct
    type ord_key = Node.node
    val compare = Node.compare
  end
  structure Map = BinaryMapFn(Key)

  type graph = Node.node list Map.map (* Adjacency list *)
  val empty = Map.empty

  fun addEdge (g, x, y) = (* snip *)
  fun format g = (* snip *)
end

structure UDG = UndirectedGraphFn(struct
  type node = int
  val compare = Int.compare
  val format = Int.toString
end)

错误

当我做

结构UDG = UndirectedGraphFn(struct
类型node = int
val compare =整数比较
val格式= Int.toString
结尾)

UDG.addEdge(UDG.empty，1,2)

我收到类型不匹配的信息:

错误:运算符和操作数不一致[字面意义]
运算符域:UDG.graph *？.UDG.node *？.UDG.node
操作数:UDG.graph * int * int
表达:
UDG.addEdge(UDG.empty，1,2)

最佳答案

好的，我对这种语言不熟悉(请原谅我的无知):

我只是使用以下结构:

V.E1.E2.En+1
V2.E1.E2.En+1
Vn+1.E1.E2.En+1

因此基本上，小数点前的第一个数字将代表顶点，每个Edge将由小数点后跟(类似于IP地址)来表示

这样:

可以存储为:

1.2.5

2.1.5.3

3.2.4

4.3.5.6

5.1.2.4

6.4

然后在您的代码中，它的边添加/删除简单，并且非常容易解析(因为顶点始终是第一个数字)