Parcours de graphes

15.1 Introduction et motivation

Représenter un graphe (chapitre 14) ne suffit pas : il faut savoir le parcourir — visiter systématiquement tous les sommets atteignables depuis un point de départ. C'est l'opération de base dont découlent quantité d'algorithmes : tester si deux sommets sont reliés, compter les composantes, trouver le plus court chemin en nombre d'arêtes, détecter un cycle, colorier un graphe.

Deux stratégies s'opposent et se complètent : le parcours en profondeur (DFS), qui s'enfonce le plus loin possible avant de revenir, et le parcours en largeur (BFS), qui explore par cercles concentriques autour du départ. Le premier s'écrit naturellement par récursion (ou avec une pile) ; le second avec une file — les structures du chapitre 8. Tout au long, un tableau de marquage évite de visiter deux fois le même sommet (donc de tourner en rond). On suppose les graphes donnés en listes d'adjacence (int list array).

15.2 Le parcours en profondeur (DFS)

Principe : visiter un sommet, le marquer, puis visiter récursivement chacun de ses voisins non encore visités. On s'enfonce dans une branche jusqu'au bout avant d'explorer les suivantes.

let parcours_profondeur adj depart =
  let n = Array.length adj in
  let vu = Array.make n false in
  let ordre = ref [] in
  let rec visite s =
    if not vu.(s) then begin
      vu.(s) <- true;
      ordre := s :: !ordre;
      List.iter visite adj.(s)
    end
  in
  visite depart;
  !ordre        (* sommets visités, en ordre inverse de découverte *)