Dérouler les deux parcours

Exercice · informatique (tronc commun des prépas scientifiques), chapitre 13 — Parcours de graphes

Énoncé

Dérouler le BFS à partir de a sur le graphe : G = {"a": ["b", "c"], "b": ["a", "d"], "c": ["a", "e"], "d": ["b", "f"], "e": ["c", "f"], "f": ["d", "e"]}. Donner l'ordre du DFS récursif.

Corrigé

Déroulement du BFS :
Départ : file $= [a]$ , vus $= {a}$ .
Défiler $a \to$ visites $= [a]$ . Voisins $b, c$ insérés $\to$ file $= [b, c]$ , vus $= {a, b, c}$ .
Défiler $b \to$ visites $= [a, b]$ . Voisin $d$ inséré $\to$ file $= [c, d]$ , vus $= {a, b, c, d}$ .
Défiler $c \to$ visites $= [a, b, c]$ . Voisin $e$ inséré $\to$ file $= [d, e]$ , vus $= {a, b, c, d, e}$ .
Défiler $d \to$ visites $= [a, b, c, d]$ . Voisin $f$ inséré $\to$ file $= [e, f]$ , vus $= {a, b, c, d, e, f}$ .
Défiler $e$ et $f$ (les voisins sont tous déjà marqués) $\to$ visites $= [a, b, c, d, e, f]$ .
DFS récursif : L'exploration s'enfonce : $a \to b \to d \to f \to e \to c$ . Ordre de visite : a, b, d, f, e, c.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.