Algorithmes de connexité basés sur des pointeurs

Les algorithmes de connexité suivants 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 en fait à une composante connexe du graphe : ainsi deux sommets seront reliés par un chemin si et seulement si ils appartiennent au même arbre. Cela se vérifie en comparant les racines des arbres respectifs.

On notera que, si ces algorithmes sont efficaces pour savoir si deux sommets sont reliés, ils sont en revanche beaucoup plus lourds que l'algorithme de parcours en largeur et l'algorithme de parcours en profondeur s'il s'agit seulement de savoir si un graphe est connexe.

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

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

Les trois algorithmes que nous allons vous présenter reposent sur la création et le regroupement d'arbres à partir du graphe proposé, puis sur le test de la connexité en vérifiant que tous les sommets appartiennent finalement au même arbre.

On crée donc un tableau forêt de n éléments correspondant à chaque sommet. Le contenu de chaque 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*)

Deux sommets seront ainsi 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.

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é
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*)
8 finpour

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 à peu près proportionnel au nombre de sommets, on a au final un algorithme en O(n), ce qui est peu satisfaisant. Nous allons maintenant nous intéresser à son symétrique : l'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)$...

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]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(lien) prend la valeur 2. Ensuite pour la paire (1,2), il voit que la racine de 1 est 0, que taille(lien)=2 et taille(lien)=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.

Il existe d'autres algorithmes de connexité utilisant des pointeurs, notamment l'algorithme par compression de chemin. Cependant, ils ne sont pas aussi simples que l'union équilibrée sans pour autant être plus rapides. Ainsi, la recherche d'une solution fondée sur des pointeurs de complexité linéaire a été un sujet de recherche avant que Robert Tarjan ne démontre l’impossibilité d’une telle solution en 1975.

• Union-Find
• Algorithme de Warshall.