Structures de données avancées. Première partie: graphique acyclique directionnel

Bonjour à tous! La semaine prochaine, les cours commenceront dans le nouveau groupe du cours Algorithms for Developers . À cet égard, nous partageons avec vous la traduction d'un tout petit matériel, mais plutôt intéressant.

---

Je voulais commencer cette série d'articles avec une structure de données que nous connaissons tous en tant que développeurs, mais il est possible que nous ne sachions même pas comment cela fonctionne.

«Graphique acyclique directionnel? Je n'en ai jamais entendu parler. Ne pensez pas que vous savez tout de moi! », Vous pouvez dire, mais c'est ce graphique qui permet le contrôle de version. Oui, Git est un graphique acyclique. Dans cet article, je partagerai avec vous des connaissances sur les graphes acycliques dirigés (DAG), puis je vous montrerai comment écrire les vôtres.

Qu'est-ce qu'un DAG?

Alors qu'est-ce que cela signifie même? Un DAG est un graphe unidirectionnel où aucun élément ne peut être considéré comme un enfant. Beaucoup d'entre nous connaissent les listes, les arbres et les graphiques liés. DAG est très similaire aux premier et deuxième dans la mise en œuvre du troisième.


Il ressemble à un arbre, mais pas tout à fait

Dans sa forme la plus minimale, DAG a 4 composants:

1. Noeuds Ils stockent des données.
2. Bords directionnels : flèches qui pointent dans une direction (ce qui rend cette structure de données différente des autres).
3. Un «grand» nœud d'ancêtre sans parents . (Fait amusant: la plupart des arbres ancêtres sont en fait des graphiques acycliques dirigés, pas des arbres, car parfois "des cousins ​​se marient")
4. Feuilles Ou des nœuds sans nœuds enfants.

Écrivons notre graphique acyclique dirigé

Écrivons maintenant le code. Tout d'abord, créez un constructeur avec deux propriétés et appelez-le DAG.

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

Créez une méthode pour ajouter des nœuds. Tu vois ce que j'ai fait ici?

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

Comment ça marche? L'objet vertex est l'endroit où se produit toute la magie. Nous ajoutons un nœud, un objet avec des nœuds entrants et un tableau avec tous leurs noms, une variable de type booléen qui signale si le nœud pointe vers quelque chose ou non, et sa valeur. Nous y reviendrons plus tard.

Ajoutons maintenant quelques arêtes et connectons les nœuds ensemble. 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 sa visit .

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

Les événements suivants se produisent:

 DAG.prototype.addEdge = function(fromName, toName) { if (!fromName || !toName || fromName === toName) { return; } const from = this.add(fromName) const to = this.add(toName); if (to.incoming.hasOwnProperty(fromName)) { return; } function checkCycle(vertex, path) { if (vertex.name === toName) { throw new Error(“Theres a cycle foo!!!!!“)); } } visit(from, checkCycle); from.hasOutgoing = true; to.incoming[fromName] = from; to.incomingNames.push(fromName); }; 

Il est temps de rendre hommage

Pendant que j'étudiais les matériaux pour écrire cet article, j'ai lu de merveilleux messages de personnes incroyablement intelligentes, et en conséquence, la plupart des informations ont été reçues d'eux. J'ai obtenu certaines des informations théoriques de ce poste bien structuré sur le DAG et le contrôle de version. Le code présenté ici est inspiré des sources d' emberjs et de leurs auteurs. Et j'ai beaucoup appris d'autres articles et articles sur DAG dans les blogs de nombreuses personnes formidables.

Merci d'avoir lu!