Algorithme de Prim (simplifié)

Labyrinthes : différents algorithmes

Algorithme de Prim (simplifié)

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 (simplifié)

C’est l’algorithme de Prim pour produire un arbre couvrant minimal, simplifié de telle sorte que tous les poids des arêtes sont les mêmes. Il nécessite un espace de stockage proportionnel à la taille du labyrinthe. Commencez avec un sommet aléatoire. Continuez en sélectionnant au hasard une arête de passage reliant le labyrinthe à un point qui n’en fait pas encore partie, et attachez-la au labyrinthe. Le labyrinthe est terminé quand il n’y a plus d’arêtes à considérer. Comme les arêtes n’ont pas de poids et ne sont pas ordonnées, elles peuvent être stockées dans une simple liste, ce qui signifie que la sélection d’éléments dans la liste est très rapide et ne prend qu’un temps constant. Par conséquent, c’est beaucoup plus rapide que l’algorithme de Prim original avec des poids d’arêtes aléatoires. La texture du labyrinthe produit aura un facteur « rivière » plus faible et une solution plus simple que l’algorithme de Prim original, car il se répandra uniformément à partir du point de départ comme du sirop versé, au lieu de contourner et de s’écouler autour des groupes d’arêtes de poids plus élevé qui ne sont pas couverts avant plus tard. Copy