OCaml : add element to a list inside an Array

Question

我正在用 OCaml 编写一个基本程序，我在其中使用了图表。我将图表定义为:

type 'a graph = ('a * int list) array;;

其中数组中的元素是顶点，列表中的元素是顶点的边。我需要能够在 O(|V|+|E|) 中构建一个看起来合法的图表。所以我首先用空列表构建了顶点数组。现在，我想添加边缘。

我得出的唯一方法是:

let addEdge a b g = g.(a)<-(fst g.(a), b::snd g.(a));;

我对此不太确定，但在我看来，这在我执行此操作时与 a 的度数呈线性关系。这意味着如果我的一个顶点连接到所有其他顶点，它将花费我 O(n^2)

我说得对吗？如果是，我是否必须保持这种线性？

Answer 1

让我们看看你做了什么(我更喜欢以更易读的方式重写它 ;-)):

let addEdge a b g = 
  let (c, al) = g.(a) in
  g.(a) <- (c, b :: al);;

对于每条边 a -> b，您可以通过将 b 添加到对应于 a 的列表中来将此边添加到您的数组中。获取数组的内容是 O(1) 并且将元素添加到列表也是 O(1) 所以，如果我们恢复你所做的

• O(|V|) 创建数组
• O(|E|) 添加边
• O(|V| + |E|) 创建并填充数组

这看起来像是一种线性的做事方式。当您必须确定两个顶点是否相连时，问题就会出现。 ;-)