Algorithme de Kruskal (1956)

L'Algorithme de Kruskal est apparu pour la première fois dans les Actes de l’"American Mathematical Society", pages 48 à 50 en 1956, et a été écrit par Joseph Kruskal. Il consiste à trouver l'arbre couvrant minimum. 1️⃣️ On cherche la distance la plus courte entre 2 points. 2️⃣️ Si un autre chemin existe déjà, on ne retient pas cette branche. 3️⃣️ On répète l'étape 1 jusqu'à ce que tous les points soient accessibles par n'importe quel autres points. Cet algorithme, très simple à coder, peut se révéler très consommateur de calculs lors du classement des différentes routes suivant leur distance et de la vérification de routes existantes (Algorithme de parcours en largeur ou profondeur). Algorithmes similaires : Algorithme de Borůvka - Algorithme de Prim.