Union-find

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 \in \{ 1, \ldots, 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(N^2)\). 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(N^2)\).

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 \(\Omega(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.

Pour aller plus loin

L'article Union-find sur Wikipédia complète ce billet avec illustrations et références. Union-find fait également parti des cours d'algorithmique de France-IOI.

Discussion

There are no comments yet. Feel free to leave a reply using the form below.

Post a comment

You can use Markdown with $\LaTeX$ formulas in your comment.

You agree to the publication of your comment on this page under the CC BY 4.0 license.

Your email address will not be published.

© Stéphane Caron — All content on this website is under the CC BY 4.0 license.
τ