Avancé
🧠 Fondamentaux
30 XP
0 personnes ont réussi
Trouver un chemin dans un graphe
Tu sais maintenant parcourir un graphe. Mais comment trouver le chemin entre deux noeuds ? C'est comme trouver l'itineraire entre deux villes sur une carte.
L'astuce est de garder en mémoire, pour chaque noeud visite, par quel noeud on y est arrive (son predecesseur). Une fois qu'on atteint la destination, on remonte la chaine des predecesseurs pour reconstituer le chemin.
En utilisant un BFS, le chemin trouve sera toujours le plus court en nombre d'aretes.
Écris une fonction trouver_chemin(graphe, depart, arrivee) qui retourne une liste de noeuds formant un chemin du depart a l'arrivee, ou None si aucun chemin n'existe. Le chemin doit inclure le depart et l'arrivee.
Exemple : g = {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A'], 'D': ['B']} trouver_chemin(g, 'A', 'D') donne ['A', 'B', 'D']
Tests (2/4)
Chemin direct
g = {'A': ['B'], 'B': ['A', 'C'], 'C': ['B']}
chemin = trouver_chemin(g, 'A', 'C')
assert chemin is not None
assert chemin[0] == 'A' and chemin[-1] == 'C'
Aucun chemin
g = {'A': ['B'], 'B': ['A'], 'C': ['D'], 'D': ['C']}
assert trouver_chemin(g, 'A', 'C') is None
+ 0 tests cachés
Indices (3 disponibles)
Solution officielle
from collections import deque
def trouver_chemin(graphe, depart, arrivee):
if depart == arrivee:
return [depart]
predecesseurs = {depart: None}
file = deque([depart])
while file:
noeud = file.popleft()
for voisin in graphe.get(noeud, []):
if voisin not in predecesseurs:
predecesseurs[voisin] = noeud
if voisin == arrivee:
chemin = []
courant = arrivee
while courant is not None:
chemin.append(courant)
courant = predecesseurs[courant]
return chemin[::-1]
file.append(voisin)
return None