OCaml: Element zu einer Liste in einem Array hinzufügen

Question

Ich mache ein Basisprogramm in OCaml, in dem ich Graphen benutze. I definiert einen Graphen als:

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

wo Elemente in dem Array die Vertices sind, und die Elemente in den Listen die Kanten von dem Scheitelpunkt sind. Ich muss in der Lage sein, einen Graph in O (| V | + | E |) zu erstellen, der echt erscheint. Also habe ich zuerst das Vertex-Array mit leeren Listen erstellt. Jetzt möchte ich die Kanten hinzufügen.

Der einzige Weg, den ich mit herauskommen, ist dies:

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

Ich bin nicht wirklich sicher darüber, aber es scheint mir, diese linear zu der Zeit in dem Grad der a ich dies tun . Das würde bedeuten, wenn einer meiner Vertices mit jedem anderen Vertices verbunden ist, wird es mich O (n^2)

Bin ich richtig? Wenn ich bin, muss ich das trotzdem linear halten?

Answer 1

Mal sehen, was Sie tun (ich ziehe es in eine besser lesbare Art und Weise neu zu schreiben ;-)):

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

Für jede Kante a -> b Sie diese Kante durch Hinzufügen b der Liste Ihr Array hinzuzufügen entsprechenden zu a. Erster den Inhalt eines Arrays ist O (1) und in die Liste ein Element hinzuzufügen, ist O (1) auch so, wenn wir wieder, was Sie

• O tun (| V |), um das Array zu erstellen
• O (| E |) die Ränder hinzufügen
• O (| V | + | E |) das Array

Es ist wie eine lineare Art und Weise zu tun, sieht zu erstellen und zu füllen. Das Problem wird auftreten, wenn Sie herausfinden müssen, ob zwei Scheitelpunkte verbunden sind. ;-)