Parcours de graphes
Cours · informatique (tronc commun des prépas scientifiques), chapitre 13 · prépas scientifiques, tronc commun · le début du chapitre, la suite sur Adloun
13.1 Introduction et motivation
Un graphe en mémoire ne livre rien de lui-même : pour savoir si deux stations de métro sont reliées, si un labyrinthe a une sortie, si un logiciel a des dépendances circulaires, il faut explorer — partir d'un sommet et visiter, de proche en proche, tout ce qui est accessible. C'est le parcours de graphe, l'algorithme fondamental du domaine, dont presque tout le reste (connexité, cycles, plus courts chemins) n'est qu'une instrumentation.
Or il n'y a essentiellement que deux façons d'explorer, et elles diffèrent par un seul choix : quand plusieurs directions s'offrent, traite-t-on d'abord la dernière découverte — on s'enfonce, c'est le parcours en profondeur — ou la première — on rayonne par cercles, c'est le parcours en largeur ? Ce choix est exactement celui d'une structure de données : une pile ou une file, que ce chapitre introduit pour l'occasion — avec un détour obligé par leur implémentation, car la file naïve en liste Python cache un piège de complexité que le programme tient à montrer. À l'arrivée : la connexité et ses composantes, la détection de cycles, et les distances en nombre d'arêtes — le plus court chemin non pondéré, marchepied du chapitre 14.
13.2 Piles et files
13.2.1 Deux disciplines d'attente
Une pile (stack) est une collection où l'on insère et retire du même côté — le sommet. Discipline LIFO (last in, first out) : le dernier entré sort le premier, comme une pile d'assiettes. Opérations : empiler, dépiler, tester la vacuité — toutes exigées en . En Python, la liste fait une pile parfaite :
pile = []
pile.append(x) # empiler : O(1)
x = pile.pop() # dépiler (le DERNIER ajouté) : O(1)
len(pile) == 0 # vide ?Une file (queue) insère d'un côté et retire de l'autre. Discipline FIFO (first in, first out) : le premier entré sort le premier — la file d'attente du guichet. Opérations : enfiler, défiler, vacuité, en aussi.
La tentation est d'écrire la file avec une liste : file.append(x) pour enfiler, file.pop(0) pour défiler. C'est correct — et c'est un piège de complexité : pop(0) retire la première case, et la liste décale toutes les autres — coût à chaque défilement ! Un parcours qui défile sommets devient en silence. La solution du programme : le module dédié collections.deque (double-ended queue), conçu pour des insertions et retraits en aux deux bouts :
from collections import deque
file = deque()
file.append(x) # enfiler à droite : O(1)
x = file.popleft() # défiler à gauche : O(1)C'est le « choix éclairé des collections » du chapitre 10, version structure : même contrat, complexités opposées — et l'écart se mesure (exercice 4).
13.3 Le parcours en profondeur
13.3.1 S'enfoncer d'abord
Le parcours en profondeur (DFS, depth-first search) explore depuis un sommet source en suivant un chemin aussi loin que possible, et ne revient en arrière que bloqué. Version itérative, avec une pile et un ensemble de sommets visités :
def parcours_profondeur(G: dict, source) -> list:
"""Renvoie la liste des sommets accessibles depuis source,
dans l'ordre de leur visite."""
visites = []
vus = {source} # marqués : dans la pile ou déjà visités
pile = [source]
while pile: # variant : nb de sommets jamais empilés... voir preuve
s = pile.pop()
visites.append(s)
for v in G[s]:
if v not in vus:
vus.add(v)
pile.append(v)
return visitesLa version récursive, équivalente, confie la pile à la machine (chapitre 6 — c'est la pile d'appels) :
def dfs(G: dict, s, vus: set, visites: list) -> None:
vus.add(s)
visites.append(s)
for v in G[s]:
if v not in vus:
dfs(G, v, vus, visites)Exercices du chapitre
- Mesurer le piège de la file-liste corrigé
- Sortir du labyrinthe corrigé
- Le graphe est-il un arbre ? corrigé
- Le graphe biparti, ou le coloriage en deux couleurs corrigé
- L'échelle des mots corrigé
- Les arbres, preuve du théorème corrigé