Algorithmes sur les graphes
Nous avons réalisé plusieurs algorithmes pour générer un labyrinthe puis pour se déplacer dedans.
Algorithme de Kruskal
Cet algorithme permet de créer un arbre couvrant à partir d'un graph orienté quelconque. Ci dessous une comparaison entre un graphe généré aléatoirement et un arbre couvrant minimum généré à partir du même graphe.
Algorithme de Fisher-Yates
On utilise l'agorithme de Fisher-Yates pour mélanger le tableau des arrêtes du graphe.
Extension de l'algorithme de Kruskal
On ajoute une probabilité de garder une arrête lors de l'exécution de l'algorithme de Kruskal. Avec une probabilité égale à 0, l'algorithme est inchangé. Voici un exemple avec une probabilité de 0,5 puis 1.
