Un parcours de graphe fournit souvent un outil pour étudier certaines propriétés du graphe : un graphe non orienté est-il connexe ? est-il biparti ? quels sont ses points d’articulation? un graphe orienté est-il fortement connexe?… Les parcours servent aussi de base à d’autres algorithmes.
Après une présentation générale des parcours, nous développons plus particulièrement les parcours en largeur et en profondeur. Nous détaillons ensuite plusieurs applications des parcours.
Nous allons définir une sorte de « moule » décrivant un parcours de graphe à partir d’un sommet donné. C’est à partir de ce moule que l’on pourra insérer certaines instructions de façon à utiliser le parcours pour un objectif donné. Nous traiterons d’abord le cas orienté, puis le cas non orienté.
Dans un parcours de graphe à partir d’un sommet donné r, on « atteint » de proche en proche tous les sommets accessibles à partir de r sous la contrainte de n’atteindre un nouveau sommet qu’à partir d’un sommet déjà atteint. Par ailleurs, on ne veut pas atteindre deux fois le même sommet. En général, pendant le parcours, un certain traitement, dépendant de l’application, est effectué sur les sommets. Dans un parcours, on rencontre aussi chaque arc dont l’origine est accessible à partir de r, ce qui permet si nécessaire de tenir compte de ces arcs pour une application donnée. Durant le parcours, les arcs qui permettent d’atteindre un sommet à partir d’un sommet donné définissent ce qu’on appelle l’arborescence du parcour…