avancerade datastrukturer Del 1: riktad acyklisk Graf (DAG)

**pågående arbete**

Jag ville starta denna serie med en datastrukturstruktur som vi alla är som utvecklare intimt bekanta med men kanske inte ens vet det: riktade acykliska grafer. ”Jag har aldrig hört talas om det. Du känner mig inte!”du kanske säger, men den här grafen är det som gör versionskontroll möjlig. Git är en acyklisk graf. I det här inlägget, Jag kommer att ge dig lite kunskap på hög nivå på DAGs och sedan visa dig hur man gör en med lite kod.

Vad är en DAG?

Så vad betyder det ens? En dag är en graf som flyter i en riktning, där inget element kan vara ett barn av sig själv. Så de flesta av oss är bekanta med länkade listor, träd och till och med grafer. En DAG är mycket lik de två första och en implementering av den tredje.

Vid ett minimum kommer en dag att ha 4 saker:

1. noder: en plats för att lagra data.
2. riktade kanter: Pilar som pekar i en riktning (det som gör denna datastruktur annorlunda)
3. någon stor förfädernod utan föräldrar. (Roligt faktum: de flesta anor träd är faktiskt DAGs och inte faktiskt träd eftersom kusiner någon gång gifter sig med varandra.)
4. blad: noder utan barn

Låt oss göra en

Så låt oss skriva lite kod. Låt oss först skapa en konstruktör med två egenskaper och kalla det DAG.

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

nästa lägger vi till en add-metod. Ser du vad jag gjorde där?

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å hur fungerar det här? Vertexobjektet är där alla bra saker händer. Vi lägger till en nod, ett objekt med inkommande noder och en matris med alla deras namn, en boolesk om det pekar på något och ett värde. Vi kommer till några av dessa lite senare.

Nu kan lägga till några kanter och göra saker ansluta till varandra. Innan vi kan göra det måste vi skapa en hjälpfunktion som kontrollerar om vi har besökt den noden eller inte. Låt oss kalla 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();
}

vad händer här är

Låt oss ge kredit där det verkligen beror

forska i den här artikeln läste jag några bra inlägg av otroligt smarta människor och det mesta av informationen kom från dem. Jag lärde mig det mesta av teorin genom att läsa detta välskrivna inlägg på DAGs och versionskontroll. Koden här fick all sin inspiration från emberjs källkod och de lysande författarna bakom den. Jag har också läst många andra artiklar och blogginlägg om Dagsbilder från stora människor runt om på internet. Tack för att du läste!