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

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)

我得到了类型不匹配的错误：

错误：运算符和操作数不匹配[literal]
  运算符域：UDG.graph * ?.UDG.node * ?.UDG.node
  操作数：    UDG.graph * int * int
  在表达式中：
    UDG.addEdge (UDG.empty,1,2)

- Andrew Keeton

---

在你的错误信息中，它说“UDG.addEdge(UDG.empty.....”也许它正在尝试将字符串“empty”乘以UDG.node？抱歉，我不熟悉SML。 - Darknight

Answer 1

有几种可能性，适用于不同的图操作，它们各有优缺点。使用邻接表和邻接矩阵的背景和示例可以在这篇很好的介绍中找到。

以无向方式使用它们涉及到权衡（空间与速度之间）。这份课程材料更详细地介绍了邻接表样式，并提供了一些关于可能的修改以用于无向用途的想法。

- ShuggyCoUk

---

-1是否愿意给出一个原因？ - ShuggyCoUk

很抱歉，我投了反对票，这样它就不会自动被接受。并不是说你的回答没有帮助，只是我认为它（或其他回答）还不值得被接受。如果您编辑它，我会撤回我的-1。 - Andrew Keeton

好的，对于你的错误信息我恐怕没有太多可以提供的了。虽然SML不是我的强项，但我想问一下为什么你要自己编写代码而不使用链接论文中提供的代码呢？ - ShuggyCoUk

我感觉很愚蠢，没有查看你的链接；我只是假设它们是标准的邻接列表与矩阵。尽管它们不完全是我要找的，但仍然很有帮助。 - Andrew Keeton

Answer 2

好的，我不熟悉这种语言（请原谅我的无知）：

我会简单地使用以下结构：

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

基本上，小数点前的第一个数字表示顶点，每个边都以小数点表示（有点像IP地址）。

例如：

如图所示：

可以存储为：

然后，在您的代码中，添加/删除边很简单，解析也非常容易（因为顶点始终是第一个数字）。

- Darknight

---

这实际上是个相当聪明的想法。特别是如果数据结构需要先填充，然后用于可视化目的。我正在进行一个业余项目，旨在创建这样一种可视化，并且我一定会尝试这种方法。 - manneorama

Answer 3

一个非常简单的方法就是使用哈希表，以源节点作为键，将连接节点列表作为值。然后编写一个添加函数，它执行两个哈希表插入操作，一个是(src, tgt)，另一个是(tgt, src)。

在OCaml中：

let add n1 n2 =
  let aux n1 n2 =
    match Hashtbl.find_option tbl n1 with
    | None -> Hashtbl.add tbl n1 [n2]
    | Some nodes -> Hashtbl.replace tbl n1 (n2::nodes)
  in
  let _ = aux n1 n2 in
  aux n2 n1

这将是一个有向图，只需在插入时添加两个方向即可。哈希表查找函数将充当您的connected函数。

（实际上，在Ocaml中，哈希表为一个键提供多个值，因此您可以使用Hashtbl.find_all函数并保存列表。但这是最容易转换为SML的方法。）

- David Crawshaw

Answer 4

我们可以将图表示为一系列列表，我们称之为数据结构：邻接表。

- xmen-5