Les parcours en profondeur et le parcours en largeur sont deux algorithmes permettant de déterminer les composantes connexes d'un graphe. Avec des petites variations ils pourront aussi déterminer la nombre de sommets séparant un sommet des autres ou déterminer la présence de cycle dans le graphe.
La différence entre les deux deux parcours est lié dans l'utilisation dans l'en de file et de l'autre des piles.
Parcours en largeur.
Diamètre et rayon d'un graphe.
On peut avec une petite modification indiquer le nombre de d’arêtes séparant les sommets du sommet de départ. Par suite on peut avoir le diamètre (distance maximale entre deux sommets du graphe) et le rayon (distance minimale permettant de passer d'un certain sommet aux autres) d'un graphe connexe.
Parcours en profondeur.
Détermination d'un cycle.
On peut en modifiant un peu l'algorithme du parcours en profondeur déterminer la présence d'un cycle pour cela il suffit de savoir si au bout d'un moment on rejoint un sommet colorié en vert.
On lance le parcours pour tous les sommets du graphe et on regarde si on arrive à un cycle.
Si le graphe est non orienté il faut cependant s'assurer de ne pas retourner en arrière.