Parcourir un graphe

Une seule idée, deux rangements

Le principe commun tient en trois phrases. On garde une réserve de sommets découverts mais pas encore traités. Tant qu'elle n'est pas vide, on en sort un, on le traite, et on y met ses voisins pas encore visités. Une marque empêche de traiter deux fois le même sommet ; le moment où l'on pose cette marque dépend de la réserve, et la suite du chapitre dit pourquoi.

La file et la pile sont les deux structures du chapitre d'algorithmique sur les piles et les files, qui déroule déjà un parcours en largeur sur les postes d'un atelier.

Pourquoi cela change tout. Une file traite les sommets par ordre de découverte, donc par distance croissante au départ : le parcours avance par couches concentriques.
Une pile traite en priorité le dernier découvert, donc s'enfonce le long d'une branche jusqu'au bout avant de revenir : le parcours suit la structure du graphe.
La file donne les distances. La pile donne les branches, et avec elles les hiérarchies et l'ordre dans lequel on termine les sommets.

Le parcours en largeur, pas à pas

Dérouler la figure ci-dessous pas à pas. La file y est dessinée sous le graphe, comme une rangée de jetons : un sommet entre à droite et sort à gauche. Le petit numéro posé sur un sommet est son rang de visite, le nombre écrit dessous sa distance au départ, et les arêtes en gras forment l'arbre de parcours : celles par lesquelles chaque sommet a été découvert. Quand un sommet a plusieurs voisins nouveaux, ils sont pris dans l'ordre de sa liste de voisins, ici l'ordre alphabétique. C'est une convention : une autre donnerait un autre ordre de visite, et la figure écrit sous le graphe les listes qu'elle suit.

L'ordre de visite est A B C D E F G. Ce qui n'est pas arbitraire, c'est la succession des couches : d'abord le sommet de départ, puis tous ceux à une arête (B, C), puis tous ceux à deux arêtes (D, E), et ainsi de suite ; sur la figure, ce sont les colonnes. À l'intérieur d'une couche, l'ordre vient de la convention alphabétique.

Le parcours en profondeur, sur le même graphe

Même graphe, même départ, une pile au lieu d'une file. Regarder comme le tracé change de nature, et suivre la pile sous le graphe : un sommet y entre et en sort par le dessus, et un même sommet peut y entrer plusieurs fois. Les sommets restent rangés par distance à A, ce qui fait voir le parcours aller et venir entre les colonnes au lieu de les balayer dans l'ordre.

L'ordre est A B D C E F G. Le BFS avait visité C en troisième position, le DFS le visite en quatrième, après être descendu jusqu'à D. Et surtout, l'arbre de parcours du DFS est un long chemin, A B D C E F G, là où celui du BFS était étalé.

Les deux parcours en Python

Le code emploie une file toute faite : deque, du module collections, où append ajoute à droite et popleft() retire à gauche l'élément le plus ancien, en temps constant, là où liste.pop(0) décalerait tous les autres. La pile, elle, est une simple liste : append empile, pop() dépile le dernier arrivé. Le graphe est un dictionnaire qui associe à chaque sommet la liste de ses voisins, rangés ici par ordre alphabétique.

Les voisins sont rangés dans des listes, qui gardent leur ordre : le résultat est le même à chaque exécution. Avec des ensembles set, qui n'ont pas d'ordre fixe, le même BFS pourrait rendre A B C D E F G une fois et A C B E D F G la suivante, et il faudrait trier les voisins avant de les parcourir.

La version récursive, et l'ordre de fin

Écrit en récursif, le parcours en profondeur donne deux ordres d'un coup : celui dans lequel on arrive sur les sommets, et celui dans lequel on les termine, quand tout ce qui a été découvert depuis eux est exploré.

La version récursive marque un sommet en y arrivant, et c'est juste : l'appel pour C n'a lieu qu'au moment où l'on s'y enfonce, pas quand A le découvre. L'ordre d'arrivée, dit aussi ordre préfixe, est celui de la figure : A B D C E F G.

