Les notes d’implantation de l’algorithme de Kruskal

Cours les notes d’implantation de l’algorithme de Kruskal, tutoriel & guide de travaux pratiques en pdf.

Les notes d’implantation de l’algorithme de Kruskal

L’algorithme de Kruskal ajoute des arcs à l’ASM suivant l’ordre croissant de leur longueur, l’ajout d’un arc ne devant pas induire de cycle. On peut montrer que, dans un graphe sans cycle, l’ajout d’un arc ne conduit pas à la formation de cycle si et seulement si cet arc joint deux composantes connexes différentes. Cette propriété nous fournit un moyen simple de tester si un arc peut être ajouté. Il faut cependant pouvoir déterminer si deux nœuds ou sommets appartiennent à des composantes connexes différentes. Ceci se réalise simplement en utilisant un vecteur Composantes[1..n] ayant la propriété invariante suivante:
Deux nœud  i et j de l’ASM font partie de la même composante connexe si et seulement si:
Composantes[i] = Composantes[j].
Au départ, l’ASM ne possède aucun arc; il contient donc n composantes connexes dégénérées, d’un seul nœud chacune. Nous initialisons alors Composantes de telle sorte que Composantes[i] = i, avec i ∈ {1, 2, …, n}. Puis, lorsqu’un arc est ajouté, il joint deux nœuds ou sommets  s1 et s2 appartenant à des composantes connexes différentes (disons C1 et C2). Il faudra alors joindre les composantes C1 et C2.
Toutes les fois qu’un arc est ajouté, le nombre de composantes connexes diminue de1 . L’exécution de la boucle principale se terminera donc lorsqu’il n’y aura plus qu’une seule composante connexe (un arbre étant un graphe connexe sans cycle).
Le programme 9 .3 constitue une implantation de l’algorithme de Kruskal. Ce programme est écrit en Turbo Pascal qui accepte des identificateurs de longueur supérieure à celle que permet le PASCAL standard.