**Work in progress * *
jeg ønsket å sparke i gang denne serien med en datastruktur struktur som vi alle er som utviklere nært kjent med, men kanskje ikke engang vet det: Directed Acyclic Grafer. «Jeg har aldri hørt om det. Du kjenner meg ikke!»du kan si, men denne grafen er det som gjør versjonskontroll mulig . Git er en asyklisk graf. I dette innlegget vil jeg gi deg litt kunnskap på Høyt nivå Om DAGs og deretter vise deg hvordan du lager en med litt kode.
Hva er EN DAG?
Så hva betyr det selv? EN dag er en graf som flyter i en retning, hvor ingen element kan være et barn av seg selv. Så de fleste av oss er kjent Med Kobletlister, trær og til og med grafer. EN DAG er veldig lik de to første, og en implementering av den tredje.
i det minste vil en dag ha 4 ting:
- noder: et sted å lagre dataene.
- Rettet Kanter: Piler som peker i en retning (det som gjør denne datastrukturen annerledes)
- Noen store forfedre uten foreldre. (Morsomt faktum: De fleste forfedre er Faktisk DAGs og ikke egentlig trær fordi fettere på et tidspunkt blir gift med hverandre.)
- Leaves: Noder uten barn
La Oss Lage en
Så la oss skrive litt kode. Først, la oss lage en konstruktør med to egenskaper og kalle DET DAG.
function DAG() {
this.nodes = ;
this.vertices = {};
}
Neste vil vi legge til en add-metode. Ser du hva jeg gjorde der?
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;
};
Så hvordan fungerer dette? Vertex-objektet er hvor alle de gode greiene skjer. Vi legger til en node, et objekt av innkommende noder, og en matrise med alle navnene deres, en boolsk om det peker på noe og en verdi. Vi kommer til noen av disse litt senere.
nå kan du legge til noen kanter og få ting til å koble til hverandre. Før vi kan gjøre det, må vi opprette en hjelpefunksjon som sjekker om vi har besøkt den noden eller ikke. La oss kalle det besøk.
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();
}
Hva skjer her er
La Oss Gi Kreditt Hvor Det Egentlig Skyldes
Forske på denne artikkelen, jeg leste noen gode innlegg av utrolig smarte mennesker og det meste av informasjonen kom fra dem. Jeg lærte det meste av teorien ved å lese dette godt skrevet innlegg På DAGs og versjonskontroll. Koden her fikk all sin inspirasjon fra emberjs kildekoden og de strålende forfatterne bak den. Jeg har også lest mange andre artikler og blogginnlegg om DAGs fra flotte mennesker rundt på internett. Takk for at du leser!