GraphMaze

maze.arbre_couvrant(G)

Construit l’arbre couvrant minimal d’un graphe avec l’algorithme de Kruskal.

On trie les arêtes par poids croissant, puis on les ajoute une par une en vérifiant qu’elles ne créent pas de cycle (avec Union-Find).

Paramètres:

G (nx.Graph) – Le graphe d’entrée avec des arêtes pondérées.

Renvoie:

L’arbre couvrant minimal du graphe.

Type renvoyé:

nx.Graph

maze.create_maze(rows, cols, n_cycles)

Génère un labyrinthe sous forme de graphe.

On crée d’abord une grille complète avec des poids aléatoires, puis on calcule l’arbre couvrant minimal pour obtenir un labyrinthe sans cycles. Enfin, on rajoute quelques arêtes pour créer des cycles et rendre le labyrinthe plus intéressant.

Paramètres:

• rows (int) – Le nombre de lignes du labyrinthe.

• cols (int) – Le nombre de colonnes du labyrinthe.

• n_cycles (int) – Le nombre de cycles à ajouter dans le labyrinthe.

Renvoie:

Le graphe représentant le labyrinthe.

Type renvoyé:

nx.Graph

maze.draw_maze_terminal(G, rows, cols, path=None, start=None, end=None, point_list=None)

Affiche le labyrinthe dans le terminal avec des couleurs.

Le point de départ est affiché en vert (SS), l’arrivée en rouge (EE), les points intermédiaires en bleu (OO) et le chemin en orange (XX).

Paramètres:

• G (nx.Graph) – Le graphe représentant le labyrinthe.

• rows (int) – Le nombre de lignes du labyrinthe.

• cols (int) – Le nombre de colonnes du labyrinthe.

• path (list, optional) – La liste des noeuds formant le chemin à afficher, optionnel.

• start (tuple, optional) – Le noeud de départ, optionnel.

• end (tuple, optional) – Le noeud d’arrivée, optionnel.

• point_list (list, optional) – La liste des points intermédiaires à afficher, optionnel.

maze.parse_input(tmp)

Convertit une entrée utilisateur comme « A1 » en coordonnées (ligne, colonne).

La partie alphabétique correspond à la colonne, la partie numérique correspond à la ligne. Par exemple, « B3 » devient (2, 1).

Paramètres:

tmp (str) – La chaîne de caractères entrée par l’utilisateur (ex: « A1 »).

Renvoie:

Les coordonnées du noeud sous forme (ligne, colonne).

Type renvoyé:

tuple

maze.bfs(G, start, end)

Trouve le chemin le plus court entre deux noeuds avec un parcours en largeur (BFS).

On explore les noeuds voisins niveau par niveau jusqu’à atteindre le noeud d’arrivée. Ça garantit que le chemin trouvé est le plus court.

Paramètres:

• G (nx.Graph) – Le graphe dans lequel on cherche le chemin.

• start (tuple) – Le noeud de départ.

• end (tuple) – Le noeud d’arrivée.

Renvoie:

La liste des noeuds formant le chemin le plus court, ou None si aucun chemin n’existe.

Type renvoyé:

list or None

maze.main()

Initialise intéractivement le labyrinthe et les points par lesquels passer puis affiche le chemin