Algorithmes de connexité basés sur des pointeurs
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

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 (Un arbre est une plante terrestre capable de se développer par elle-même en hauteur, en général au delà de sept mètres. Les arbres acquièrent une structure rigide composée d'un tronc qui peut...) 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 (La largeur d’un objet représente sa dimension perpendiculaire à sa longueur, soit la mesure la plus étroite de sa face. En géométrie plane, la largeur est la plus petite des deux mesures d'un rectangle,...) et l'algorithme de parcours en profondeur s'il s'agit seulement de savoir si un graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) est connexe.

Notations

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} ]\!]n est le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) de sommets du graphe. Le graphe sera présenté sous forme de liste de paires, chaque paire (On dit qu'un ensemble E est une paire lorsqu'il est formé de deux éléments distincts a et b, et il s'écrit alors :) correspondant à une arête. Les implémentations seront écrites en langage générique.

Principe général

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 (Tableau peut avoir plusieurs sens suivant le contexte employé :) 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 recherche scientifique désigne en premier lieu l’ensemble des actions entreprises en vue de produire et de développer les connaissances...) 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 (Dans les technologies de l'information, une donnée est une description élémentaire, souvent codée, d'une chose, d'une transaction, d'un événement, etc.), 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 (Le mot phase peut avoir plusieurs significations, il employé dans plusieurs domaines et principalement en physique :) 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 (On distingue :) 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 (Le temps est un concept développé par l'être humain pour appréhender le changement dans le monde.) 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 r1 de i et r2 de j, puis on donne à tous les éléments qui avaient pour racine r1 une nouvelle racine: r2. 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 (La Lente est une rivière de la Toscane.) 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(n2), 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 (La longueur d’un objet est la distance entre ses deux extrémités les plus éloignées. Lorsque l’objet est filiforme ou en forme de lacet, sa longueur est celle de l’objet complètement...) 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 (Le mot implantation peut avoir plusieurs significations :) 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é (La complexité est une notion utilisée en philosophie, épistémologie (par exemple par Anthony Wilden ou Edgar Morin), en physique, en biologie (par exemple par Henri Atlan), en...) 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 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.

À voir également

  • Union-Find
  • Algorithme de Warshall.
Page générée en 0.101 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique