Un graphe en dictionnaire

Dans cet exercice, nous allons créer un graphe de lieux, mais cette fois-ci en encapsulant les algorithmes de parcours (largeur et profondeur) dans des fonctions réutilisables.

Voici le schéma des chemins orientés de notre forêt :

• Entrée mène à Clairière et Grotte,

• Clairière mène à Rivière,

• Grotte mène à Rivière,

• Rivière mène à Sortie,

• Sortie ne mène nulle part (cul-de-sac).

• Si vous voulez faire afficher sur la console la valeur d'une variable nommée v, utilisez l'instruction print(v).

1. 1

   Indice

   Associez chaque nom de lieu à une liste de ses destinations possibles. N'oubliez pas la Sortie avec une liste vide [].
   Modélisation du graphe : Créez un dictionnaire graphe où chaque clé (chaîne de caractères) est associée à la liste de ses destinations. N'oubliez pas la "Sortie" qui a une liste vide.
2. 2

   Indice

   La syntaxe d'accès est nom_dictionnaire[cle].
   Accès aux voisins : Récupérez la liste des voisins de la "Clairière" depuis le graphe et stockez-la dans la variable voisins_clairiere.
3. 3

   Indice

   Initialisez la file avec le sommet de départ passé en paramètre. Utilisez .pop(0) pour retirer le premier élément et renvoyez la liste des visites à la fin.
   Fonction Parcours en Largeur (BFS) : Écrivez une fonction parcours_largeur(graphe, depart) qui prend en paramètres le dictionnaire du graphe et le nom du sommet de départ. Elle doit implémenter l'algorithme avec une file (utilisation de .pop(0)) et renvoyer la liste ordonnée des sommets visités.
4. 4

   Indice

   Identique au parcours en largeur, mais utilisez .pop() (sans index) pour retirer le dernier élément de la liste (comportement de pile).
   Fonction Parcours en Profondeur (DFS) : Écrivez une fonction parcours_profondeur(graphe, depart) qui implémente l'algorithme avec une pile (utilisation de .pop()) et renvoie la liste ordonnée des sommets visités.
5. 5

   Indice

   Appelez d'abord votre fonction de parcours en largeur. Ensuite, multipliez la longueur de la liste obtenue (via len()) par 0.5.
   Appel et calcul du coût : Appelez la fonction parcours_largeur avec le graphe et "Entrée" comme point de départ. Stockez le résultat dans la variable visites_bfs. Sachant que chaque lieu visité coûte 0.5 point d'énergie, calculez l'énergie totale dépensée et stockez ce nombre décimal (float) dans la variable energie_depensee.