Variante de l'algorithme de tri topologique : gestion efficace des dépendances
2025-04-03
Cet article présente un algorithme de tri topologique amélioré basé sur l'algorithme de Kahn, mais il traite les nœuds comme des ensembles au lieu de nœuds individuels. L'algorithme trouve itérativement les ensembles racines du graphe, les supprime et répète jusqu'à ce que le graphe soit vide. L'ordre des ensembles racines supprimés forme un ordre topologique, et les nœuds au sein du même ensemble racine sont indépendants et peuvent être traités en parallèle. L'algorithme peut également détecter les cycles et renvoyer un ordre topologique partiel au lieu d'arrêter complètement.