functional-programming - OCaml 中表示图最常用的数据结构是什么？

Question

在 Java 或其他命令式编程中，图可以表示为 matrix或 adjacent list . adjacent list可能是最受欢迎的，因为它使用时紧凑且方便array .

在函数式编程中，我们通常不使用 mutable array .那么通常我们如何在 OCaml 或其他函数式编程中呈现图形？

用 map 替换数组?

在 ocaml 99, graph它列出了4种方式:

边缘条款形式

一种方法是列出所有边，边是一对节点。在这种形式中，对面描绘的图形表示为以下表达式:

['h', 'g';  'k', 'f';  'f', 'b';  'f', 'c';  'c', 'b']

我们称这种形式为边子句形式。显然，孤立节点无法表示。

图项形式

另一种方法是将整个图表示为一个数据对象。根据图为一对两个集合(节点和边)的定义，我们可以使用以下 OCaml 类型:

type 'a graph_term = { nodes : 'a list;  edges : ('a * 'a) list }

然后，上面的示例图表示为:

let example_graph =
{ nodes = ['b'; 'c'; 'd'; 'f'; 'g'; 'h'; 'k'];
  edges = ['h', 'g';  'k', 'f';  'f', 'b';  'f', 'c';  'c', 'b'] }

我们称之为图项形式。请注意，列表保持排序，它们实际上是集合，没有重复的元素。每条边在边列表中只出现一次；即从节点 x 到另一个节点 y 的边表示为 (x,y)，不存在 (y,x) 对。图项形式是我们的默认表示。您可能希望使用集合而不是列表来定义类似的类型。

邻接表形式

第三种表示方法是将与每个节点相邻的节点集与每个节点相关联。我们称其为邻接表形式。

人性化表格

到目前为止，我们介绍的表示非常适合自动化处理，但它们的语法对用户不是很友好。手动输入术语既麻烦又容易出错。我们可以定义一个更紧凑和“人性化”的符号如下:一个图(带有字符标记的节点)由一串原子和 X-Y 类型的项表示。原子代表孤立的节点，X-Y 术语描述边缘。如果 X 显示为边的端点，则自动将其定义为节点。我们的例子可以写成:

"b-c f-c g-h d f-b k-f h-g"

考虑到处理效率，我认为以上 4 种方式都不够好。

对于 record type graph-term form ，没有有效的方法来定位节点(总是 O(n))和定位附加到节点的边。

Answer 1

有两件事需要考虑:图的表示，以及一些图算法中使用的中间数据结构。

我认为邻接表形式是表示图形的最节省内存的方式。可以通过拥有该类型的树或 map 来改善一点

type Graph a = Map a [a]

但是，当您想要运行诸如“强连通分量”或“拓扑排序”之类的算法时，这些算法很可能会使用可变数组来实现它。

请注意，在像 Haskell 这样的语言中，ST monad 可以拥有临时可变状态，即数组)，而不是全局状态。使用它的函数仍然是整体纯的。