Parcours de graphe

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

Parcours de graphe

Graphes

Parcours de graphe

F pour passer en plein écran ou O pour afficher la vue d'ensemble.
Versions sans animation, plein écran, imprimable.

Exercices

Pile

Lire les symboles de gauche à droite :

• Lettre : empiler
• * : dépiler

1. I N V O * * * *
2. V * R E * * T *
3. L E B * U L * * *
4. E L B * U * L * * *

Solution

1. I N V O * * * * : O V N I
2. V * R E * * T * : V E R T
3. L E B * U L * * * : B L U E
4. E L B * U * L * * * : B U L L E

File

Lire les symboles de gauche à droite :

• Lettre : enfiler
• * : défiler

1. I N V O * * * *
2. V * R E * * T *

Solution

1. I N V O * * * * : I N V O
2. V * R E * * T * : V R E T

L'ordre est préservé : FIFO (First In First Out)

Parcours d'arbre

Quelle est l'ordre de parcours de l'arbre suivant en commençant par bleu ?

1. Parcours en profondeur (DFS)
2. Parcours en largeur (BFS)

Solution

Réponses possibles :

1. bleu - rouge - jaune - turquoise - orange - vert - noir
2. bleu - rouge - vert - jaune - turquoise - noir - orange

Parcours de graphe

Quelle est l'ordre de parcours du graphe suivant en commençant par bleu ?

1. Parcours en profondeur (DFS)
2. Parcours en largeur (BFS)

Solution

Réponses possibles :

1. bleu - rouge - jaune - turquoise - orange - noir - vert
2. bleu - rouge - vert - jaune - turquoise - noir - orange

Références

• 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%C3%A9es)
• 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