informatique (tronc commun des prépas scientifiques) · Chapitre 13 · Application directe du cours
Accessible ?
Parcours de graphes · niveau 1 (application)
Énoncé
Écrire la fonction existe_chemin(G, u, v) qui s'arrête dès que la cible v est atteinte.
Corrigé
def existe_chemin(G: dict, u, v) -> bool:
if u == v:
return True
vus = {u}
pile = [u]
while pile:
s = pile.pop()
for w in G[s]:
if w == v:
return True # Arrêt anticipé
if w not in vus:
vus.add(w)
pile.append(w)
return FalseExercices semblables
- L'échelle des mots corrigé
- Les arbres, preuve du théorème corrigé
- Six degrés de séparation — mesurer un petit monde corrigé
- Pile ou file, à la main corrigé
- Dérouler les deux parcours corrigé