Parcourir un graphe
Ce que ce chapitre apporte
- Dérouler à la main un parcours en largeur et un parcours en profondeur.
- Expliquer pourquoi la file donne les couches et la pile donne les branches.
- Écrire les deux parcours, en itératif, et savoir où marquer un sommet.
- Calculer les distances et les plus courts chemins en nombre d'arêtes.
- Décomposer un graphe en composantes connexes.
- Détecter un cycle, et tester si un graphe est biparti.
- Justifier la complexité \Theta(n + m).
Une seule idée, deux rangements
Le principe commun tient en quatre lignes. 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 jamais vus. On marque chaque sommet pour ne jamais le mettre deux fois.
Le parcours en largeur (BFS) sort de la réserve le sommet le plus anciennement entré : la réserve est une file.
Le parcours en profondeur (DFS) sort le sommet le plus récemment entré : la réserve est une pile.
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 cycles et les hiérarchies.
Le parcours en largeur, pas à pas
Déroulez l'animation ci-dessous. Le numéro en orange est le rang de visite, les arêtes en gras forment l'arbre de parcours : celles par lesquelles chaque sommet a été découvert.
L'ordre de visite est A B C D E F G, et il n'est pas arbitraire : d'abord le sommet de départ, puis tous ceux à une arête, puis tous ceux à deux arêtes, et ainsi de suite.
Le BFS visite les sommets par distance croissante au sommet de départ. La distance calculée est donc le plus court chemin en nombre d'arêtes.
Si l'on attend de le retirer, il peut être ajouté plusieurs fois par des voisins différents : la file gonfle, le parcours devient quadratique sur un graphe dense, et les distances calculées peuvent être fausses.
C'est l'erreur la plus fréquente sur ce code, et elle ne se voit pas sur un petit exemple.
Le parcours en profondeur, sur le même graphe
Même graphe, même départ, une pile au lieu d'une file. Regardez comme le tracé change de nature.
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 une longue chaîne, là où celui du BFS était étalé.
Sur un graphe profond, cette pile peut déborder. En Python, la limite par défaut est d'environ mille appels imbriqués : un chemin de dix mille sommets fait échouer le programme. La version itérative avec une pile explicite n'a pas cette limite.
parent, et il ne coûte rien.On remonte ensuite de la cible vers le départ, puis on retourne la liste. Ce mécanisme resservira à l'identique pour Dijkstra.
Ce que la complexité vaut
Chaque sommet entre au plus une fois dans la réserve, et chaque arête est examinée deux fois, une par extrémité. D'où :
Avec une matrice, trouver les voisins d'un sommet coûte au lieu de , et le parcours devient . Sur un graphe creux, c'est la différence entre une seconde et une heure.
1.Lequel des deux parcours donne les plus courts chemins en nombre d'arêtes ?
2.À quel moment marque-t-on un sommet comme vu, dans un BFS ?
3.Combien coûte un parcours sur un graphe donné par sa matrice d'adjacence ?
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 , 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 à la sienne, et l'on vérifie qu'aucune arête ne relie deux sommets de même couleur.
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.
DFS : cycles, composantes fortement connexes, tri topologique, structure arborescente. Il révèle la structure parce qu'il suit les branches jusqu'au bout.
Quand les arêtes portent des poids, la file devient une file de priorité et le BFS devient Dijkstra. C'est le chapitre 5.
Exercices type
Pourquoi le BFS donne-t-il les plus courts chemins, et pas le DFS ?
Parce que la file traite les sommets dans l'ordre où ils ont été découverts, donc par distance croissante au départ.
Quand le BFS retire un sommet à distance , tous les sommets à distance ou moins sont déjà découverts. Le premier chemin trouvé vers un sommet est donc le plus court.
Le DFS, lui, s'enfonce dans une branche : il peut atteindre un sommet voisin du départ après un détour de vingt arêtes. Le chemin qu'il trouve est un chemin, jamais garanti minimal.
Que se passe-t-il si on marque un sommet au défilement plutôt qu'à l'enfilement ?
Le même sommet peut entrer plusieurs fois dans la file, une fois par voisin qui le découvre.
Conséquences : la file peut contenir jusqu'à éléments au lieu de , le parcours devient quadratique sur un graphe dense, et si l'on écrit la distance au moment du défilement, une valeur plus grande peut écraser une valeur correcte.
Le parcours reste correct sur de petits exemples, ce qui rend l'erreur difficile à repérer : elle ne se manifeste qu'à l'échelle.
Comment tester qu'un graphe est biparti, et que fournir comme preuve du contraire ?
Par un BFS bicolore : on colorie le départ en 0, chaque sommet découvert reçoit la couleur opposée à celle de son découvreur.
Si l'on rencontre une arête entre deux sommets de même couleur, le graphe n'est pas biparti, et cette arête ferme un cycle de longueur impaire.
C'est cette arête qu'il faut donner comme preuve : elle est vérifiable en une ligne, alors qu'affirmer « j'ai essayé toutes les partitions » ne prouve rien.
Un DFS récursif échoue avec « maximum recursion depth exceeded ». Pourquoi, et que faire ?
Parce que la profondeur de récursion suit la longueur de la plus longue branche de l'arbre de parcours. Sur un graphe en chaîne de 10 000 sommets, cela fait 10 000 appels imbriqués, alors que Python en autorise environ mille par défaut.
Deux réponses. Augmenter la limite avec sys.setrecursionlimit règle le symptôme, mais la pile système peut déborder pour de bon.
La bonne réponse est la version itérative avec une pile explicite : elle n'a d'autre limite que la mémoire disponible.
Comment compter les composantes connexes, et quel est le coût total ?
On parcourt les sommets ; chaque fois qu'on en trouve un non visité, on lance un parcours complet depuis lui et on compte une composante de plus.
Le coût total reste , et non : chaque sommet et chaque arête n'est traité que dans un seul parcours, celui de sa propre composante.
C'est le même schéma pour toute propriété qui se calcule composante par composante.
Sur un graphe donné par sa matrice d'adjacence, quelle est la complexité d'un BFS ?
.
Chaque sommet est défilé une fois, et pour chacun il faut lire toute sa ligne de matrice pour trouver ses voisins, soit cases, y compris les zéros.
Sur un graphe creux où , cela transforme un algorithme linéaire en algorithme quadratique. C'est la raison la plus concrète de préférer les listes d'adjacence.
La méthode
- Choisis la réserve : file pour les distances, pile pour la structure.
- Marque à l'enfilement, toujours.
- Mémorise le parent si tu veux le chemin et pas seulement sa longueur.
- Trie les voisins quand tu veux un résultat reproductible, en devoir comme en test.
- Relance depuis chaque sommet non vu pour couvrir toutes les composantes.
- Préfère la version itérative dès que le graphe peut être profond.
- Donne l'arête fautive comme preuve qu'un graphe n'est pas biparti.
En résumé
- BFS et DFS ne diffèrent que par la réserve : file contre pile.
- La file explore par couches, la pile s'enfonce dans les branches.
- Le BFS donne les distances et les plus courts chemins en nombre d'arêtes.
- Un sommet se marque à l'enfilement.
- Le tableau parent reconstruit le chemin, pas seulement sa longueur.
- Les deux parcours coûtent en listes d'adjacence, en matrice.
- Relancer depuis chaque sommet non vu donne les composantes connexes, toujours en .
- Un BFS bicolore teste le bipartisme et fournit le cycle impair en cas d'échec.
- Une arête arrière en DFS, vers un sommet vu autre que le père, ferme un cycle.
Et ensuite ? L'arbre de parcours qui apparaît dans les animations n'est pas un accident : c'est un objet à part entière, et le chapitre suivant lui est consacré, jusqu'à la question de l'arbre couvrant de poids minimal.