Leçons de niveau 16

Théorie des graphes/Parcours

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
Début de la boite de navigation du chapitre
Parcours
Icône de la faculté
Chapitre no 3
Leçon : Théorie des graphes
Chap. préc. :Propriétés
Chap. suiv. :Arbres couvrants
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Théorie des graphes : Parcours
Théorie des graphes/Parcours
 », n'a pu être restituée correctement ci-dessus.

Parcourir un graphe permet de savoir si celui-ci est connexe ou non. Lorsque l’on parcourt un graphe, on part d'un sommet quelconque et on explore tous les autres sommets de proche en proche. Il existe deux types de parcours de graphe : en largeur et en profondeur.

Parcours en largeur[modifier | modifier le wikicode]

Ce type de parcours utilise une file pour déterminer si le graphe est connexe. Il fonctionne de la manière suivante :

  1. On met le nœud de départ dans la file ;
  2. On retire le nœud en tête de file afin d'examiner ses sommets adjacents ;
  3. On note le nœud que l’on examine ;
  4. On ajoute tous les voisins non examinés dans la file ;
  5. Si la file n’est pas vide, on reprend l'étape 2.

Si tous les nœuds ont été examinés à l'issu de l'algorithme, le graphe est connexe.

Exemple[modifier | modifier le wikicode]

Graph.traversal.example.png

Dans ce cas, on parcourt le graphe dans l’ordre suivant : A, B, C, E, D, F, G.

Parcours en profondeur[modifier | modifier le wikicode]

Ce type de parcours utilise plutôt une pile pour déterminer si le graphe est connexe. Lorsque l’on parcourt le graphe, on part d'un sommet quelconque puis l’on explore à fond le premier chemin. Une fois le chemin fini ou lorsque l’on retombe sur un sommet déjà exploré, on recommence en partant du deuxième voisin. L'exemple indique plus en détail son fonctionnement.

Exemple[modifier | modifier le wikicode]

Si l’on reprend l'exemple précédent, on parcourt le graphe dans l’ordre suivant : A, B, D, F, E, C, G.