Compter les composantes connexes

Par unir & trouver — il n'y a rien à écrire, le compteur de l'exercice « Ce que la structure refuse de faire » fait tout :

(* Nombre de composantes connexes. Entrees : n sommets, liste d'aretes (u,v).
   Complexite : O(m alpha(n)), soit O(m) en pratique. *)
let composantes n aretes =
  let u = creer n in
  List.iter (fun (a, b) -> ignore (unir u a b)) aretes;
  u.classes

Correction : invariant de la boucle — après traitement d'un préfixe des arêtes, les classes de la structure sont exactement les composantes connexes du graphe partiel formé de ce préfixe. Il tient à l'initialisation ($n$ sommets isolés) et se conserve à chaque arête. Terminaison : la liste est finie.

Par parcours : on construit les listes d'adjacence, puis on lance un parcours depuis chaque sommet non encore visité et l'on compte les lancements. Complexité $\Theta (n+m)$, c'est-à-dire mieux que $O(m\alpha (n))$ à la constante près, et sans structure annexe.

Alors pourquoi unir & trouver ? Parce que les deux ne répondent pas à la même question.

• Le parcours suppose le graphe connu d'avance. Il faut avoir construit les listes d'adjacence, donc avoir vu toutes les arêtes.
• Unir & trouver traite les arêtes au fil de l'eau et répond à tout moment. C'est la connexité dynamique : après chaque nouvelle arête, on sait immédiatement combien il reste de composantes, sans rien recalculer.

Une simulation le rend concret : en tirant des arêtes au hasard entre $n=1000$ sommets jusqu'à ce que le graphe soit connexe, il en faut en moyenne $3731$ (mesuré sur $60$ tirages) ; la théorie du collectionneur de vignettes prévoit $\frac{n}{2}\ln n\approx 3454$. Avec un parcours, il aurait fallu tout recommencer après chaque arête ; avec unir & trouver, le compteur descend tout seul.