Algorithmes de connexité basés sur des pointeurs

Les algorithmes de connexité permettent de déterminer rapidement si deux sommets d'un graphe non orienté sont reliés par un chemin ou non, en créant un tableau de pointeurs qui implémente en fait une forêt d'arbres.

Chaque arbre créé par l'algorithme correspond à une composante connexe du graphe : ainsi, deux sommets seront reliés par un chemin du graphe si et seulement s'ils appartiennent au même arbre. La vérification se résume à la comparaison des racines des arbres respectifs.

Dans le cas d'un graphe fixé à l'avance, cet algorithme est moins efficace que l'algorithme de parcours en largeur et l'algorithme de parcours en profondeur, qui permettent de répondre à ce type de requête en temps constant après un prétraitement linéaire. Cependant, il est utile dans le cas d'un graphe construit de façon incrémentale.

Notations

Le graphe en question est noté $G=(S,A)$ , où $S$ est l’ensemble des sommets et $A$ l’ensemble des arêtes, avec $A\subset S\times S$ . Le graphe n’est pas orienté.

De manière à simplifier l’implémentation du problème, on suppose que $S=\{0,\dots ,n-1\}$ , où n est le nombre de sommets du graphe. Le graphe est présenté sous forme d'une liste de paires, chaque paire correspondant à une arête. Les implémentations seront écrites en langage générique.

Principe général

Les trois algorithmes présentés reposent sur la création et le regroupement d'arbres à partir du graphe ; le test de la connexité se ramène à vérifier que tous les sommets appartiennent finalement au même arbre.

