MST en temps linéaire - algorithme, graphique, minimum-spanning-tree

Je me prépare pour l’examen final d’Algorithmes et j’ai une question à laquelle j’espère que vous pourrez m'aider.

Etant donné un graphe non orienté avec des poids compris entre 1 et 100, comment puis-je trouver l'arbre de recouvrement minimum dans un temps linéaire?

Réponses:

Vous pourriez utiliser Algorithme de Kruskal avec ensemble disjoint et trier les bords en utilisant compter le tri, parce que vos poids sont limités.