TP : Recherche d'un arbre couvrant de poids minimum par l'algorithme de Kruskal

INFormatique et
RESeaux

Ecole Nationale Supérieure des Télécommunications

Langage C

Base de
Connaissances
Indispensables

Recherche d'un arbre couvrant de poids minimum par l'algorithme de Kruskal

Définition

Soit un graphe connexe non orienté G=(S,A) où S est l'ensemble des sommets et A l'ensemble des arêtes. Chaque arête possède un poids. Il s'agit de déterminer un arbre couvrant de poids minimum ou autrement dit un graphe partiel (graphe ayant les mêmes sommets mais seulement une partie des arêtes) connexe de poids minimum ; le poids d'un graphe est ici la somme des poids de ses arêtes.

Pour résoudre ce problème, on utilise l'algorithme de Kruskal.

Plus précisément, les sommets sont ici des points dans un plan. Le graphe est le graphe complet. Le poids d'une arête est la distance euclidienne entre ses extrémités.

L'ordre du graphe et les coordonnées des sommets sont lus dans un fichier. On demande à l'utilisateur de donner le nom de ce fichier

Les arêtes de l'arbre couvrant de poids minimum sont sauvegardés dans un fichier dont on demande le nom à l'utilisateur.
Les résultats sont affichés graphiquement à l'écran ; on peut utiliser pour cela la librairie graphique documentée ici ;

Eléments d'analyse

Si l'ordre du graphe s'appelle ordre, les sommets s'appellent 0, 1, 2, ..., ordre - 1.
Les poids sont des "doubles" ; le poids d'une arête est la distance euclidienne entre ses extrémités.

Les définitions de types

Un type structure nommé Coord contient les deux coordonnées d'un sommet (deux champs entiers abs et ord)
Un type structure nommé Arete contient trois champs pour les deux extrémités de l'arête et son poids(extr1 et extr2 de type int, poids de type double).

Les variables globales

l'ordre du graphe, nommé ordre,
la taille du graphe, nommée taille, celle-ci pourra être calculée dès que l'ordre est connu puisqu'on traite ici un graphe complet ;
un tableau de Coord, nommé coordonnee, qui mémorisera les coordonnées de l'ensemble des sommets ; coordonnee[i] contiendra ainsi les coordonnées du sommet i ; ce tableau sera alloué dynamiquement ;
un tableau nommé graphe qui mémorisera l'ensemble des arêtes ; c'est ce tableau qui est trié par poids croissants avant d'effectuer l'algorithme proprement dit ; ce tableau sera alloué dynamiquement.

Les fonctions

Une fonction de saisie du graphe
Une fonction qui trie les arêtes par poids croissants ; on pourra pour cela utiliser un tri par insertion.
Une fonction qui réalise l'algorithme de Kruskal proprement dit et retourne un tableau contenant les arêtes d'un arbre couvrant de poids minimum.
Une fonction qui effectue l'affichage graphique des sommets du graphe et de l'arbre couvrant de poids minimum.
Une fonction qui affiche la liste des arêtes d'un arbre couvrant de poids minimum.

Fichiers de tests

Vous disposez des fichierss de test :

"kruskal.don"

"kruskal2.don"

Vous pouvez fabriquer d'autres fichiers de tests.

Algorithme de Kruskal

L'algorithme de Kruskal traite du problème de l'arbre couvrant de poids minimum.
On commence par trier les arêtes par poids croissants.
On construit au fur et à mesure l'arbre de poids minimum en partant d'un ensemble vide d'arêtes. On numérote les sommets pour que, au fur et à mesure de l'algorithme, deux sommets aient même numéro si et seulement s'ils appartiennent à une même composante connexe de l'arbre en construction. Pour cela, on attribue au départ le numéro i au sommet i. On ajoute à l'arbre les arêtes en suivant le tableau trié mais en "sautant" les arêtes dont les extrémités ont même numéro (qui appartiennent donc à une même composante connnexe). Lorsqu'on ajoute une arête, on note num1 et num2 les numéros de ses extrémités : tout sommet ayant comme numéro num2 voit changer son numéro en num1.

Exemple correspondant au fichier kruskal.don.

Les arêtes sont celles d'un arbre couvrant de poids minimum.

Corrigé

On peut quelquefois disposer de ce corrigé