Chargement…
Graphe non orienté d'arêtes A-B, A-C, B-D, C-D, D-E. Les voisins sont listés par ordre alphabétique. Donne l'ordre de visite du parcours en largeur d'abord depuis A.
File de départ : [A], visités : {A}. Retirer A : ses voisins B et C ne sont pas visités. Ordre : A, B, C. File : [B, C]. Retirer B : son voisin A est déjà visité, son voisin D ne l'est pas. Ordre : A, B, C, D. File : [C, D]. Retirer C : ses voisins A et D sont déjà visités. Retirer D : ses voisins B et C sont déjà visités, son voisin E ne l'est pas. Ordre : A, B, C, D, E. File : [E]. Retirer E : son voisin D est déjà visité. Ordre final : A, B, C, D, E.
Avec le même graphe (A-B, A-C, B-D, C-D, D-E), donne l'ordre de visite du parcours en profondeur d'abord depuis A, puis propose un chemin de A vers E.
On visite A. Les voisins de A sont B puis C. On part sur B et on visite B. Les voisins de B sont A (déjà visité) puis D. On visite D. Les voisins de D sont B (déjà visité) puis C. On visite C. Les voisins de C sont A et D, tous deux déjà visités : on revient en arrière jusqu'à D. D a encore un voisin non visité, E : on visite E. Les voisins de E se réduisent à D, déjà visité : on revient en arrière. Ordre final : A, B, D, C, E. Chemin de A vers E : en partant de A, on va en B, puis en D, puis en E, ce qui donne le chemin A-B-D-E.
Dans un parcours en largeur d'abord, quelle structure de données sert à mémoriser les sommets à traiter ?
Une file.
La file range les sommets dans leur ordre d'arrivée et les fait sortir dans ce même ordre. Le parcours en largeur traite ainsi les sommets du plus proche au plus éloigné du départ.
Graphe non orienté d'arêtes A-B, A-C, B-D, C-D, D-E. Quel est l'ordre de visite du parcours en largeur d'abord depuis A ?
A, B, C, D, E.
On part de A et on enfile ses voisins B et C. On traite ensuite B, qui fait entrer D, puis C, dont les voisins sont déjà visités. On traite D, qui fait entrer E, puis E. L'ordre de sortie de la file donne A, B, C, D, E.
Ce même graphe contient-il un cycle ? Si oui, donne-en un.
Oui, par exemple A-B-D-C-A.
On part de A, on suit l'arête vers B, puis vers D, puis vers C, et l'arête C-A ramène au départ. On obtient un chemin fermé, donc un cycle.
Cette fiche fait partie de notre collection MathématiquesDécouvre toutes nos fiches de 3e pour réviser efficacement !
Voir toutes les fiches de 3e