UNIVERSITÉ DE MAROUA THE UNIVERSITY OF MAROUA
**** ****
INSTITUT SUPÉRIEUR DU THE HIGHER INSTITUTE OF THE
SAHEL SAHEL
**** ****
DÉPARTEMENT DEPARTMENT OF COMPUTER
INFORMATIQUE ET DES SCIENCE AND
TÉLÉCOMMUNICATIONS TELECOMMUNICATIONS
**** ****
INFORMATIQUE ET TÉLÉCOMMUNICATIONS
UE : Algorithmique et structure de données 2
TPE : Implémentation de l'algorithme pour la recherche de
l'arbre couvrant minimum : Prim et Kruskal
Réaliser par :
Faouzi el Mansour 14A341S
Alger Souleymanou Abdou 14A409S
Soussia Kaini 13Z690S
Mohamadou Aminou 13Z004S
Enseignant :Douwe Hallam vincent
Années académique 2016/2017
Introduction
Un graphe est un ensemble de nœuds qui sont reliés entre eux par des arcs.
Mathématiquement, un graphe est représenté par un couple de deux ensembles G = (X;U) où X est
l’ensemble des nœuds et U l’ensemble des arcs. Un arbre couvrant minimum est un arbre induit par
le graphe dont la somme des coûts des arcs est minimum. Comment trouver l’arbre couvrant
minimum dans un graphe ? Quelles algorithmes utiliser et comment l’implémenter ? Ferons l’objet
de notre analyse.
Pour répondre a ces questions, nous allons commencer par présenter le principe de chaque
algorithmes( Prim et Kruskal) en suite décrire la démarche que nous avons adopter pour résoudre le
problème d’arbre couvrant minimum. Nous allons à présent considérer le problème de trouver non
seulement un sous-arbre couvrant mais un sous-arbre couvrant de poids minimal. L’ on se restreint
au cas de graphes (non orientés) simples. L’algorithme de Prim répond à cette question.
Principe de l’algorithme de Prim :
Soit G = (V, E) un graphe connexe non orienté dont les arêtes sont pondérées par une
fonction p : E→ R+ . L’idée de cet algorithme est de construire le sous-arbre de proche en proche. Si
on dispose déjà d’un sous- graphe G ′ = (V ′ , A) connexe d’un arbre de poids minimal couvrant G,
on lui ajoute une arête de poids minimal parmi les arêtes joignant un sommet de V ′ à un sommet de
V \ V′. Puisqu’il faut couvrir l’arbre tout entier, on débute la procédure avec un sous-graphe
restreint à une quelconque arête de G.
Algorithme de Prim :
1. Prim (G=(V,E))
2. V ← { v } où v est un sommet choisi arbitrairement dans V
3. E ← {}
3. tant que V != V
4. e = (s1 ,s2)← e = (s1 ,s2) ∈ E tel que s1 ∈ V , s2 ∈ V’ et coût ( e ) est minimal
5. ajouter s 2 à V’
6. ajouter e à E‘
7. retourner G’ = (V‘ , E‘)
Soit l’exemple :
Travail Personnel de l’Étudiant : Algorithmique et structures de données 2
La dessus nous avons un graphe donc l’arbre couvrant minimum a été trouver en appliquant
l’’algorithme de Prim. L’algorithme de Prim n’est pas le seul répondant à cette question. On
rencontre aussi l’algorithme de Kruskal.
Principe de l’algorithme de Kruskal :
➢ L’algorithme maintient une forêt d’arbres
➢ À chaque itération, on choisit l’arête de coût minimal
➢ Cette arête est acceptée, si elle relit deux arbres distincts, sinon elle est rejetée (pourrait
former un cycle)
➢ L’algorithme se termine lorsqu’on a un seul arbre
Algorithme de Kruskal :
1. Kruskal (G=(V , E))
2. pour tout sommet v ∈ V
3. C( v ) ← créer un ensemble { v }
4. Q ← créer FilePrioritaire<Arête>(E) où la clé est le poids
5. tant que | E’ | < | V | − 1
6. e = (v1 , v2) ← Q . enleverMinimum ()
7. si C (v1) != C (v2)
8. ajouter e à E’
9. fusionner C ( v1 ) et C ( v2 ) afin que C ( v1) = C ( v2 )
10. retourner G’ = (V , E’)
void kruskal(Graphe G,/Arbre *sortie){
int k=0;
V={};
trier les arêtes par ordre de poids croissant
while (k<n){
Parcourir la liste triée
Sélectionner la première arête, w, qui ne forme pas de cycle
k++;
V=VU{w}
}
*sortie =graphe(S,V);
}
prenons l’exemple ci-dessous :
Travail Personnel de l’Étudiant : Algorithmique et structures de données 2
La aussi, nous obtenons le même arbre couvrant minimum.
Pour l’implémentation de ces deux algorithmes, nous avons utiliser les structures de données
tas et le graphe. Par définition, un tas ou (Heap en anglais) est un arbre binaire presque parfait c’est-
a-dire complet au rang (h-1) si h est la hauteur de l’arbre. Pour ce travail, nous avons utilise comme
langage de programmation le langage C qui est l’un des langages qui nous permet de créer ce genre
de tas a l’aide des structure de données abstraites.
Pour construire notre projet, nous avons crée un makefile pour chaque algorithme. Arriver
au niveau du terminal, il faut taper « make » pour construire le programme exécutant l’algorithme
Prim et en suite taper ./Prim fichier.txt ou le fichier.txt en question contient la représentation du
graphe. Nous avons le même cheminement pour l’algorithme de Kruskal. Pour effacer les
exécutables construites précédemment, il faut taper la commande « make clean ».
Notre makefile :
Prim: main.c tas.c graphe.c
gcc -o Prim main.c tas.c graphe.c
clean:
rm -f Prim
Kruskal: mainKruskal.c tas.c graphe.c
gcc -o kruskal mainKruskal.c tas.c graphe.c
clean:
rm -f Kruskal
Conclusion
En somme, il était question pour nous dans ce travail d’implémenter les deux algorithmes
Prim et Kruskal pour la détermination de l’arbre couvrant minimum, l’on a utiliser des structures de
données adéquates pour résoudre le problème pose plus haut. Il en ressort que les deux algorithmes
produisent les mêmes résultats et sont efficace pour ce genre des recherches.
Travail Personnel de l’Étudiant : Algorithmique et structures de données 2
Bibliographie :
[1] Douwe Hallam Vincent, Algorithmique et structures de données 1.
[2] Douwe Hallam Vincent, Algorithmique et structures de données 2.
[3] Douwe Hallam Vincent, Programmation avance en C.
[4] Éric Beaudry, Graphes / Arbres de recouvrement à coût minimal (ARM).
[5] Michel Rigo, Théorie des graphes .
Travail Personnel de l’Étudiant : Algorithmique et structures de données 2
