OCaml：配列内のリストに要素を追加する

Question

OCamlでグラフを使用する基本的なプログラムを作っています。 Iのようなグラフを定義：配列内の要素は、頂点、及びリストの要素である

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

頂点からエッジです。私は合法的なO（| V | + | E |）のグラフを構築できる必要があります。 私はまず、空のリストを持つ頂点配列を作成しました。さて、私はエッジを追加したいと思います。

私が出てきた唯一の方法はこれです：

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

私はこれについては本当にわからないんだけど、私がこれを行う時点での度で線形であるように思えます。これは、私の頂点の1つが他のすべての頂点に接続されている場合は、O（n^2）になります。

私はそうですか？ もし私がそうであれば、とにかくこれを線形に保つ必要がありますか？

Answer 1

のは、（;-)私はより読みやすい方法でそれを書き換えることを好む）あなたが何をすべきかを見てみましょう：あなたは、対応するリストにbを追加して、配列に、このエッジを追加a -> b各エッジに対して

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

aになります。配列の内容を取得すると、O（1）と、リストに要素を追加するとOである（1）もそう、私たちは、あなたが何をしたか再開する場合

• O（| V |）アレイを作成し
• O（| E |）それはやっての線形道のように見える配列

を作成し、埋めるために（| V | + | | E）エッジ

Oを追加します。 2つの頂点が接続されているかどうかを調べなければならないときに問題が発生します。 ;-)