Unir & trouver, arbres couvrants

Cours · informatique (MP2I/MPI), chapitre 23 · MP2I et MPI · le début du chapitre, la suite sur Adloun

Le parcours en largeur d'un graphe : les sommets sont visités par distances croissantes depuis la source.

23.1 Une structure faite pour une seule question

La question est : ces deux éléments sont-ils dans le même paquet ? Et l'opération est : fusionne ces deux paquets. Rien d'autre. On ne sait pas séparer, on ne sait pas énumérer un paquet, on ne sait même pas le nommer autrement que par un représentant arbitraire.

Cette pauvreté est la source de l'efficacité, et le programme la traite comme un cas d'école de la démarche du chapitre chap:abstraction : « on commence par donner des implémentations naïves de la structure unir & trouver qui privilégient soit l'opération unir, soit l'opération trouver, avant de donner une implémentation par des arbres qui permet une mise en œuvre efficace des deux opérations ».

Définition 23.1Le contrat

La structure représente une partition d'un ensemble ${0, \dots, n - 1}$ en classes d'équivalence.

Opération	Rôle	Effet
`creer(n)`	constructeur	$n$ classes, chacune à un élément
`trouver(x)`	accesseur	le représentant de la classe de $x$
`unir(x, y)`	transformateur	fusionne les classes de $x$ et $y$

Deux éléments sont dans la même classe si et seulement si trouver leur rend le même représentant.

23.2 Deux mises en œuvre naïves

Exemple 23.2Privilégier trouver

Un tableau $c$ où $c [x]$ est directement le numéro de classe de $x$ .


int trouver(const int c[], int x) { return c[x]; }         /* O(1) */

void unir(int c[], int n, int x, int y) {                  /* O(n) */
    int a = c[x], b = c[y];
    if (a == b) { return; }
    for (int k = 0; k < n; k = k + 1) { if (c[k] == b) { c[k] = a; } }
}

trouver est immédiat, unir doit balayer tout le tableau.

Exemple 23.3Privilégier unir

Chaque élément pointe vers un parent, et l'union se contente d'accrocher une racine sous l'autre.


int trouver(const int p[], int x) {                        /* O(hauteur) */
    while (p[x] != x) { x = p[x]; }
    return x;
}

void unir(int p[], int x, int y) {                         /* O(hauteur) */
    p[trouver(p, x)] = trouver(p, y);
}

unir est bon marché — mais rien n'empêche l'arbre de dégénérer en peigne, et trouver devient alors $O (n)$ . C'est exactement le défaut de l'arbre binaire de recherche non équilibré du chapitre chap:tas.

23.3 La mise en œuvre efficace

Deux optimisations, chacune tenant en une ligne, et dont la conjonction rend la structure quasi instantanée.

Exercices du chapitre

Ce que la structure refuse de faire corrigé
Les deux naïves, chiffrées corrigé
La faute qui sépare au lieu d'unir corrigé
La borne $lo g_{2} n$ est atteinte corrigé
Le rang ment, et c'est voulu corrigé
Combien d'arbres couvrants minimaux ? corrigé

La suite du cours · Tous les exercices du chapitre