Parcours de graphes et plus courts chemins
Cours · informatique (MP2I/MPI), chapitre 19 · MP2I et MPI · le début du chapitre, la suite sur Adloun
19.1 Une seule idée, deux structures
Parcourir un graphe, c'est visiter chaque sommet accessible une fois et une seule. L'algorithme tient en quatre lignes, et il est le même pour les deux parcours du programme : on garde une réserve de sommets découverts mais non traités, on en retire un, on marque et on empile ses voisins.
Tout tient dans la nature de la réserve.
| Réserve | Parcours obtenu | Ce qu'il donne |
|---|---|---|
| Pile (lifo) | en profondeur | tri topologique, cycles, composantes |
| File (fifo) | en largeur | plus courts chemins à arcs unitaires |
| File de priorité | Dijkstra | plus courts chemins pondérés |
C'est l'illustration la plus nette du chapitre chap:abstraction. Les trois lignes du tableau partagent le même squelette ; seule la structure de réserve change, et avec elle la nature du parcours. Une pile explore au plus loin avant de revenir ; une file explore par cercles concentriques ; une file de priorité explore par distance croissante.
19.2 Le squelette
(* Marque tous les sommets accessibles depuis s. g est en listes d'adjacence.
Précondition : 0 <= s < Array.length g. *)
let parcours g s =
let n = Array.length g in
let vu = Array.make n false in
let reserve = creer () in (* pile OU file : tout est là *)
ajouter reserve s;
vu.(s) <- true;
while not (est_vide reserve) do
let u = retirer reserve in
List.iter (fun v ->
if not vu.(v) then begin
vu.(v) <- true; (* on marque EN AJOUTANT *)
ajouter reserve v
end) g.(u)
done;
vuSi l'on ne marquait qu'au retrait, un sommet ayant plusieurs prédécesseurs serait ajouté plusieurs fois à la réserve avant d'être traité. Le résultat resterait correct, mais la complexité pourrait exploser — jusqu'à sur certains graphes. La ligne vu.(v) <- true doit accompagner l'ajout.
Avec des listes d'adjacence, tout parcours est en : chaque sommet entre au plus une fois dans la réserve, et chaque arc est examiné au plus une fois. Avec une matrice d'adjacence, il devient — ce que le chapitre chap:graphes chiffrait.
19.3 Le parcours en profondeur
Avec une pile, ou — plus naturellement — par récursion, la pile d'exécution jouant le rôle de la réserve :
(* Marque les sommets accessibles depuis u. vu est modifié en place. *)
let rec profondeur g vu u =
vu.(u) <- true;
List.iter (fun v -> if not vu.(v) then profondeur g vu v) g.(u)Les arcs qui ont servi à découvrir un sommet forment un arbre — l'arborescence du parcours. Les autres arcs se classent : arcs arrière (vers un ancêtre), avant (vers un descendant déjà vu), transverses. La présence d'un arc arrière caractérise l'existence d'un cycle.
19.3.1 Composantes connexes
(* Renvoie un tableau c tel que c.(u) est le numéro de la composante de u.
Complexité : Theta(n + m). *)
let composantes g =
let n = Array.length g in
let c = Array.make n (-1) in
let numero = ref 0 in
for s = 0 to n - 1 do
if c.(s) = -1 then begin (* sommet encore non atteint *)
let rec visiter u =
c.(u) <- !numero;
List.iter (fun v -> if c.(v) = -1 then visiter v) g.(u)
in
visiter s;
incr numero
end
done;
cLa boucle extérieure relance un parcours depuis chaque sommet non encore atteint : c'est ce qui permet d'atteindre toutes les composantes, et non seulement celle du départ. Le nombre final de !numero est le nombre de composantes.
Exercices du chapitre
- Marquer au retrait : chiffrer ce que cela coûte corrigé
- Le parcours en profondeur itératif n'est pas le récursif corrigé
- Bicolorabilité par un parcours en largeur corrigé
- Combien d'insertions dans la file de priorité ? corrigé
- Poids négatifs : ajouter une constante ne sauve rien corrigé
- L'ordre des boucles de Floyd-Warshall : le contre-exemple minimal corrigé