Les algorithmes d’UNION-FIND

Table des matières

INTRODUCTION GÉNÉRALE
CHAPITRE 1: ARBRE COUVRANT MINIMAL 
1.1 Introduction
1.2 Graphes, Arbres et arbres couvrants
1.3 Propriétés d’un arbre couvrant minimal
1.4 Algorithmes d’UNION-FIND
1.4.1 Méthode 1 : Tableau de correspondance entre un sommet et son groupe
1.4.2 Méthode 2 : Compression par chemin
1.5 Algorithme de Borûvka
1.5.1 Exemple
1.6 Algorithme de Kruskal
1.7 Algorithme de Prim
1.8 Exemple étape par étape
1.9 Algorithme de Prim avec une matrice de distance
1.10 Liste d’adjacence
CHAPITRE 2: LES FILES DE PRIORITÉ 
2.1 Introduction
2.2 Liste chaînée
2.3 Lestas
2.3.1 Comparaison des opérations de base sur différents tas
2.3.2 Le tas binaire
2.3.3 Opération d’insertion
2.3.4 Suppression du minimum
2.3.5 Opération decreasekey
2.3.6 Opération delete
2.3.7 Construire le tas en temps linéaire
2.3.8 Exemple de construction d’un tas
2.3.9 Preuve de la borne
2.4 Le tas binomial
2.4.1 Structure du nœud binomial
2.4.2 Trouver le minimum
2.4.3 Union de deux tas binomiaux
2.4.4 Union de deux arbres de degré k
2.4.5 Union rapide
2.4.6 Opération d’UNION
2.4.7 Opération DecreaseKey
2.4.8 Suppression du minimum
2.5 Tas de Fibonacci
2.5.1 Opération de l’Union
2.5.2 Opération d’insertion
2.5.3 Extraction du minimum
2.5.4 Opération decreaseKey
CHAPITRE 3: COMPARAISON EMPIRIQUE DES PERFORMANCES 
3.1 Introduction
3.2 Les programmes testés
3.3 Mesures du temps
3.4 Note sur l’algorithme de Borûvka et de Kruskal
3.5 Résultats empiriques
3.5.1 Graphes creux
3.5.2 Graphes moyennement denses
3.5.3 Graphes denses
3.6 Consommation mémoire
3.7 Algorithmes de Union-Find pour Kruskal
3.7.1 UNION-FIND sur les graphes creux
3.7.2 UNION-FIND sur les graphes moyennement denses
3.7.3 UNION-FIND sur les graphes denses
3.8 Discussion sur les résultat