home	accès étudiants

Arbre couvrant de poids minimum

Exercice 1

Déterminer un arbre couvrant de poids minimum du graphe suivant

à l'aide de l'algorithme de Kruskal ;
à l'aide de l'algorithme de Prim.

Exercice 2

Implémenter l'algorithme de Prim en C, C++ ou Java. Le programme doit lire le graphe à partir d'un fichier en format

n m
u₁ v₁ c₁
...
u_m v_m c_m

et produire un fichier en format

x₁ y₁
...
x_n-1 y_n-1
c

où

n est le nombre de sommets du graphe ;
m est le nombre d'arêtes du graphe ;
(u_j,v_j), j=1,...,m sont les arêtes du graphe ;
c_j est le coût de l'arête (u_j,v_j) ;
(x_k,y_k), k=1,...,n-1 sont les arêtes de l'arbre couvrant ;
c est le coût total de l'arbre couvrant.

Avant de commencer, réfléchir bien sur la représentation du graphe et les structures de données / les classes appropriées.

Que se passe-t-il si le graphe n'est pas connexe ? Faire les modifications nécessaires pour trouver la forêt couvrante dans ce cas.

Éléments de correction

Il n'y a pas de représentation « universelle » de graphes. La représentation qu'on va utiliser dépend des besoins de notre application. Ici nous proposons une implémentation simple qui est loin d'être complète, mais qui est bien adaptée aux algorithmes de Prim et de Kruskal.

Il n'y a pas de classe pour représenter les sommets. Ils sont représentés tout simplement par leurs numéros, entiers entre 0 et n - 1.
La classe Arete représente les arêtes du graphe. C'est une classe simple contenant une paire de sommets et le coût de l'arête.
La classe Graphe représente les graphes. Elle contient la matrice d'adjacence du graphe (adj[i][j] = true ssi (i,j) est une arête) et une matrice dist dans laquelle on stocke les longueurs des arêtes (les distances entre les sommets). Cette classe a quelques méthodes de base permettant d'accéder aux données.
La classe AlgoKruskal est un exemple d'utilisation des classes Graphe et Arete. Elle implemente l'algorithme de Kruskal. Le fichier ex.dat décrit le graphe d'exercice 1, mais les sommets sont numérotés de 0 à n - 1.