Algorithme de Prim (original)

Labyrinthes : différents algorithmes

Algorithme de Prim (original)

Traduit en Français par moi-même. Les originaux sont ici.

Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Algorithme de Prim (original)<

C’est l’algorithme de Prim pour produire un arbre couvrant minimal, opérant sur des poids d’arêtes aléatoires uniques. Il nécessite un espace de stockage proportionnel à la taille du labyrinthe.

Fonctionnement de l’algorithme :

  1. Commencez avec n’importe quel sommet (le labyrinthe final sera le même quel que soit le sommet de départ).
  2. Continuez en sélectionnant l’arête de passage ayant le plus petit poids qui relie le labyrinthe à un point qui n’en fait pas encore partie.
  3. Attachez cette arête au labyrinthe.
  4. Le labyrinthe est terminé quand il n’y a plus d’arêtes à considérer.

Pour sélectionner efficacement l’arête suivante, une file de priorité (généralement implémentée avec un tas) est nécessaire pour stocker les arêtes frontières. Malgré cela, cet algorithme est relativement lent, car la sélection d’éléments et la maintenance du tas nécessitent un temps logarithmique (log(n)).

Par conséquent, l’algorithme de Kruskal, qui produit également un arbre couvrant minimal, peut être considéré comme meilleur, car il est plus rapide et produit des labyrinthes avec une texture identique. En fait, avec la même graine de nombres aléatoires, des labyrinthes identiques peuvent être créés avec les algorithmes de Prim et de Kruskal.