Le problème est le suivant : on dispose de plusieurs ensembles d'éléments
disjoints que l'on souhaite unir un certain nombre de fois, et ce de façon
efficace. Indexons les éléments par des entiers i∈{1,…,n}, et notons S(i) l'ensemble auquel l'élément i appartient.
L'approche naïve consiste à maintenir un tableau parent[i] en mémoire, et à
réunir deux ensembles en mettant à jour tous les éléments qui leur
appartiennent :
Union(S1, S2) :
Pour chaque élément i de S2 :
parent[i] = S1
Dans le pire des cas, les ensembles initiaux sont les singletons {i} pour chaque élément, et nous les réunissons un par un en choisissant des
singletons pour S1 : la complexité est alors O(N2). Mais il est
possible de faire mieux : l'algorithme union-find fait de même en O(N) !
Principe
Il n'est pas toujours évident de comprendre cet algorithme dans son étonnante
concision si l'on a pas étudié au préalable la notion d'arbre. L'idée est de maintenir
pour chaque élément-noeud l'index de son parent direct dans un arbre
représentant l'ensemble : chaque ensemble est alors identifié par l'indice de
la racine de son arbre. Unir deux ensembles est alors direct : il suffit de
définir la racine de l'un comme parente de la racine de l'autre. Mais, tel
quel, la complexité est toujours en O(N2).
Pseudo-code
Voici le pseudo-code de la fonction Find :
Find(i) :
si vide(parent[i]) :
retourner i
parent[i] = Find(parent[i])
retourner parent[i]
Réunir deux ensembles se fait alors en une seule instruction :
Union(i, j) :
parent[Find(i)] = Find(j)
Notez comme désormais nous identifions implicitement les ensembles par
l'identifiant i d'un de leurs éléments, la racine, pour lequel
parent[i] == i. À l'initialisation, tous les ensembles sont des singletons
{i}, et donc le tableau parent est initialisé par :
pour chaque i de 1 à n :
parent[i] = i
La puissance de l'union-find vient de la compression de chemin : lorsque l'on
demande à un noeud à quel ensemble il appartient, on ne se contente pas de
remonter dans l'arbre depuis le noeud jusqu'à la racine pour retrouver le
résultat : on « compresse » le chemin en définissant la racine
comme parent direct de chaque noeud rencontré. Toute requête ultérieure sur les
mêmes éléments s'exécutera alors en temps constant, du moins jusqu'à la
prochaine union.
Complexité
L'union-find présente un complexité « amortie » en O(N).
L'opération Find(i) retournant l'ensemble S[i] de l'élément
i s'effectue en O(N) car on examinera en pire cas chacun des
éléments de l'ensemble. De même, l'opération Union(i, j) effectue deux
appels à Find(i), un sur chaque élément : sa complexité en pire cas est
donc également en O(N).
Il ne faut cependant pas oublier que le pire cas est assez rare : en pratique,
il est peu probable de rencontrer un arbre de N éléments sans compression
de chemin aucune, et même lorsque c'est le cas, la moindre opération Find(i)
ferait tendre sa configuration vers le cas moyen, voire vers le meilleur cas
qui est Ω(1). Cet algorithme est efficace et de nombreux problèmes
plus généraux peuvent être résolus en l'utilisant : détection des composantes
connexes et fortement connexes, modélisation de jeux de réflexion, etc.
Unions plus judicieuses
Lors de l'union de deux ensembles de tailles différentes, définir celui qui
comporte le plus d'éléments comme descendant de celui qui en comporte le moins
engendrera des chemins plus longs à compresser. Une optimisation simple
consiste alors à maintenir, pour chaque ensemble i, le nombre d'éléments
qu'il contient et de reprendre la fonction union de telle sorte qu'elle
choisisse toujours l'arbre le plus petit comme descendant du plus gros. Ce
procédé est illustré par le code C++ suivant :
#include <cstdio>
const int MAX_NODES = 42;
int parent[MAX_NODES];
int size[MAX_NODES];
int uf_find(int node) {
if (parent[node] == 0) {
return node;
}
parent[node] = uf_find(parent[node]);
return parent[node];
}
void uf_union(int node1, int node2) {
int set1 = uf_find(node1);
int set2 = uf_find(node2);
int parent_set = (size[set1] >= size[set2]) ? set1 : set2;
int child_set = (size[set1] < size[set2]) ? set1 : set2;
if (set1 != set2) {
parent[child_set] = parent_set;
size[parent_set] += size[child_set];
}
}
int main() {
int cmd = 42;
int node;
for (node = 1; node < MAX_NODES; node++) {
size[node] = 1;
}
while (cmd) {
printf("0. Quitter\n1. Unir\n2. Index\n");
scanf("%d", &cmd);
if (cmd == 1) {
int node1, node2;
printf("Entrez deux noeuds a unir :\n");
scanf("%d%d", &node1, &node2);
uf_union(node1, node2);
} else if (cmd == 2) {
printf("Entrez le noeud a examiner :\n");
scanf("%d", &node);
printf("%d appartient a %d\n", node, uf_find(node));
}
}
return 0;
}
Dans ce code nous comptons sur le fait que le tableau global parent est
initialisé à zéro. Si ce n'est pas le cas, il faudra également initialiser ce
tableau dans la fonction principale.
Discussion
Feel free to post a comment by e-mail using the form below. Your e-mail address will not be disclosed.