Erweiterte Datenstrukturen. Erster Teil: Directional Acyclic Graph

Hallo allerseits! Nächste Woche beginnt der Unterricht in der neuen Gruppe des Kurses Algorithmen für Entwickler . In diesem Zusammenhang teilen wir Ihnen die Übersetzung eines sehr kleinen, aber recht interessanten Materials mit.

---

Ich wollte diese Artikelserie mit einer Datenstruktur beginnen, mit der wir alle als Entwickler vertraut sind, aber es ist möglich, dass wir nicht einmal wissen, wie es funktioniert.

„Richtungsakzyklischer Graph? Ich habe noch nie davon gehört. Denken Sie nicht, dass Sie alles über mich wissen! “, Können Sie sagen, aber es ist diese Grafik, die die Versionskontrolle ermöglicht. Ja, Git ist ein azyklischer Graph. In diesem Artikel werde ich Ihnen Kenntnisse über Directed Acyclic Graphs (DAGs) vermitteln und Ihnen dann zeigen, wie Sie Ihre eigenen schreiben.

Was ist eine DAG?

Was bedeutet das überhaupt? Eine DAG ist ein unidirektionaler Graph, in dem kein Element als untergeordnetes Element betrachtet werden kann. Viele von uns kennen verknüpfte Listen, Bäume und Grafiken. Die DAG ist der ersten und zweiten bei der Umsetzung der dritten sehr ähnlich.


Es sieht aus wie ein Baum, aber nicht ganz

In seiner minimalsten Form besteht die DAG aus 4 Komponenten:

1. Knoten Sie speichern Daten.
2. Richtungskanten : Pfeile, die in eine Richtung zeigen (was diese Datenstruktur von den anderen unterscheidet).
3. Ein „großer“ Ahnenknoten ohne Eltern . (Unterhaltsame Tatsache: Die meisten Ahnenbäume sind tatsächlich azyklische Graphen, keine Bäume, weil sich manchmal "Cousins ​​heiraten")
4. Blätter Oder Knoten ohne untergeordnete Knoten.

Schreiben wir unseren gerichteten azyklischen Graphen

Jetzt schreiben wir den Code. Erstellen Sie zunächst einen Konstruktor mit zwei Eigenschaften und nennen Sie ihn DAG.

function DAG() { this.nodes = []; this.vertices = {}; } 

Erstellen Sie eine Methode zum Hinzufügen von Knoten. Sehen Sie, was ich hier gemacht habe?

 DAG.prototype.add = function(node) { if (!node) { return; } if (this.vertices[node]) { return this.vertices[node]; } const vertex = { node: node, incoming: {}, incomingNodes: [], hasOutgoing: false, value: null }; this.vertices[node] = vertex; this.nodes.push(node); return vertex; }; 

Wie funktioniert es Im vertex geschieht die ganze Magie. Wir fügen einen Knoten, ein Objekt mit eingehenden Knoten und ein Array mit all ihren Namen hinzu, eine Variable vom Typ Boolean, die signalisiert, ob der Knoten auf etwas zeigt oder nicht, und seinen Wert. Wir werden später darauf zurückkommen.

Fügen wir nun einige Kanten hinzu und verbinden die Knoten miteinander. Bevor wir dies tun können, müssen wir eine Hilfsfunktion erstellen, die prüft, ob wir diesen Knoten besucht haben oder nicht. Nennen wir sie visit .

 function visit(vertex, fn, visited, path) { const name = vertex.name, vertices = vertex.incoming, names = vertex.incomingNames, len = names.length, i; if (!visited) { visited = {}; } if (!path) { path = []; } if (visited.hasOwnProperty(name)) { return; } path.push(name); visited[name] = true; for (i = 0; i < len; i++) { visit(vertices[names[i]], fn, visited, path); } fn(vertex, path); path.pop(); } 

Folgendes passiert:

 DAG.prototype.addEdge = function(fromName, toName) { if (!fromName || !toName || fromName === toName) { return; } const from = this.add(fromName) const to = this.add(toName); if (to.incoming.hasOwnProperty(fromName)) { return; } function checkCycle(vertex, path) { if (vertex.name === toName) { throw new Error(“Theres a cycle foo!!!!!“)); } } visit(from, checkCycle); from.hasOutgoing = true; to.incoming[fromName] = from; to.incomingNames.push(fromName); }; 

Es ist Zeit, Tribut zu zollen

Während ich Materialien zum Schreiben dieses Artikels studierte, las ich einige wundervolle Nachrichten von erstaunlich klugen Leuten, und als Ergebnis wurden die meisten Informationen von ihnen erhalten. Ich habe einige der theoretischen Informationen aus diesem gut strukturierten Beitrag über DAG und Versionskontrolle erhalten. Der hier vorgestellte Code ist von Emberjs Quellen und ihren Autoren inspiriert. Und ich habe viel aus anderen Artikeln und Posts über DAG in den Blogs vieler großartiger Leute gelernt.

Danke fürs Lesen!