Les trois parcours d'un même graphe

Mesures :

profondeur recursive depuis 0 : 0 1 3 6 4 5 2 7
largeur depuis 0              : 0 1 2 3 4 5 6 7
distances                     : 0 1 1 2 2 2 3 4

En profondeur, on descend : $0\to 1\to 3\to 6$, puis depuis $6$ on visite $4$ (déjà accessible autrement), $5$, et de $5$ on remonte vers $2$ ; le sommet $7$ n'est visité qu'en tout dernier, alors qu'il est voisin de $6$, visité en quatrième. L'ordre de visite en profondeur ne dit rien de la distance.

En largeur, l'ordre coïncide ici avec la numérotation, par construction du graphe. Les distances forment les couches $\{0\}$, $\{1,2\}$, $\{3,4,5\}$, $\{6\}$, $\{7\}$.

L'arborescence du parcours en largeur est formée des arêtes ayant servi à découvrir un sommet ; le tableau des pères mesuré vaut $[-1;0;0;1;1;2;3;6]$ :

Sept arêtes sur neuf : une arborescence sur $n$ sommets en compte toujours exactement $n-1$. Les deux arêtes manquantes, $4-6$ et $5-6$, relient des sommets de couches consécutives sans avoir servi à découvrir : dans un parcours en largeur d'un graphe non orienté, toute arête hors de l'arborescence relie deux sommets de couches identiques ou consécutives — jamais davantage, sinon on aurait découvert plus tôt.