**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.
Na velmi minimální, DAG bude mít 4 věci:
- Uzly: místo pro ukládání dat.
- směrované hrany: Šipky, které ukazují jedním směrem (věc, která dělá tuto datovou strukturu odlišnou)
- 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.)
- 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í!