Gymnase

Apparence

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
  1. I N V O * * * *
  2. V * R E * * T *
  3. L E B * U L * * *
  4. E L B * U * L * * *
Réponse
  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

Exercice : File ​

Lisez les symboles de gauche à droite :

  • Lettre : enfiler
  • * : défiler
  1. I N V O * * * *
  2. V * R E * * T *
Réponse
  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)

Exercice : 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)

Réponse

Réponses possibles :

  1. bleu - rouge - jaune - turquoise - orange - vert - noir
  2. 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 ?

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

Réponse

Réponses possibles :

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

Sources ​