Structures de données avancées Partie 1: Graphe Acyclique dirigé (DAG)

**Travail en cours **

Je voulais lancer cette série avec une structure de structure de données que nous connaissons tous en tant que développeurs, mais que nous ne connaissons peut-être même pas: Graphes acycliques dirigés.  » Je n’en ai jamais entendu parler. Tu ne me connais pas ! »vous pouvez dire, mais ce graphique est ce qui rend le contrôle de version possible. Git est un graphe acyclique. Dans cet article, je vais vous donner un peu de connaissances de haut niveau sur les DAG, puis vous montrer comment en créer un avec du code.

Qu’est-ce qu’un DAG ?

Alors qu’est-ce que cela signifie même? Un DAG est un graphique qui circule dans une direction, où aucun élément ne peut être un enfant de lui-même. La plupart d’entre nous sont donc familiers avec les listes de liens, les arbres et même les graphiques. Un DAG est très similaire aux deux premiers et une implémentation du troisième.

Au minimum, un DAG aura 4 choses:

1. Nœuds: Un endroit pour stocker les données.
2. Bords dirigés: Flèches qui pointent dans une direction (ce qui rend cette structure de données différente)
3. Un grand nœud ancestral sans parents. (Fait amusant: La plupart des arbres d’ascendance sont en fait des DAGs et non des arbres parce que les cousins se marient à un moment donné.)
4. Feuilles: Nœuds sans enfants

Faisons-En Un

Alors écrivons du code. Tout d’abord, créons un constructeur avec deux propriétés et appelons-le DAG.

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

Ensuite, nous ajouterons une méthode add. Tu vois ce que j’ai fait là-bas ?

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;
};

Alors, comment cela fonctionne-t-il? L’objet sommet est l’endroit où toutes les bonnes choses se produisent. Nous ajoutons un nœud, un objet de nœuds entrants et un tableau avec tous leurs noms, un booléen indiquant s’il pointe vers quelque chose et une valeur. Nous en parlerons un peu plus tard.

Maintenant, ajoutons des bords et faisons en sorte que les choses se connectent les unes aux autres. Avant de pouvoir le faire, nous devons créer une fonction d’assistance qui vérifie si nous avons visité ce nœud ou non. Appelons ça visite.

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();
}

Ce qui se passe ici, c’est

Donnons du crédit Là Où c’est vraiment dû

En recherchant cet article, j’ai lu d’excellents articles de personnes incroyablement intelligentes et la plupart des informations provenaient d’eux. J’ai appris la majeure partie de la théorie en lisant cet article bien écrit sur les DAG et le contrôle de version. Le code ici a tiré toute son inspiration du code source emberjs et des brillants auteurs derrière lui. J’ai également lu de nombreux autres articles et articles de blog concernant les DAG de personnes formidables sur Internet. Merci d’avoir lu!