Union-Find

Introduction

Le problème est le suivant : on dispose de nombreux ensembles d'éléments disjoints que l'on souhaite unir un certain nombre de fois, et ce de façon efficace. L'approche naïve consiste à maintenir, pour chaque élément, un index de l'ensemble auquel il appartient : unir deux ensembles revient alors à remettre à jour chacun des éléments qui leur appartiennent. La complexité en pire cas est donc O(N²), 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 simple : 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²).

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 retourner 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(noeud) retournant l'ensemble de l'élément noeud 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(noeud1, noeud2) effectue deux appels à FIND(noeud), 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 très peu probable de rencontrer un arbre de N éléments sans compression de chemin aucune, et même si c'était le cas, la moindre opération FIND(noeud) ferait tendre sa configuration vers le cas moyen, voire vers le meilleur cas qui est en temps constant. Cet algorithme est donc d'une incontestable efficacité 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.

Pseudo code

Dans la proposition de pseudo-code qui vient, on suppose que les noeuds sont indicés par des entiers naturels non-nuls, ce qui permet de définir avec la valeur 0 la constante indiquant que le noeud est racine de son propre ensemble (ie. il n'a pas de parent, ou il est son propre parent).

parent[] = {0, 0, ...}
 
Fonction FIND(noeud)
    Si (parent[noeud] = 0)
        Retourner (noeud)
    Sinon
        parent[noeud] = FIND(parent[noeud])
        Retourner (parent[noeud])
 
Fonction UNION(noeud1, noeud2)
    parent[FIND(noeud1)] = FIND(noeud2)

Améliorations

Unions plus judicieuses

L'une des améliorations possibles de cet Union-Find est issue d'un simple constat : 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. Il suffit alors de maintenir pour chaque ensemble le nombre d'éléments qu'il contient et de reprendre la fonction d'union de telle sorte qu'elle choisisse toujours l'arbre le plus petit comme descendant du plus gros. Ce procédé est illustré par l'implémentation ci-après.

Implémentations

Voici une brève implémentation en C++ utilisant la technique des unions par rang.

#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), set2 = uf_find(node2);
    int parentSet = (size[set1] >= size[set2]) ? set1 : set2;
    int sonSet = (size[set1] < size[set2]) ? set1 : set2;
 
    if (set1 != set2) {
        parent[sonSet] = parentSet;
        size[parentSet] += size[sonSet];
    }
}
 
int main()
{
    int cmd = 42, node, node1, node2;
 
    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) {
            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;
}