On retrouve les notions de parcours en largeur et en profondeur déjà rencontrées avec les arbres.
Passe par l'utilisation d'une file. Contrairement aux arbres, il peut y avoir des boucles dans les graphes et on risque de parcourir plusieurs fois un même sommet. On marque donc les sommets visités pour ne pas les visiter deux fois.
Dans un graphe, aucun sommet n'a de statut particulier. Il n'y a pas de racines. On doit choisir un sommet pour commencer le parcours. Le résultat obtenu dépendra du point de départ choisi. Dans notre exemple, le parcours part du sommet A.
Considérons le graphe non orienté suivant. Nous allons le parcourir en largeur à partir du sommet A.
On crée une file vide et on place A dans la file. A est marqué.
On lance maintenant une boucle qui se répète tant que la file n'est pas vide :
Prendre l'élément suivant dans la file (A), faire le traitement voulu sur A et placer ses voisins (B et C) dans la file et les marquer. Remarquez que l'on note aussi que l'on a atteint B et C en venant de A ce qui peut avoir son importance.
La file n'étant pas vide, on continue avec l'élément suivant (B). B a deux voisins, C et E. C est déjà marqué et est ignoré. E est marqué et placé dans la file.
On poursuit avec le prochain élément de la file (C). Son seul voisin non marqué est D. Celui ci est marqué et placé dans la file.
On poursuit avec le prochain élément de la file (E). Ses voisins F et G sont marqués et placés dans la file.
Le parcours se termine avec les D, G et F sans plus aucun ajout dans la file. Au final on aura parcouru dans l'ordre ABCEDGF.
Dans notre exemple, il n'y a aucune raison de faire B avant C ou G avant F.
Le parcours terminé, on a également un arbre qui décrit les chemins de A à tous les autres : Pour aller de A à G, le chemin est A–B–E–G.
En général, la difficulté posée par les graphes est qu'il existe de nombreux chemins entre deux sommets. On n'a pas ce problème dans un arbre car dans un arbre il n'y a pas de boucles. Les algorithmes consistent donc souvent à extraire un chemin unique ce qui revient à extraire un arbre du graphe.
Le parcours en profondeur utilise une pile. L'idée est de poursuivre l'exploration d'un chemin en particulier plutôt que d'explorer tous les chemins en même temps.
On crée une pile vide et on place le sommet de départ dans cette pile.
Tant que la pile n'est pas vide on va effectuer le traitement suivant : on prend le sommet de la pile, on le traite et on ajoute ses enfants (B et C) à la pile.
On poursuit avec le nouveau sommet de pile (B)
Différence avec le parcours en largeur : On poursuit sur le chemin B-E puisque E est sur le dessus de la pile, au lieu de revenir à l'étude de C.
On prend F au sommet de la pile.
Il ne reste ensuite qu'à traiter D, G et C. Dans cet exemple, le traitement s'effectue dans l'ordre ABEFDGC.