Algorithme reverse-delete
De Wikipedia, l'encyclopédie encyclopedia
En informatique, l'algorithme reverse-delete[1] (litt. « inverse-supprime ») est un algorithme de recherche d'arbre couvrant minimum dans un graphe connexe non-orienté et pondéré. Il a été introduit en 1956 par Joseph Kruskal[2] en même temps que l'algorithme de Kruskal qui résout le même problème.
L'algorithme reverse-delete est en quelque sorte l'inverse de l'algorithme de Kruskal : le second part d'un graphe vide et ajoute des arêtes par poids croissant, tandis que le premier part du graphe original et en supprime des arêtes par poids décroissant. Les deux algorithmes sont des algorithmes gloutons qui choisissent la meilleure solution à chaque étape.