Arbre couvrant minimal
Trouver des connexions économiques avec Kruskal et examiner les décisions union–find.
À propos de cet outil
Relier les sommets sans cycle au poids total minimal. Une arête non orientée par ligne : A B 4. A seul ajoute un sommet isolé. Les lignes vides ou commençant par # sont ignorées. Identifiants : 1–24 lettres ASCII, chiffres, tirets, points ou soulignés. Poids avec point décimal et exposant éventuel ; zéro et valeurs négatives acceptés. Limites : 24 sommets, 80 arêtes différentes, 12 000 caractères, poids entre −1e9 et 1e9. A B 4 et B A 4 ne comptent qu’une fois ; des poids différents restent des arêtes parallèles.
Calculer donne immédiatement le résultat ; Pas examine une arête. Animation facultative de 0–2000 ms, initialement 350. Pause/Reprendre conserve le parcours ; Calculer peut le terminer. Réinitialiser ou modifier les entrées abandonne le parcours. Les brouillons du graphe et du délai sont enregistrés localement, même incomplets ou invalides. Recharger restaure les entrées sans calculer ; la progression n’est pas sauvegardée.
Kruskal examine les poids croissants. Union–find accepte une arête seulement entre composantes distinctes ; sinon elle créerait un cycle. Union par rang et division des chemins accélèrent les recherches. Les égalités suivent les identifiants triés, sensibles à la casse. Plusieurs arbres minimaux peuvent être valides. Tri O(E log E), opérations union–find amorties presque constantes. Toutes les arêtes sont examinées pour montrer les cycles rejetés, même après la formation de l’arbre.
Le réseau initial pèse 13 : B–C 1, B–D 2, E–F 2, A–C 3, C–E 5. Les entrées disjointes donnent un arbre minimal par composante, sommets isolés compris : une forêt couvrante minimale. Ce n’est pas un calcul de plus court chemin ou d’itinéraire. Les boucles sont rejetées. La longueur géométrique ne représente pas le poids.
Six couleurs aident à distinguer les composantes et se répètent au-delà ; les membres exacts figurent dans le tableau. Arêtes retenues vertes, rejetées rouges en tirets, arête courante plus épaisse. Les tableaux donnent arêtes retenues, membres des composantes et décisions examinées. Les longs identifiants utilisent des numéros dans le graphe ; au-delà de 16 sommets le défilement est local. Les arêtes denses peuvent se superposer. Arithmétique flottante ; affichage jusqu’à 12 chiffres significatifs.