C'est l'ordre qu'il faut chaque fois qu'un sommet ne peut être traité qu'après tout ce qui en dépend. Dans un arbre, il traite les enfants d'un nœud avant le nœud lui-même : c'est ainsi qu'on résout un arbre de jeu en partant des feuilles, dans le chapitre sur les jeux séquentiels. Sur un graphe orienté sans circuit, en relançant le parcours depuis chaque sommet non vu, l'ordre de fin lu à l'envers donne un tri topologique, question que le chapitre sur les graphes orientés traite par une autre méthode.

Ce que la complexité vaut

Dans un BFS, chaque sommet entre au plus une fois dans la file. Dans le DFS itératif, un sommet peut entrer dans la pile une fois par arête qui le touche (neuf empilements pour sept sommets sur le graphe du chapitre, comme le compte la figure), soit au plus $2m + 1$ entrées en tout. Dans les deux cas, chaque sommet n'est traité qu'une fois, et chaque arête est examinée deux fois, une par extrémité. D'où, avec des listes d'adjacence :

Le parcours depuis un sommet s'arrête à sa composante, et peut donc coûter bien moins ; le parcours complet, relancé depuis chaque sommet non vu, atteint tout le graphe et coûte exactement de l'ordre de $n + m$.

Avec une matrice, trouver les voisins d'un sommet coûte $\Theta(n)$ au lieu de $\Theta(\deg(v))$, et le parcours complet devient $\Theta(n^2)$. Sur les 200 000 carrefours du chapitre précédent, à dix millions de cases lues par seconde, c'est la différence entre moins d'une seconde et plus d'une heure.

Ce qu'on obtient en plus, presque gratuitement

Les composantes connexes

Un parcours atteint exactement la composante de son sommet de départ. Pour décomposer tout le graphe, on relance un parcours depuis chaque sommet pas encore vu.

Trois couleurs, trois composantes. Le coût total reste $\Theta(n + m)$, puisque chaque sommet n'est traité que dans un seul parcours.

Le test de bipartisme

Un graphe est biparti si et seulement s'il n'a aucun cycle impair. Le BFS le teste en une passe : on colorie le sommet de départ en 0, chaque voisin découvert reçoit la couleur opposée à celle du sommet qui le découvre, et l'on vérifie qu'aucune arête ne relie deux sommets de même couleur.

Quand une arête relie deux sommets de même couleur, le test échoue. Sur le graphe suivant, le BFS parti de A donne la couleur 0 à D et à E, tous deux à distance 2, et l'arête D-E les relie. Cette arête ne suffit pas à convaincre : elle ne dit pas pourquoi ses deux extrémités devaient recevoir la même couleur. Ce qui le dit, c'est le cycle qu'elle ferme avec les deux branches de l'arbre de parcours qui mènent à ses extrémités, remontées jusqu'à leur premier ancêtre commun, ici A.

La longueur de ce cycle est toujours impaire. Les deux branches descendent du même ancêtre, et leurs extrémités sont à la même distance du départ ou à des distances qui diffèrent d'une unité ; comme elles portent la même couleur, elles sont à la même distance, donc les deux branches ont la même longueur $k$, et le cycle a $2k + 1$ arêtes.

La détection de cycle

Dans un graphe non orienté, le DFS trouve un cycle dès qu'il rencontre une arête vers un sommet déjà vu qui n'est pas son père immédiat. Cette arête, dite arête arrière, ferme un cycle avec le chemin de l'arbre. Dans un graphe non orienté, un BFS le ferait aussi bien, avec le même critère ; c'est dans un graphe orienté que le DFS devient indispensable, comme le montrera le chapitre sur les graphes orientés.

Lequel pour quoi.

BFS : plus court chemin en nombre d'arêtes, distance, couches, bipartisme. Il donne les distances parce qu'il explore par couches.
DFS : structure arborescente, ordre de fin, et, dans un graphe orienté, détection des circuits et tri topologique. Il révèle la structure parce qu'il suit les branches jusqu'au bout.
Quand les arêtes portent des poids positifs, la file devient une file de priorité, qui rend toujours le sommet en attente le plus proche du départ, et le BFS devient Dijkstra ; avec des poids négatifs, il faut autre chose. C'est le chapitre 5.

Mettre en pratique