Tool guide

Arbre couvrant minimal : Prim et Kruskal comparés

Le panneau Arbre couvrant répond à la question du câblage le moins cher : garder chaque nœud connecté et payer le plus petit poids total d’arêtes possible. Prim fait pousser un arbre depuis une racine ; Kruskal balaie les arêtes par ordre de poids et fusionne les composantes. Tous deux rapportent le poids total, les arêtes choisies sur le nombre d’arêtes du graphe, le nombre de composantes et si le résultat est une forêt — cette dernière ligne passe à Oui quand le graphe d’entrée est déconnecté. Le graphe vient du banc de travail de graphes partagé.

Updated 4 sources5 min read