Parcours
Objectifs
- Définir le parcours d'un graphe
- Différencier les parcours en profondeur et en largeur
- Définir, différencier et utiliser une pile et une file
- Appliquer un parcours en profondeur et en largeur à un graphe
Cours
Appuyez sur F pour passer en plein écran.
Version plein écran ou imprimable.
Exercices
Exercice : Pile
Lisez les symboles de gauche à droite :
- Lettre : empiler
- * : dépiler
I N V O * * * *
V * R E * * T *
L E B * U L * * *
E L B * U * L * * *
Réponse
I N V O * * * *
:O V N I
V * R E * * T *
:V E R T
L E B * U L * * *
:B L U E
E L B * U * L * * *
:B U L L E
Exercice : File
Lisez les symboles de gauche à droite :
- Lettre : enfiler
- * : défiler
I N V O * * * *
V * R E * * T *
Réponse
I N V O * * * *
:I N V O
V * R E * * T *
:V R E T
L'ordre est préservé : FIFO (First In First Out)
Exercice : Parcours d'arbre
Quelle est l'ordre de parcours de l'arbre suivant en commençant par bleu
?
- Parcours en profondeur (DFS)
- Parcours en largeur (BFS)
Réponse
Réponses possibles :
- bleu - rouge - jaune - turquoise - orange - vert - noir
- bleu - rouge - vert - jaune - turquoise - noir - orange
Exercice : Parcours de graphe
Quelle est l'ordre de parcours du graphe suivant en commençant par bleu
?
- Parcours en profondeur (DFS)
- Parcours en largeur (BFS)
Réponse
Réponses possibles :
- bleu - rouge - jaune - turquoise - orange - noir - vert
- bleu - rouge - vert - jaune - turquoise - noir - orange
Sources
- https://fr.wikipedia.org/wiki/Parcours_de_graphe
- https://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_profondeur
- https://fr.wikipedia.org/wiki/Algorithme_de_parcours_en_largeur
- https://fr.wikipedia.org/wiki/Pile_(informatique)
- https://fr.wikipedia.org/wiki/File_(structure_de_données)
- https://www.lecluse.fr/nsi/NSI_T/donnees/listes_piles_files/
- https://www.programiz.com/dsa/graph-dfs
- https://www.programiz.com/dsa/graph-bfs