Math & Numbers

Calculateur d'arbre couvrant minimal (Kruskal / Prim)

Calcule l'arbre couvrant minimal d'un graphe non orienté pondéré (1–30 arêtes, une par ligne : nœud1, nœud2, poids) avec deux algorithmes : Kruskal trie par poids et applique une union-find, en journalisant chaque arête acceptée ou rejetée comme cycle ; Prim part d'un nœud initial et prend à chaque pas l'arête la moins chère sortant de la composante, en montrant sa croissance. Les boucles sont ignorées ; un graphe non connexe est rejeté avec son nombre de composantes ; le poids total des deux algorithmes doit coïncider (contrôle interne). Classique : A-B 4, A-C 2, B-C 5, B-D 10, C-E 3, D-E 4, D-F 11, E-F 8 → poids de l'ACM 21 (A—C, C—E, A—B, D—E, E—F), B—C rejetée comme cycle.