Ocaml 中有向图的合理数据结构类型

Question

我想使用邻接表来表示图结构，我不需要对边进行加权。我想练习一些简单的练习，比如找到一个循环、BFS、DFS、添加删除边……没什么特别的。（我也可以用哈希表来做，但我需要更多 List 练习）

type 'a dgraph = DG of ('a * 'a list) list

我的问题是：

这是 DG 的合理表述吗？
这些不应该是递归类型吗？（不知何故感觉更自然）

我不想搬起石头砸自己的脚，从一开始就设计得很糟糕type，那会导致更复杂的实现。

示例：

let g = 
    DG (
        [
            ('a', ['c'; 'd']);
            ('c', ['d']);
            ('b', ['a'; 'e']);
        ]
    )

注：

我没有在 http://ocaml.org/learn/tutorials/99problems.html#Graphs 上找到邻接表表示法。

Answer 1

这是一个非常好的图形表示。您需要确保标签是唯一的。您也没有区分标签和节点的其他可能内容。

使用这种结构，从标签到带有标签的节点需要搜索外部列表。如果您的图表变大，这可能会开始花费太长时间。所以你需要构建一个从标签到节点的辅助映射。我自己做过很多次。

另一个解决方案是拥有独立于节点内容的节点索引。这也降低了处理重复标签的难度。我现在正在研究图形问题，结构基本上是这样的：

 type 'a mygraph = ('a * int list) array

'a类型表示一个节点的内容，数组索引用于link它们在一起

我还使用过使用散列 table 而不是数组的结构。当您的节点类型中有一些可用作索引的唯一标识符时，这很有效。（或者你可以使用任意构造的索引。）散列table结构的优点是更容易修改图。

您的数据结构似乎应该是递归的，但是（在我看来）这混淆了图形和图形的表示。如果您希望您的数据结构实际上是一个图形而不是仅仅表示一个图形，那么它必须是递归的。像这样：

type 'a rgraph = RG of 'a * 'a rgraph list

像这样的数据结构几乎不可能在像 OCaml 这样急切的语言中使用。当它们有循环时，构造所需的值非常困难。

可以使用 let rec:

# let rec rg1 = RG (17, [rg1]);;
val rg1 : int rgraph = RG (17, [<cycle>])

但是我个人从未见过 "real world" 代码可以使用这样的结构。请注意，let rec 的这种用法在 OCaml 手册中被标记为语言扩展（第 7.2 节，值的递归定义）。

你可以通过使用引用使这样的数据结构更tractable，可能是这样的：

type 'a rrgraph = RRG of 'a * 'a rrgraph list ref

然后您可以创建您的节点，然后 link 它们一起创建。我过去使用过这样的结构，但我觉得我失去了使用 immutable 数据的一些很好的保证。

# let node1 = RRG (7, ref []);;
val node1 : int rrgraph = RRG (7, {contents = []})
# let node2 = RRG (8, ref []);;
val node2 : int rrgraph = RRG (8, {contents = []})
# let RRG (_, links) = node1 in links := [node2];;
- : unit = ()
# let RRG (_, links) = node2 in links := [node1];;
- : unit = ()
# node1;;
- : int rrgraph = RRG (7, {contents = [RRG (8, {contents = [<cycle>]})]})

这样表示的一个优点是您可以自由创建新节点，而无需维护包含所有节点的中央 table。垃圾收集器负责删除不再可达的节点。

Ocaml 中有向图的合理数据结构类型

Reasonable data-structure type for a Directed graph in Ocaml

ocaml

graph-theory

graph

data-structures