代表无向图的好的数据结构是什么？ [英] What is a good data structure to represent an undirected graph?

问题描述

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

I need to construct an undirected graph. I don't need it to do anything too fancy, but ideally it would work like this:

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中是否有一个良好的数据结构来对这些关系进行建模？我应该自己滚动吗？

Is there a good data structure in SML/NJ to model these relationships? Should I just roll my own?

我已经尝试了自己滚动，但是尝试测试时，出现类型不匹配错误。我对SML结构和函子的经验很基础，所以我认为我做的事情显然是错误的。我该如何工作？另外，您能帮我把它做成’图吗？从语义上来说，这似乎更有意义。

I've gone ahead and tried rolling my own, but I get a type mismatch error when I try to test it. My experience with SML structures and functors is pretty basic, so I think I'm doing something obviously wrong. How do I get this to work? Also, can you help me make this an 'a graph? That seems to make more sense, semantically.

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)

错误

当我这样做时

Error

When I do

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

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

我遇到类型不匹配的情况：

I get a type mismatch:

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)

推荐答案

有多种可能性，不同的优缺点适合于图形上的不同操作。
这个不错的介绍背景和使用邻接表和邻接矩阵的示例。

There are several possibilities with differing pros and cons suited to different operations on the graphs. This nice intro gives background and examples of using Adjacency Lists and Adjacency Matrices.

以非定向方式使用它们涉及权衡取舍（空间速度）。 本课程资料详细介绍了邻接关系列表样式，并提供一些有关在非定向用法中可能使用的更改的想法。

Using them in an undirected fashion involves trade offs (space verses speed). this course material goes into more detail on the adjacency list style and provides some thoughts on the possible alterations for use in undirected usage.

这篇关于代表无向图的好的数据结构是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！