How it works?

Maintenez un booléen inTree pour chaque sommet. Commencez avec seulement le sommet 0 dans l'arbre. La frontière est constituée de chaque arête ayant exactement une extrémité à l'intérieur de l'arbre, appelée une arête traversante.

Processus étape par étape :

1. Parmi toutes les arêtes traversantes, choisissez celle qui a le poids le plus faible.
2. Ajoutez son extrémité extérieure à l'arbre et ajoutez son poids au total.
3. Répétez jusqu'à ce que l'arbre contienne les n sommets (cela nécessite n - 1 arêtes).

Si à un moment donné aucune arête traversante n'existe mais que des sommets restent à l'extérieur, le graphe n'est pas connexe.

Exemple avec les arêtes [0,1,1, 1,2,2, 2,3,3, 0,3,4] : à partir de 0, prenez 0-1(1), puis 1-2(2), puis 2-3(3) ; total 6.