Théorie des graphes/Parcours

Début de la boite de navigation du chapitre

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.

fin de la boite de navigation du chapitre

Parcours en largeur

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

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

Parcours en profondeur

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

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