什么是表示无向图的良好数据结构？

Question

我需要构建一个无向图.我不需要它做任何太花哨的事情,但理想情况下它会像这样工作:

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)

错误

当我做

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

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

我得到一个类型不匹配:

Error: operator and operand don't agree [literal]
  operator domain: UDG.graph * ?.UDG.node * ?.UDG.node
  operand:         UDG.graph * int * int
  in expression:
    UDG.addEdge (UDG.empty,1,2)

Answer 1

有多种可能性，各有利弊，适合图表上的不同操作。 这个精彩的介绍提供了使用邻接列表和邻接矩阵的背景和示例。

以无方向的方式使用它们需要权衡（空间与速度）。本课程材料更详细地介绍了邻接列表样式，并提供了一些关于无向使用中可能的更改的想法。