On crée un tableau forêt de n éléments correspondant chacun à un sommet. Le contenu de la i-ième case du tableau est le sommet j vers lequel pointe le sommet i : si c’est une racine, i pointe vers lui-même ; sinon il pointe vers un autre sommet j différent de i (c'est-à-dire que i est un fils de j). Ainsi :

forêt[i]=j

\Rightarrow

i pointe vers j

Au début, chaque sommet est racine de l'arbre qu'il forme seul : forêt est initialisé avec les valeurs 0, 1, …, n-1.

On recherche la racine de l'arbre auquel appartient un sommet de la manière récursive suivante :

1 racine (i, forêt)                          (*trouve la racine d'un nœud i*)     
2    tant que i != forêt[i] faire
3       i:=forêt[i] done;                    (*suit les pointeurs jusqu'à tomber sur une racine*)
4    retourne i;;                            (*retourne le résultat*)

Ainsi, deux sommets sont reliés si et seulement s’ils pointent (directement ou indirectement) vers la même racine (racine(i,forêt)=racine(j,forêt)).

Les algorithmes de connexité possèdent deux facettes :

l’union : pour chaque arête donnée, l'algorithme relie les deux sommets dans la forêt ; autrement dit il fait en sorte qu'ils appartiennent au même arbre. C'est cette phase qui est propre aux algorithmes ;
l’appartenance : on détermine si deux sommets sont bien reliés en comparant la racine de leurs arbres respectifs. La vitesse de cette opération dépend de l'algorithme choisi car la profondeur des arbres de la forêt générée croît avec le temps d'exécution.

Algorithme d'appartenance rapide

Cet algorithme est le plus élémentaire des trois. Il repose sur une idée simple : on crée en fait des arbres où les feuilles sont directement reliées à leur racine. Ainsi, pour chaque arête (i, j) on enregistre les racines respectives r₁ de i et r₂ de j, puis on donne à tous les éléments qui avaient pour racine r₁ une nouvelle racine : r₂. Ainsi on relie entre eux tous les éléments liés à i et j en les faisant pointer vers la même racine. L'union se déroule donc ainsi:

1 union1(i, j, forêt)
2   r1=racine(i, forêt)                 (*ou directement r1=forêt[i]*)
3   r2=racine(j, forêt)                 (*ou directement r2=forêt[j]*) 
4   si r1 != r2                         (*si i et j ne sont pas déjà liés*)
5   pour k allant de 0 à n-1 faire
6     si forêt[k]=r1 alors              (*si le sommet est lié à i*)
7       forêt[k] :=r2                   (*le lier à j*)

On testera l'appartenance pour i et j d'une manière très rapide puisqu'il suffit que forêt[i] et forêt[j] soient égaux (les feuilles étant directement liées aux racines), d'où le nom d'algorithme d'appartenance rapide.

Par contre, l'opération d'union est très lente puisque pour chaque nouvelle paire l'algorithme doit parcourir l'intégralité de l'arbre. On peut prouver aisément que l'algorithme effectuera $n\cdot p$ itérations durant la phase union, avec n le nombre de sommets et p le nombre de paires. Le nombre de paires étant dans le pire des cas $n(n-1)/2$ , donc de l'ordre de $O(n^{2})$ , on a finalement un algorithme en $O(n^{3})$ , ce qui est peu satisfaisant. Nous allons maintenant nous intéresser à son symétrique : l'union rapide.

Algorithme d'union rapide

Une autre solution consiste à créer des arbres de structure plus complexe que ceux de l'algorithme précédent de manière à avoir une union beaucoup plus rapide. Le principe est le suivant : lorsque l'on veut lier i à j, on cherche d'abord leur racine de la manière indiquée dans le paragraphe principe général, puis on fait pointer la racine de i vers la racine de j: l'arbre contenant i devient alors un sous-arbre de celui contenant j.

1 union2(i, j, forêt)
2   r1=racine(i, forêt)             (*r1=racine de i*)
3   r2=racine(j, forêt)             (*r2=racine de j*)
4   si r1 != r2                     (*si les racines sont différentes*)
5     forêt[r1] :=r2                (*on fait pointer r1 vers r2*)

Comme vous le voyez, l'union est très simple. Cependant, l'appartenance est lente à cause de la fonction racine: en effet l'algorithme doit suivre récursivement des pointeurs pour arriver à la racine, et ce chemin peut dans cet algorithme être long. L'opération union, utilisant aussi la fonction racine, est elle aussi affectée.

Dans le pire des cas, l'algorithme reçoit dans l'ordre les paires (0,1), (1,2), (2,3), …, (n-2,n-1). Il lui faut alors, pour déterminer la connexité, effectuer i itérations pour chaque sommet i (l'opération racine nécessite en effet ici i itérations). L'appartenance se fait alors en $O\left(n^{2}\right)$ …

Algorithme d'union équilibrée

Ce dernier algorithme, à peine plus compliqué, utilise comme son nom l'indique une union plus lente, mais le compromis en vaut la peine puisqu'il surpasse de loin les deux algorithmes précédents. Le défaut de l'algorithme précédent était la longueur des chemins à l'intérieur des graphes : le problème est ici résolu en comparant la taille de deux arbres, et en reliant toujours la racine du plus petit à la racine du plus grand. La taille des arbres sera stockée dans un tableau annexe taille de taille n dont tous les éléments ont au départ pour valeur 1. taille[i] correspond à la taille de l'arbre ayant pour racine i. L'implémentation est la suivante :

1 union3(i, j, forêt, taille)
2   r1=racine(i, forêt)                       (*r1=racine de i*)
3   r2=racine(j, forêt)                       (*r2=racine de j*)
4   si r1 != r2                               (*si les racines sont différentes*) 
5      si taille[r1]<taille[r2]               (*si l'arbre de j est plus grand que celui de i*)
6         forêt[r1] :=r2                      (*on fait pointer r1 vers r2*) 
7         taille[r2] :=taille[r2]+taille[r1]  (*et on augmente la taille de l'arbre de racine r2*)
8      sinon
9         forêt[r2] :=r1                      (*on fait pointer r2 vers r1*) 
10        taille[r1] :=taille[r1]+taille[r2]  (*et on augmente la taille de l'arbre de racine r1*)

Reprenons le « pire des cas » de l'union rapide : l'algorithme fait d'abord pointer 1 vers 0 et taille[0] prend la valeur 2. Ensuite pour la paire (1,2), il voit que la racine de 1 est 0, que taille[0]=2 et taille[2]=1 (plus petite), donc 2 va pointer vers 0 et ainsi de suite : on a à la fin un arbre trivial dont tous les sommets pointent vers 0. L'appartenance est dans ce cas aussi rapide que pour l'algorithme d'appartenance rapide!

Pour cet algorithme le pire des cas est celui où les arêtes présentées sont telles que chaque arbre est de taille égale : on montre alors que la complexité est en $O\left(p\cdot \ln {n}\right)$ avec p le nombre de paires et n le nombre de sommets.

La complexité est donc quasi linéaire.

Conclusion

Il existe d'autres algorithmes de connexité utilisant des pointeurs, notamment l'algorithme par union équilibrée et compression de chemin, dont la complexité est légèrement meilleure (voir l'article Union-Find). Cependant, Robert Tarjan a démontré en 1975 qu'aucun algorithme de ce type ne peut avoir une complexité linéaire.

Articles connexes

Portail de l'informatique théorique