Pokročilé Datové Struktury Část 1: Režie Acyklický Graf (DAG)

**Work in progress**

chtěl jsem odstartuje tato série se datové struktury, struktura, která jsme všichni jako vývojáři důvěrně obeznámen s, ale dokonce ani nemusí vědět, že: Namířených Acyklických Grafů. „Nikdy jsem o tom neslyšel. Neznáš mě!“můžete říci, ale tento graf je to, co umožňuje správu verzí. Git je acyklický graf. V tomto příspěvku, Dám vám trochu znalostí na vysoké úrovni o Dag a pak vám ukážu, jak si vytvořit nějaký kód.

co je DAG?

Co to vůbec znamená? DAG je graf, který teče jedním směrem, kde žádný prvek nemůže být dítětem sám o sobě. Takže většina z nás je obeznámena s Propojenýmiseznamy, stromy a dokonce i grafy. DAG je velmi podobný prvním dvěma a implementaci třetího.

Podobný stromu, ale ne úplně stejné.

Na velmi minimální, DAG bude mít 4 věci:

  1. Uzly: místo pro ukládání dat.
  2. směrované hrany: Šipky, které ukazují jedním směrem (věc, která dělá tuto datovou strukturu odlišnou)
  3. nějaký skvělý uzel předků bez rodičů. (Zábavný fakt: většina rodových stromů jsou ve skutečnosti DAGs a ne ve skutečnosti stromy, protože bratranci se v určitém okamžiku oženili.)
  4. listy: uzly bez dětí

Udělejme jeden

takže pojďme napsat nějaký kód. Nejprve vytvoříme Konstruktor se dvěma vlastnostmi a nazveme ho DAG.

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

dále přidáme metodu přidání. Vidíš, co jsem tam udělal?

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

jak to tedy funguje? Vrcholový objekt je místo, kde se dějí všechny dobré věci. Přidáme uzel, objekt příchozích uzlů a pole se všemi jejich jmény, boolean o tom, zda ukazuje na něco a hodnotu. K některým z nich se dostaneme o něco později.

nyní umožňuje přidat některé hrany a dělat věci připojit k sobě navzájem. Než to můžeme udělat, musíme vytvořit pomocnou funkci, která zkontroluje, zda jsme tento uzel navštívili nebo ne. Říkejme tomu návštěva.

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 = true;
for (i = 0; i < len; i++) {
visit(vertices], fn, visited, path);
}
fn(vertex, path);
path.pop();
}

Co se stane, zde je,

Pojďme Dát Úvěr, Kde je to Opravdu Kvůli

Zkoumá tento článek, četl jsem některé skvělé příspěvky úžasně chytří lidé, a většina informací pochází od nich. Většinu teorie jsem se naučil čtením tohoto dobře napsaného příspěvku na DAGs a správu verzí. Kód zde dostal veškerou inspiraci ze zdrojového kódu emberjs a skvělých autorů za ním. Také jsem četl řadu dalších článků a blogových příspěvků týkajících se dag od skvělých lidí po celém internetu. Děkuji za přečtení!

Napsat komentář

Vaše e-mailová adresa nebude zveřejněna. Vyžadované informace jsou označeny *