#algorithme #code

Un Directed Acyclic Graph (DAG) est une structure de donnée en graph, où chaque “vertex” possède une ou plusieurs “edges” unidirectionnels vers un autre vertex. Il n’y a pas de cycle dans un DAG.

Les vertices d’un DAG peuvent être triés avec l’algorithme Topological Sort. Cet algorithme ordonne les vertices tel que tous les vertices qui ont une edge vers un vertex v se trouvent avant v.

L’algorithme fonctionne de cette manière : 1. Créer un array in_degree qui compte le nombre de edges qui entrent dans chaque vertex v 2. Prendre n’importe quel vertex v tel que in_degree[v] = 0, et l’ajouter au résultat. 3. Pour chaque edge sortant de v, décrémenter le in_degree de tous les vertices rencontrés

A la fin, result contient tous les vertices du graph, en topological order.