Parcours en largeur

Cet exercice conduit à l'implémentation du parcours en largueur dans un graphe non pondéré et permet de :

• construire le parcours en larguer lui-même,
• trouver la distance (nombre de sauts minimal) entre deux sommets,
• trouver le chemin le plus court dans un graphe non pondéré.

1. 1

   Indice

   Utiliser une liste Python comme une file. L'initialiser une file avec le sommet de départ puis parcourir les voisins non visités pour les ajouter à la liste de parcours. Une structure de données decouverts doit mémoriser les sommets déjà découverts pour ne pas les parcourir plusieurs fois.
   Écrire une fonction parcours_largeur(g, depart) -> list[int] qui renvoie la liste des sommets visités lors d'un parcours en largeur à partir du sommet depart. Par exemple parcours_largeur([[1, 2], [0, 2], [0, 1]], 0) renvoie [0, 1, 2].
2. 2

   Indice

   Stocker le sommet et la distance courante dans la file d'attente sous la forme d'un tuple, puis interrompre la recherche dès que le sommet stop est extrait de la file.
   Écrire une fonction distance(g, start, stop) -> int qui calcule la distance minimale (nombre de sauts minimal) entre start et stop dans le graphe g. Par exemple distance([[1], [0, 2], [1]], 0, 2) renvoie 2.
3. 3

   Indice

   Remonter itérativement les parents depuis le sommet d'arrivée jusqu'à la racine puis inverser la liste obtenue pour restituer le chemin correct.
   Écrire une fonction remonter_chemin(parents, stop) qui renvoie la liste des sommets formant le chemin depuis la racine jusqu'à stop en utilisant le tableau de parents. Par convention, le sommet de départ est son propre parent sur le chemin. Par exemple remonter_chemin([0, 0, 1, 2], 3) renvoie [0, 1, 2, 3].
4. 4

   Indice

   Enregistrer le prédécesseur de chaque voisin découvert pendant l'exploration.
   Écrire une fonction plus_court_chemin(g, start, stop) qui renvoie un tuple (distance, chemin) correspondant au chemin le plus court entre start et stop en termes de nombre de sauts dans un graphe non pondéré. Par exemple plus_court_chemin([[1], [0, 2], [1]], 0, 2) renvoie (2, [0, 1, 2]).