I. Introduction et définitions de base

I-A. Algorithme

Un algorithme est une suite finie et non ambiguë d'opérations visant la résolution d'un problème. On le formule généralement comme la transformation d'un ensemble de valeurs d'entrée en un ensemble de valeurs de sortie.

Un algorithme est dit totalement correct lorsque, pour chaque instance d'un problème, il se termine en produisant la bonne sortie. Il sera dit partiellement correct si, quand il se termine, il donne la bonne sortie, sans assurer qu'il se termine. Il sera approximatif s'il ne donne qu'une approximation de la solution (comme les algorithmes numériques).

Pour tout algorithme, on se pose finalement trois questions : sa correction, sa vitesse d'exécution et la possibilité de faire mieux.

I-B. Structure de données

Une structure de données est une méthode de stockage et d'organisation des données pour en faciliter l'accès et la modification. Elle regroupe des données à gérer et un ensemble d'opérations qu'on peut leur appliquer. En général, il existe plusieurs manières de représenter ces données et plusieurs implémentations de leur manipulation.

L'interface sera définie dans un type de données abstrait (TDA). Il spécifie précisément la nature et les propriétés des données à stocker et les modalités des opérations.

I-C. Récursivité

Un algorithme est dit récursif s'il s'invoque lui-même (directement ou non – récursif multiple). Cela permet de simplifier l'expression de certains algorithmes.

Une procédure sera récursive terminale si elle n'effectue plus aucune opération après s'être invoquée récursivement.

II. Outils d'analyse des algorithmes

II-A. Analyse de la correction

La correction d'un algorithme s'étudie par rapport à un problème donné. Un algorithme sera correct pour une instance d'un problème s'il produit une solution correcte pour cette instance. Il sera correct pour un problème s'il est correct pour toute instance de ce problème.

II-A-1. Types d'analyse

On peut vérifier cette correction de manière empirique, en testant concrètement l'algorithme (il faut alors l'implémenter et trouver suffisamment d'instances du problème), ou de manière formelle, mathématique. On se focalisera sur cette deuxième approche.

II-A-2. Analyse formelle

Une assertion est une relation entre les variables qui est vraie à un moment dans l'exécution. Notamment, on compte les pré- et postconditions (conditions que doivent remplir les données d'entrée et de sortie) Image non disponible et Image non disponible.

Ainsi, un code sera correct si le triplet de Hoare Image non disponible est vrai. Pour vérifier cette propriété, on insère des assertions Image non disponible décrivant l'état des variables à chaque étape du programme et on vérifiera que cette suite de triplet est correcte :

Image non disponible
Image non disponible
Image non disponible
Image non disponible

Pour les boucles, on mettra en évidence une assertion particulière, Image non disponible , l'invariant de boucle, qui décrit l'état du programme pendant l'exécution. Cet invariant est vrai après l'initialisation de la boucle, après chaque itération (Image non disponible est vrai) et à la sortie de la boucle (Image non disponible est vrai). En général, l'algorithme découle de l'invariant, de l'idée de base à la conception.

II-A-3. Terminaison des boucles

Une fois qu'on a prouvé que la boucle était correcte, il faut s'assurer qu'elle se termine. On cherchera donc une fonction de terminaison Image non disponible :

  • définie sur base des variables de l'algorithme ;
  • à valeur naturelle ;
  • décroissante suite à l'exécution du corps de la boucle ;
  • à valeur positive tant que le gardien de la boucle est vrai.

Ainsi, quand Image non disponible atteindra zéro, on aura infirmé le gardien et la boucle sera terminée.

II-A-4. Preuve par induction et algorithmes récursifs

La preuve par induction se passe en deux étapes :

  • cas de base : on montre explicitement que la propriété est vraie pour une série d'instances ;
  • cas inductif : on suppose que la propriété est vraie pour les instances précédentes du problème et on montre qu'elle l'est aussi pour l'instance suivante.

Cette manière de procéder est correcte, car le corps des naturels Image non disponible est bien ordonné par la relation Image non disponible (dans tout sous-ensemble de Image non disponible, il y a un plus petit élément).

II-B. Analyse de la complexité en temps

On peut la mesurer de manière expérimentale en implémentant l'algorithme et en le lançant sur des instances du problème. Cependant, les temps de calcul vont largement dépendre de l'implémentation, de la machine, du compilateur, des données, etc.

On préférera donc une manière plus théorique de procéder, sur base d'un modèle de calcul abstrait, la RAM (Random Access Machine). Les types de base sont limités aux entiers et nombres flottants avec une taille maximale. Une série d'opérations de base est définie ; chacune prend un temps constant et une série d'instructions est toujours exécutée de manière sérielle.

On distingue plusieurs types de calcul de complexité : le cas le plus défavorable (on considère le temps maximal pour toute instance d'une certaine taille), le plus favorable (on considère le temps minimal pour toute instance d'une certaine taille) et moyen (on considère le temps pour toute instance d'une certaine taille pondéré par la probabilité de cette instance).

II-C. Analyse asymptotique

On se contentera d'une analyse asymptotique, en considérant des instances très grandes. Cela simplifiera les calculs : on ne garde que le terme dominant en en ignorant le coefficient. En effet, même en augmentant considérablement la puissance de calcul, cela ne fera pas varier de manière significative le temps d'exécution de l'algorithme.

On utilisera trois notations :

  • Image non disponible, on définit une borne supérieure asymptotique à la fonction ;
  • Image non disponible, on définit une borne inférieure asymptotique à la fonction ;
  • Image non disponible, on définit une borne serrée asymptotique à la fonction.

II-D. Analyse asymptotique serrée

On peut utiliser une analyse asymptotique plus précise que les notations introduites précédemment : par exemple, Image non disponible, alors que, asymptotiquement, la différence entre les deux fonctions est énorme. Avec la notation Image non disponible, seules quelques constantes Image non disponible peuvent convenir pour satisfaire Image non disponible. En notation Image non disponible, cette relation est valable pour toute constante Image non disponible.

On introduit donc les notations suivantes.

  • Image non disponible ; notamment, cela implique que Image non disponible.
  • Image non disponible ; notamment, cela implique que Image non disponible.

III. Algorithmes de tri

III-A. Types de tri

On peut assigner une série d'adjectifs aux algorithmes de tri en fonction de leurs caractéristiques :

  • interne : en mémoire centrale, par opposition à externe (où les données ne sont pas accessibles aussi rapidement) ;
  • de tableau : qui trie une structure de données offrant un accès constant à ses éléments ;
  • générique : qui peut trier n'importe quel type d'objets comparables, sans hypothèse sur leur valeur ;
  • comparatif : basé sur la comparaison des clés des éléments ;
  • itératif : basé sur un ou plusieurs parcours itératifs du tableau, par opposition à récursif ;
  • en place : qui modifie directement la structure en cours de tri sans la dupliquer ;
  • stable : qui conserve l'ordre relatif des éléments égaux.

III-B. Tri par insertion

L'invariant : on considère la partie A[1..j-1] du tableau triée. À chaque itération, on va insérer la clé A[j] à sa bonne place en décalant d'un rang vers la droite tous les éléments plus grands que cette clé. Une fois qu'on trouve un élément égal ou plus petit, on l'insère juste après.

Cet algorithme a une complexité Image non disponible dans les pire et moyen cas ; dans le meilleur, il suffit de comparer tous les éléments et la complexité est de Image non disponible.

Tri par insertion : InsertionSort(A)
Sélectionnez
for j = 2 to A:length
	key = A[j]
	// Insert A[j] into the sorted sequence A[1..j-1].
	i = j - 1
	while i > 0 and A[i] > key
		A[i + 1] = A[i]
		i = i - 1
	A[i + 1] = key

III-C. Tri par fusion

On sépare le tableau en deux sous-tableaux de même taille, que l'on trie récursivement ; ensuite, on fusionne les deux sous-tableaux en gardant l'ordre (application du principe de diviser pour régner). Le cas de base correspond au tri d'un seul élément, qui ne nécessite aucune opération.

Pour la fusion des tableaux, on prend trois paramètres tels que Image non disponible, en sachant que les deux sous-tableaux à fusionner (A[p..q] et A[q+1..r]) sont déjà triés.

Tri par fusion : MergeSort(A, p, r)
Sélectionnez
if p < r
	q = round down (p+r)/2
	MergeSort(A, p, q)
	MergeSort(A, q + 1, r)
	Merge(A, p, q, r)
Fusion de tableaux : Merge(A, p, q, r)
Sélectionnez

n1 = q - p + 1
n2 = r - q
Let L[1..n1 + 1] and R[1..n2 + 1] be two new arrays
for i = 1 to n1
	L[i] = A[p + i - 1]
for j = 1 to n2
	R[j] = A[q + j]

L[n1 + 1] = 1
R[n2 + 1] = 1

i = 1
j = 1
for k = p to r
	if L[i] <= R[j]
		A[k] = L[i]
		i = i + 1
	else
		A[k] = R[j]
		j = j + 1

III-D. Tri rapide

Il s'agit d'un tri en place et non stable appliquant le principe du diviser pour régner. Sa complexité est Image non disponible dans le pire cas, bien que le cas moyen soit de la complexité optimale Image non disponible, le pire cas étant rare.

Le principe : pour trier un certain tableau A[p..r], on choisit un pivot (généralement le dernier élément, A[r]). Ensuite, on partitionne le tableau de telle sorte que tout élément de A[p..q-1] soit inférieur ou égal au pivot, déplacé en A[q], ainsi qu'à tout élément de A[q+1..r]. On applique ensuite récursivement l'algorithme sur chacun des deux demi-tableaux. Pour partitionner, on parcourt le tableau de gauche à droite ; on initialise la position future du pivot q à p, le début du sous-tableau à trier ; si l'élément courant est plus petit que le pivot, on le met à la position q et on incrémente q. Au final, on échange le dernier élément traité avec celui à la position q.

On peut en imaginer une série de variantes, notamment sur le choix du pivot : un élément au hasard, la médiane de trois éléments, etc. Cela diminue la chance de tomber dans le pire cas sans modifier la complexité tant que le choix s'effectue en temps constant.

On peut aussi remarquer que l'algorithme est lourd pour de petits tableaux (une vingtaine d'éléments), pour lesquels on pourra privilégier un algorithme plus naïf (par insertion, par exemple).

Tri rapide : QuickSort(A, begin, end)
Sélectionnez
if begin < end
	q = Partition(A, begin, end)
	QuickSort(A, begin, q - 1)
	QuickSort(A, q + 1, end)
Partition : Partition(A, p, r)
Sélectionnez
x = A[r]
i = p - 1
for j = p to r - 1
	if A[j] <= x
		i = i + 1
		swap(A[i];A[j])
swap(A[i + 1], A[r])
return i + 1

III-E. Tri par tas

III-E-1. Arbre

Un arbre est un graphe dirigé constitué d'un ensemble de nœuds reliés par des arcs. Ce graphe est connexe et acyclique. S'il est non vide, alors il possède un nœud distingué et unique, la racine. Un chemin est une séquence de nœuds dont toute paire consécutive est un arc de l'arbre. La hauteur d'un arbre est la distance entre la feuille la plus éloignée et la racine.

Un arbre ordonné est un arbre dans lequel l'ensemble des fils de chacun de ses nœuds est ordonné.

Un arbre est dit binaire si chacun de ses nœuds possède au plus deux fils (un gauche et un droit, le gauche précédent le droit).

Un arbre est dit parfait ou complet si toutes ses feuilles sont à la même distance de la racine.

Un arbre binaire entier ou propre (full ou proper) est un arbre binaire dans lequel tous les nœuds internes possèdent exactement deux fils. Pour ces arbres, on dispose de quelques propriétés :

  • le nombre de nœuds externes est égal au nombre de nœuds internes plus une unité ;
  • le nombre de nœuds internes est égal à Image non disponible, où Image non disponible est le nombre de nœuds ;
  • le nombre de nœuds à la profondeur (niveau) Image non disponible est inférieur ou égal à Image non disponible ;
  • la hauteur de l'arbre est inférieure ou égale au nombre de ses nœuds internes.

On peut lier la hauteur Image non disponible et le nombre de nœuds Image non disponible pour un arbre binaire entier par

Image non disponible
Image non disponible

De manière équivalente,

Image non disponible
Image non disponible

III-E-2. Tas

Un arbre binaire complet (aussi dit tas) est un arbre binaire tel que, notant Image non disponible la hauteur de l'arbre :

  • pour tout Image non disponible, il y a exactement Image non disponible nœuds à la profondeur Image non disponible ;
  • une feuille a une profondeur Image non disponible ou Image non disponible ;
  • les feuilles de profondeur maximale sont tassées sur la gauche.

Un tas binaire est un arbre binaire complet tel que :

  • à chaque nœud est associée une clé ;
  • la clé de chaque nœud est supérieure ou égale à celle de ses fils (la propriété d'ordre du tas).

Un tas (un arbre binaire complet Image non disponible de Image non disponible entrées et de hauteur Image non disponible) dispose des propriétés suivantes :

  • Image non disponible est supérieur ou égal à la taille de l'arbre complet de hauteur Image non disponible plus une unité, soit Image non disponible ;
  • Image non disponible est inférieur ou égal à la taille de l'arbre complet de hauteur Image non disponible, soit Image non disponible.

On peut également écrire

Image non disponible
Image non disponible

III-E-3. Interface

Pour un tas Image non disponible, on définit les opérations suivantes :

  • Image non disponible : le nombre de clés de Image non disponible ;
  • Image non disponible : construire un tas à partir du tableau Image non disponible ;
  • Image non disponible : insérer la valeur Image non disponible dans le tas Image non disponible ;
  • Image non disponible : récupérer la clé maximale.

III-E-4. Implémentation par un tableau

On peut représenter un tas de manière compacte par un tableau A : la racine de l'arbre est le premier élément, on peut accéder relativement aux autres éléments par ces quelques fonctions (elles renvoient l'indice à consulter).

  • Image non disponible ;
  • Image non disponible ;
  • Image non disponible.

La propriété d'ordre du tas impose ainsi Image non disponible.

On peut alors implémenter les quelques méthodes du tas.

Image non disponible considère que les deux sous-arbres du nœud Image non disponible sont des tas et réarrange l'arbre pour qu'il soit un tas (il fait descendre l'élément Image non disponible jusqu'à ce que l'arbre respecte la propriété d'ordre). Ensuite, on appelle récursivement l'algorithme du côté de l'élément qui a été déplacé (le cas échéant). Vu le lien entre la hauteur de l'arbre et le nombre de nœuds, on a une complexité de Image non disponible.

Restauration de la propriété de tas maximal : MaxHeapify(A, i)
Sélectionnez
l = Left(i)
r = Right(i)

if l <= A.heapSize and A[l] > A[i]
	largest = l
else
	largest = i

if r <= A.heapSize and A[r] > A[largest]
	largest = r

if largest 6= i
	swap(A[i];A[largest])
	MaxHeapify(A; largest)

Image non disponible construit un tas à partir d'un tableau : à partir du premier nœud qui a un successeur (gauche, s'il n'y en a qu'un), on réorganise le tas et on remonte jusqu'à la racine. On effectue Image non disponible appels à Image non disponible, d'où une complexité de Image non disponible ; une analyse plus fine sur un arbre binaire parfait atteint Image non disponible.

Construction d'un tas maximal à partir d'un tableau : BuildMaxHeap(A)
Sélectionnez
A.heapSize = A.length
for i = (round down A.length/2) downto 1
	MaxHeapify(A, largest)

Pour l'insertion dans un tas, on insère l'élément à la fin (soit avec une clé infiniment négative), puis on le déplace jusqu'à la clé voulue.

Insertion : HeapInsert(A, key)
Sélectionnez
A.heapSize = A.heapSize + 1
A[A.heapSize] = - infinity
HeapIncreaseKey(A, A.heapSize, key)
Augmentation de la clé : HeapIncreaseKey(A, i, key)
Sélectionnez
if key < A[i]
	error new key is smaller than current key
A[i] = key
while i > 1 and A[Parent(i)] < A[i]
	swap(A[i], A[Parent(i)])
	i = Parent(i)

On peut également récupérer le maximum et l'éliminer du tas assez facilement (Image non disponible et Image non disponible, respectivement : lecture et réorganisation).

Récupération du maximum : HeapMaximum(A)
Sélectionnez
return A[1]
Extraction du maximum : HeapExtractMax(A)
Sélectionnez
if A:heapSize < 1
	error \heap under
max = A[1]
A[1] = A[A.heapSize]
A:heapSize = A.heapSize - 1
MaxHeapify(A, 1) // rebuild the heap
return max

III-E-5. Tri par tas

À partir d'un tas, on récupère la racine, l'élément le plus élevé de tout le tas, on la remplace par le dernier élément. On place cette racine à la fin du tableau et on ne considère plus cette case comme partie du tas. On réordonne donc le reste du tableau comme un tas puis on recommence. Tout comme la construction d'un tas, cet algorithme a une complexité de Image non disponible.

Tri par tas : HeapSort(A)
Sélectionnez

BuildMaxHeap(A)
for i = A.length downto 2
	swap(A[i], A[1])
	A.heapSize = A.heapSize - 1
	MaxHeapify(A, 1)

III-F. Résumé

Algorithme Complexité au pire cas Complexité moyenne Complexité au meilleur cas Tri en place ?
Tri par insertion Image non disponible Image non disponible Image non disponible oui
Tri par sélection Image non disponible Image non disponible Image non disponible oui
Tri à bulles Image non disponible Image non disponible Image non disponible oui
Tri par fusion Image non disponible Image non disponible Image non disponible non
Tri rapide Image non disponible Image non disponible Image non disponible oui
Tri par tas Image non disponible Image non disponible Image non disponible oui

IV. Structures de données élémentaires

Une structure de données est une manière d'organiser et de stocker l'information pour en faciliter certaines opérations comme l'accès. Elle dispose d'une interface, un ensemble de procédures d'ajout, retrait, réorganisation, etc. des données. Elle conserve des données et des métadonnées (utilisées pour améliorer l'efficacité du traitement).

Un type de données abstrait est une définition des propriétés et de l'interface de la structure. Il admet généralement plusieurs implémentations, qui feront varier la complexité des opérations.

On distingue généralement deux types d'opérations : l'accès (en ce compris la recherche : minimum, élément suivant, etc.) et la modification (ajout, suppression, etc.).

IV-A. Pile

En anglais, stack.

Une pile est un ensemble dynamique d'objets accessibles selon une discipline LIFO. Son interface est constituée de :

  • Image non disponible : renvoie vrai si et seulement si la pile Image non disponible est vide ;
  • Image non disponible : pousse la valeur Image non disponible sur la pile Image non disponible ;
  • Image non disponible : extrait et renvoie la valeur au sommet de la pile Image non disponible.

On l'implémente généralement :

  • avec un tableau (bien que sa taille soit, a priori, de taille fixée). Complexité en temps des procédures : Image non disponible ; en espace : Image non disponible. Cela signifie que la pile ne pourra pas grandir ; ici, ce n'est pas un avantage ;
  • avec une liste liée. Complexité en temps des procédures : Image non disponible ; en espace : Image non disponible.

IV-B. File

En anglais, queue.

Une file est un ensemble dynamique d'objets accessibles selon une discipline FIFO. Son interface est constituée de :

  • Image non disponible : ajoute l'élément Image non disponible à la file Image non disponible ;
  • Image non disponible : retire l'élément à la tête de la file Image non disponible.

On l'implémente généralement avec :

  • un tableau circulaire. Complexité en temps des procédures : Image non disponible ; en espace : Image non disponible ;
  • une liste liée. Complexité en temps des procédures : Image non disponible ; en espace : Image non disponible.

IV-C. File double

En anglais, double-ended queue ou deque.

Une file double est une collection ordonnée d'objets offrant la possibilité d'insérer ou d'extraire un élément à la tête ou à la queue. Il s'agit d'une généralisation des piles et files. Son interface est constituée de :

  • Image non disponible : ajoute l'élément Image non disponible au début de la file double Image non disponible ;
  • Image non disponible : ajoute l'élément Image non disponible à la fin de la file double Image non disponible ;
  • Image non disponible : extrait l'élément situé au début de la file double Image non disponible ;
  • Image non disponible : extrait l'élément situé à la fin de la file double Image non disponible.

On l'implémente généralement avec une liste liée. Complexité en temps des procédures : Image non disponible ; en espace : Image non disponible.

IV-D. Liste

Une liste est un ensemble dynamique d'objets ordonnés accessibles relativement les uns aux autres, sur base de leur position. Il s'agit d'une généralisation des piles, files et files doubles. Son interface est constituée de :

  • Image non disponible : ajoute l'élément Image non disponible au début de la liste Image non disponible ;
  • Image non disponible : ajoute l'élément Image non disponible à la fin de la liste Image non disponible ;
  • Image non disponible : ajoute l'élément Image non disponible après Image non disponible dans la liste Image non disponible ;
  • Image non disponible : ajoute l'élément Image non disponible avant Image non disponible dans la liste Image non disponible ;
  • Image non disponible : extrait l'élément situé au début de la liste Image non disponible ;
  • Image non disponible : extrait l'élément situé à la fin de la liste Image non disponible ;
  • Image non disponible : extrait l'élément situé à la position Image non disponible de la liste Image non disponible.

On l'implémente d'une manière similaire à la file double à l'aide d'une liste doublement liée et des sentinelles. Complexité en temps des procédures : Image non disponible ; en espace : Image non disponible.

IV-E. Vecteur

Un vecteur est un ensemble dynamique d'objets occupant des rangs entiers successifs permettant la consultation, le remplacement, l'insertion et la suppression d'éléments à des rangs arbitraires. Son interface est constituée de :

  • Image non disponible : retourne l'élément situé au rang Image non disponible dans le vecteur Image non disponible ;
  • Image non disponible : remplace l'élément situé au rang Image non disponible dans le vecteur Image non disponible par Image non disponible et retourne l'élément remplacé ;
  • Image non disponible : insère l'élément Image non disponible au rang Image non disponible dans le vecteur Image non disponible ;
  • Image non disponible : extrait l'élément situé au rang Image non disponible du vecteur Image non disponible, en diminuant le rang des objets suivants ;
  • Image non disponible : renvoie la taille du vecteur.

On peut l'implémenter à l'aide d'une liste liée ou d'un tableau extensible (généralement préféré pour des temps d'accès constants ; lors de la réallocation du tableau, il faudra veiller à doubler la taille pour amortir ce coût).

IV-F. File à priorité

Une file à priorité est un ensemble dynamique d'objets classés par ordre de priorité, permettant d'extraire un objet ayant la plus grande priorité. Cela suppose un ordre total défini sur les clés. Son interface est constituée de :

  • Image non disponible : insérer l'élément Image non disponible dans la file Image non disponible ;
  • Image non disponible : récupérer l'élément de Image non disponible ayant la plus grande clé ;
  • Image non disponible : supprimer et renvoyer l'élément de Image non disponible ayant la plus grande clé.

On peut l'implémenter à l'aide d'un tableau classique (insertion en Image non disponible, vu qu'il faut garder le tableau trié ; extraction en Image non disponible ; complexité en espace : Image non disponible), d'une liste liée (mêmes complexités en temps ; en espace : Image non disponible) ou d'un tas (renvoi du premier élément en Image non disponible, il s'agit de récupérer l'élément maximal ; extraction du premier élément en Image non disponible, vu qu'il faut restaurer la propriété de tas ; changement de clé d'un élément en Image non disponible ; insertion en Image non disponible ; complexité en espace : Image non disponible).

V. Dictionnaires

V-A. Type de données abstrait

Un dictionnaire est un ensemble dynamique d'objets possédant des clés comparables, on supposera un ordre total sur ces clés. L'objectif est de minimiser le coût pour l'insertion et l'accès ainsi que pour le stockage. Son interface est constituée de :

  • Image non disponible : retourne un pointeur Image non disponible vers un élément de Image non disponible tel que Image non disponible ou Image non disponible s'il n'y a pas de tel objet ;
  • Image non disponible : ajoute l'élément Image non disponible dans le dictionnaire Image non disponible ;
  • Image non disponible : retire l'élément Image non disponible du dictionnaire Image non disponible.

V-A-1. Implémentations naïves

V-A-1-a. Liste liée

On stocke les paires clé-valeur dans une liste liée. Les complexités seront linéaires pour l'insertion, la recherche et la suppression : à chaque fois, il faut parcourir la liste pour trouver si un élément correspond (pour insertion juste après, renvoi ou suppression).

V-A-1-b. Vecteur trié

Si on a un ordre total sur les clés, on peut stocker les données dans un vecteur maintenu trié. Insertion et suppression requièrent une recherche et un décalage de tous les éléments, leur complexité reste linéaire. La recherche peut être optimisée avec une recherche dichotomique (Image non disponible).

V-B. Arbre

Les arbres binaires de recherches permettront d'implémenter une insertion et une recherche efficaces dans un dictionnaire (logarithmique dans le cas moyen, mais toujours linéaire dans le pire cas tant qu'on n'équilibre pas).

V-B-1. Type de données abstrait

Un arbre est constitué de nœuds, accessibles les uns par rapport aux autres selon leur position ; les données sont associées à ces nœuds. Son interface est constituée de :

  • Image non disponible : renvoie le parent de l'élément Image non disponible dans l'arbre Image non disponible, sauf si Image non disponible est la racine ;
  • Image non disponible : renvoie une structure de données des fils de l'élément Image non disponible dans l'arbre Image non disponible ;
  • Image non disponible : renvoie le fils gauche de l'élément Image non disponible dans l'arbre binaire Image non disponible ;
  • Image non disponible : renvoie le fils droit de l'élément Image non disponible dans l'arbre binaire Image non disponible ;
  • Image non disponible : renvoie la racine de l'arbre Image non disponible ;
  • Image non disponible : renvoie vrai si de l'élément Image non disponible est la racine de l'arbre Image non disponible ;
  • Image non disponible : renvoie vrai si de l'élément Image non disponible est un nœud interne de l'arbre Image non disponible ;
  • Image non disponible : renvoie vrai si de l'élément Image non disponible est un nœud externe de l'arbre Image non disponible ;
  • Image non disponible : renvoie les données associées à l'élément Image non disponible dans l'arbre Image non disponible ;
  • Image non disponible : renvoie le nombre de nœuds de l'arbre Image non disponible.

V-B-2. Implémentation d'un arbre binaire

V-B-2-a. Vecteur

Tout l'arbre est représenté par un vecteur, où chaque position est indiquée par l'index : la racine est à la position Image non disponible, le successeur gauche d'un nœud de rang Image non disponible sera à l'index Image non disponible, le successeur droit au rang Image non disponible.

Cependant, si l'arbre binaire n'est pas complet, on aura des trous : la complexité en espace pour le stockage de Image non disponible nœuds sera de Image non disponible, au lieu de Image non disponible pour un arbre binaire complet. Les opérations auront une complexité en temps de Image non disponible.

V-B-2-b. Structure liée

Pour chaque nœud Image non disponible de l'arbre binaire, on retient un champ de données (Image non disponible), un pointeur vers le nœud parent (Image non disponible) et un pointeur pour chaque fils (Image non disponible et Image non disponible). Cette manière de procéder peut s'extrapoler facilement à des arbres non binaires ; on utilisera un champ Image non disponible pour retenir la clé de l'élément. On aura une complexité en espace de Image non disponible, vu qu'on ne crée que les éléments nécessaires ; les opérations auront une complexité en temps de Image non disponible.

V-B-3. Parcours en profondeur

On va descendre dans l'arbre avant d'aller visiter les nœuds voisins.

V-B-3-a. Parcours infixe (en ordre)

Chaque nœud est visité après son fils gauche et avant son fils droit.

Parcours infixe d'un arbre binaire : InorderTreeWalk(x)
Sélectionnez
if x != nil
	InorderTreeWalk(x.left)
	walk(x.key)
	InorderTreeWalk(x.left)

V-B-3-b. Parcours préfixe (en préordre)

Chaque nœud est visité avant ses fils.

Parcours préfixe d'un arbre binaire : PreorderTreeWalk(x)
Sélectionnez
if x != nil
	walk(x.key)
	InorderTreeWalk(x.left)
	InorderTreeWalk(x.left)

V-B-3-c. Parcours postfixe (en postordre)

Chaque nœud est visité après ses fils.

Parcours postfixe d'un arbre binaire : PostorderTreeWalk(x)
Sélectionnez
if x != nil
	InorderTreeWalk(x.left)
	InorderTreeWalk(x.left)
	walk(x.key)

V-B-3-d. Complexité

Tous les parcours en profondeur ont une complexité en temps de Image non disponible. En effet, on doit parcourir au moins une fois chaque nœud :

Image non disponible

Image non disponible étant le nombre de nœuds à gauche et Image non disponible une constante, on a la récursion

Image non disponible

Par induction, on prouve alors que

Image non disponible

avec

Image non disponible

On a donc prouvé

Image non disponible

soit, vu la borne inférieure,

Image non disponible

V-B-4. Parcours en largeur

On visite le nœud le plus proche de la racine qui n'a pas été visité, soit d'abord la racine, puis ses enfants, les nœuds du deuxième niveau et ainsi de suite. On peut l'implémenter à l'aide d'une file avec une complexité en temps de Image non disponible :

Parcours en largeur d'un arbre binaire : BreadthTreeWalk(x)
Sélectionnez
Q = new empty queue
Enqueue(Q, x)
while not QueueEmpty(Q)
	y = Dequeue(Q)
	walk(y.key)
	if y.left != NIL
		Enqueue(Q, y.left)
	if y.right != NIL
		Enqueue(Q, y.right)

V-C. Arbre binaire de recherche

Un arbre binaire de recherche est une structure d'arbre binaire implémentant un dictionnaire dont les opérations sont en Image non disponible, Image non disponible étant la hauteur de l'arbre. La propriété d'arbre binaire de recherche est la suivante, exprimée pour deux nœuds Image non disponible et Image non disponible :

  • si Image non disponible est dans le sous-arbre de gauche de Image non disponible, alors Image non disponible ;
  • si Image non disponible est dans le sous-arbre de droite de Image non disponible, alors Image non disponible.

Un parcours infixe d'un tel arbre donnera les clés par ordre croissant.

Toutes les opérations auront une complexité dans le pire cas de Image non disponible. En supposant que les éléments ont été insérés en ordre aléatoire, on peut montrer que Image non disponible.

V-C-1. Recherche

Une recherche (récursive terminale ou itérative) dans un tel arbre aura une complexité Image non disponible.

Recherche récursive terminale : TreeSearch(x, k)
Sélectionnez
if x == NIL or k == x.key
	return x
if k < x.key
	return TreeSearch(x.left, k)
else
	return TreeSearch(x.right, k)
Recherche itérative : IterativeTreeSearch(x, k)
Sélectionnez
x = T.root
while x != NIL and k != x:key
	if k < x.key
		x = x.left
	else
		x = x.right
return x

V-C-2. Maximum et minimum

Au vu de la propriété d'arbre binaire de recherche, la clé minimale est stockée dans le nœud le plus à gauche et la clé maximale dans le nœud le plus à droite.

Recherche du minimum : TreeMinimum(x)
Sélectionnez
while x.left != NIL
	x = x.left
return x
Recherche du maximum : TreeMaximum(x)
Sélectionnez
while x.right != NIL
	x = x.right
return x

V-C-3. Successeur

On veut, à partir d'un nœud Image non disponible, trouver le nœud contenant la valeur de clé suivante, selon un ordre arithmétique. Si le sous-arbre de droite du nœud existe, alors le successeur en est le minimum. Sinon, il s'agit du premier ancêtre Image non disponible de Image non disponible tel que Image non disponible est dans le sous-arbre de gauche de Image non disponible.

Recherche du successeur : TreeSuccessor(x)
Sélectionnez
if x.right != NIL
	return TreeMinimum(x.right)
y = x.parent
while y != NIL and x == y.right
	x = y
	y = y.parent
return y

V-C-4. Insertion

Pour insérer un élément, on recherche sa clé dans l'arbre et on l'insère là où la recherche s'est arrêtée dans le cas où elle n'existe pas encore.

Insertion : TreeInsert(T, z)
Sélectionnez
y = NIL
x = T.root
while x != nil
	y = x
	if z.key < x.key
		x = x.left
	else
		x = x.right
z.parent = y
if y == NIL
	// Tree T was empty
	T.root = z
elseif z.key < y.key
	y. left = z
else
	y.right = z

V-C-5. Suppression

Trois cas particuliers sont à considérer : un seul fils ou deux fils. S'il n'y a pas de fils, il suffit de supprimer toute référence au nœud. Le but est toujours de garder la propriété d'arbre binaire de recherche. Pour supprimer le nœud Image non disponible :

  • s'il n'a qu'un seul fils : le remplacer par celui-ci ;

  • s'il a deux fils : rechercher le successeur Image non disponible de Image non disponible :

    • si Image non disponible est le fils droit de Image non disponible, remplacer Image non disponible par Image non disponible et conserver le fils droit de Image non disponible,
    • sinon, Image non disponible est dans le sous-arbre droit de Image non disponible sans en être la racine ; on remplace Image non disponible par son propre fils droit et on remplace Image non disponible par Image non disponible.
Transplantation : Transplant(T, u, v)
Sélectionnez
if u.parent == NIL
	T.root = v
elseif u == u.parent.left
	u.parent.left = v
else
	u.parent.right = v
if v != NIL
	v.parent = u.parent
Suppression : TreeDelete(T, z)
Sélectionnez
if z.left == NIL
	Transplant(T, z, z.right)
elseif z.right == NIL
	Transplant(T, z, z.left)
else // z has two children
	y = TreeSuccessor(z)
	if y.parent != z
		Transplant(T, y, y.right)
		y.right = z.right
		y.right.parent = y
	// Replace z by y
	Transplant(T, z, y)
	y.left = z.left
	y.left.parent = y

V-C-6. Tri

Un tri dans l'ordre croissant correspond à un parcours infixe de l'arbre binaire de recherche. Sa complexité en temps est identique à celle du tri rapide, bien que sa complexité en espace soit plus importante, étant donné la structure sous-jacente.

Tri par arbre binaire de recherche : BinarySearchTreeSort(A)
Sélectionnez
T = new empty binary search tree
for i = 1 to n
	TreeInsert(T;A[i])
InorderTreeWalk(T:root)

V-D. Arbre équilibré

Pour obtenir une complexité moindre, il faut maintenir un invariant sur la structure de l'arbre et prouver qu'il garantit une hauteur Image non disponible.

V-D-1. Arbre H-équilibré

On étudiera ici les arbres AVL (Adelson-Velskii-Landis), qui ont la propriété d'être H-équilibrés. Leur invariant est, pour tout sous-arbre Image non disponible de Image non disponible,

Image non disponible

Les hauteurs des deux sous-arbres d'un nœud diffèrent au plus d'une unité. Un tel arbre aura une hauteur bornée par

Image non disponible

Précisément, on peut prouver que

Image non disponible

V-D-2. Arbre AVL

Un arbre AVL (Adelson-Velskii-Landis) est un arbre binaire de recherche H-équilibré. En tant qu'arbre binaire de recherche, on peut utiliser l'algorithme des arbres binaires de recherche pour la recherche ; il aura une complexité de Image non disponible, vu la propriété.

Pour l'insertion, on procèdera comme pour un arbre binaire classique) ; ensuite, on rétablira l'invariant au besoin à l'aide de rotations.

V-D-2-a. Rotations

Image non disponible
Rotations dans les arbres AVL.

Ces rotations sont implémentées à l'aide des algorithmes suivants.

Rotation gauche : LeftRotate(x)
Sélectionnez
r = x.right
x.right = r.left
r.left = x
return r
Rotation droite : RightRotate(x)
Sélectionnez
r = x.left
x.left = r.right
r.right = x
return r

V-D-2-b. Équilibrage

On prend Image non disponible, le nœud le plus bas violant l'invariant après insertion. Tous ses sous-arbres sont H-équilibrés, il y a cependant une différence de deux niveaux entre ses sous-arbres gauche et droit. Pour rétablir l'équilibre (en cas de déséquilibre à gauche ou à droite), on devra effectuer une ou deux rotations. Ainsi, l'insertion aura une complexité logarithmique par rapport au nombre de nœuds.

V-D-2-c. Tri

On peut utiliser un arbre AVL pour le tri : on insère successivement les éléments dans l'arbre et on effectue un parcours en ordre. On aura une complexité temporelle optimale (Image non disponible), mais une complexité en espace linéaire (on doit allouer un arbre).

V-E. Table de hachage

V-E-1. Tableau à accès direct

On suppose que chaque élément est associé à une clé unique tirée d'un univers pas trop grand, Image non disponible. Le dictionnaire est alors implémenté par le tableau Image non disponible, chaque position correspondant à une clé de l'univers. Si le dictionnaire contient un élément Image non disponible avec la clé Image non disponible, alors Image non disponible contient un pointeur vers Image non disponible. Sinon, Image non disponible est un pointeur nul.

On a ainsi un dictionnaire à accès en temps constant, ainsi que la suppression et la recherche. Sa taille sera constante (Image non disponible), il ne pourra pas retenir plusieurs éléments avec la même clé. Si l'ensemble des clés utilisées est très inférieur à l'univers, alors on gaspille beaucoup de place.

V-E-2. Table de hachage

On utilise un tableau Image non disponible de taille largement inférieure à la taille de l'univers. On placera l'élément Image non disponible de clé Image non disponible à la position Image non disponible, où Image non disponible est une fonction de hachage qui établit un lien entre l'univers Image non disponible et l'ensemble des clés de Image non disponible.

Cependant, on a un risque de collision : deux clés distinctes ont la même image par la fonction de hachage. Par le principe des tiroirs, cela se produit toujours lorsqu'on a plus d'éléments à stocker que la taille du tableau. Selon le paradoxe des anniversaires, c'est même très probable, même si la fonction de hachage répartit les clés de manière uniforme.

Deux solutions pour éviter les collisions : une fonction de hachage qui répartit de manière uniforme les clés ou un tableau de taille suffisante. Dans chaque cas, en cas de remplissage suffisant, la probabilité de collision restera élevée. Deux approches résolvent définitivement ce problème : l'adressage ouvert et l'adressage fermé.

V-E-3. Fonction de hachage

Idéalement, une fonction de hachage devrait être facile à calculer (en temps constant) et satisfaire l'hypothèse de hachage uniforme, ce qui n'est pas forcément facile à obtenir (on ne connaît généralement pas la distribution des clés et elles ne sont pas forcément indépendantes). Une telle fonction suppose que la clé est un nombre naturel (sinon, il faut la coder : par exemple, pour une chaîne de caractères, prendre la valeur ASCII de chaque caractère, la pondérer par Image non disponible et sommer).

V-E-3-a. Méthode de division

La fonction de hachage calcule le reste de la division entière de la clé par la taille de la table :

Image non disponible

Cette manière de procéder est très rapide, mais dépend beaucoup du choix de Image non disponible : si Image non disponible, alors le résultat ne dépend que des Image non disponible bits les moins significatifs ; si Image non disponible et Image non disponible est une chaîne de caractères codée en base Image non disponible, alors permuter les caractères de Image non disponible n'influence pas le résultat ; si les clés sont périodiques et Image non disponible est non premier, on n'exploite qu'une partie des valeurs possibles (pour Image non disponible, l'image de Image non disponible sera Image non disponible).

V-E-3-b. Méthode de multiplication

Avec une constante Image non disponible telle que Image non disponible, Image non disponible est la partie fractionnaire de Image non disponible, on utilise la fonction

Image non disponible

La valeur de Image non disponible n'est plus critique, mais certaines valeurs de Image non disponible fonctionnent mieux.

V-E-4. Chaînage (adressage fermé)

Simplement, on stocke les éléments qui ont le même hash dans une liste (doublement) liée. On aura une insertion (en début de liste) en temps constant, une suppression linéaire pour une liste liée ou constante pour une liste doublement liée, une recherche linéaire du nombre d'éléments dans la liste, du moins dans le pire cas.

Afin d'étudier la complexité dans le cas moyen, on définit le facteur de charge

Image non disponible

Image non disponible est la taille du tableau et Image non disponible le nombre d'éléments stockés. On supposera le hachage parfaitement uniforme : pour toute clé Image non disponible, on a

Image non disponible

On considérera également que la fonction de hachage Image non disponible a une complexité temporelle Image non disponible et que l'on insère les éléments en début de liste.

Ainsi, dans le cas moyen, que la recherche soit positive ou non, on aura une complexité temporelle de Image non disponible (Image non disponible pouvant être aussi bien inférieur à l'unité ou très grand, en fonction du remplissage). Si on a

Image non disponible

soit si Image non disponible croît au moins linéairement avec la taille du tableau, on aura

Image non disponible

Toutes les opérations seront Image non disponible en moyenne.

V-E-4-a. Critique

On peut gérer un nombre illimité d'éléments et de collisions, les performances restant stables. On a cependant un surcoût lié à la gestion et au stockage des listes liées.

V-E-5. Sondage (adressage ouvert)

On stocke tous les éléments dans le tableau : une fois celui-ci rempli, on ne peut plus ajouter d'élément. Pour insérer une clé Image non disponible, on sonde toutes les autres cases à partir de Image non disponible en suivant une fonction de sondage Image non disponible.

La fonction de hachage est ainsi définie sur Image non disponible et telle que

Image non disponible

est une permutation de Image non disponible.

Pour supprimer, on ne peut pas simplement mettre un pointeur nul à l'endroit qui vient d'être libéré, on ne saurait jamais si on doit poursuivre la recherche. On utilise donc une valeur spéciale : lors de la recherche, on sait qu'on devra continuer ; lors d'une insertion, la case est considérée vide. Ainsi, le temps de recherche ne dépend plus du facteur de charge, mais de la charge maximale de la table.

Une stratégie de sondage efficace donnera un hachage uniforme : chacune des permutations de Image non disponible a la même probabilité de correspondre à une clé. Cela est cependant dur à garantir, on se satisfera généralement du fait que l'on a une permutation.

  • Sondage linéaire : facile à implémenter, on se limite à aller voir la case suivante ; on crée ainsi un fort effet de grappe, pas d'uniformité ; on a la fonction

    Image non disponible
  • Sondage quadratique : à l'aide de deux constantes bien choisies (pour garder la propriété de permutation), on effectue un parcours quadratique de la table ; l'effet de grappe est toujours présent, bien que moins marqué ; on a la fonction

    Image non disponible
  • Double hachage : on utilise deux fonctions de hachage différentes, à bien choisir pour garder la permutation ; le résultat sera très proche de l'uniformité, bien meilleur que les techniques précédentes ; on aura la fonction

    Image non disponible

V-E-5-a. Critique

Limitée par la taille du tableau, cette méthode est rapide et peu gourmande en mémoire, bien que plus ardue à implémenter pour éviter les grappes. Les suppressions sont problématiques et les performances dégringolent dès que la table est bien remplie (on peut envisager de créer une table plus grande pour stocker les éléments, mais cela empêche d'utiliser la table pendant un certain temps et il faut sélectionner une nouvelle fonction de hachage et réinsérer tous les éléments ; on garde cependant le même coût asymptotique si on double la taille, par amortissement).

V-F. Résumé

  Complexité en recherche Complexité en insertion Complexité en suppression
Implémentation Pire cas Cas moyen Pire cas Cas moyen Pire cas Cas moyen
Liste Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible
Vecteur trié Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible
Arbre binaire de recherche Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible
Arbre équilibré Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible
Table de hachage Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible

V-F-1. Arbres de recherche ou table de hachage ?

Une table de hachage est facile à implémenter, la seule solution disponible pour des clés non ordonnées, a des recherche et insertion très rapides en moyenne, mais gaspille de l'espace en faible facteur de charge ; dans le pire cas, les performances ne sont pas garanties.

Un arbre binaire de recherche (équilibré ou non ; ABR ou AVL) aura des performances garanties, ne gaspillera pas de mémoire, supportera plus d'opérations car les clés sont ordonnées, bien que l'accès et l'insertion soient plus lents en moyenne.

VI. Résolution de problèmes

VI-A. Force brute

Cette approche résout directement le problème à partir de sa définition ou d'une recherche exhaustive.

En appliquant la définition, elle mène aux tris à bulle et par sélection, de complexité quadratique ; par recherche exhaustive, on générera tous les tableaux possibles par permutation, on sélectionnera le premier à être ordonné : cette approche a une complexité temporelle de Image non disponible.

Bien que parfois seule solution possible (problème du voyageur de commerce), il existe généralement de meilleures solutions. Cette technique est très simple et d'application très large, il s'agit donc d'un bon point de départ pour trouver d'autres algorithmes plus performants (faire mieux n'a pas toujours d'intérêt), plus élégants et créatifs.

VI-B. Diviser pour régner

On divise le problème en sous-problèmes plus faciles à résoudre (jusqu'au cas de base) que l'on fusionne pour obtenir la solution du problème original. On trouve donc trois étapes : diviser (diviser le problème), régner (résoudre récursivement les sous-problèmes jusqu'au cas de base, trivial à résoudre) et fusionner (à partir des solutions des sous-problèmes, trouver la solution du problème original).

Cette approche mène aux tris par fusion et rapide, deux algorithmes de complexité optimale (au lieu de quadratique par force brute).

Elle mène à des algorithmes efficaces, cette méthode est donc très utile, bien qu'elle ne soit pas toujours applicable.

VI-C. Programmation dynamique

On cherche à obtenir la solution optimale en combinant des solutions optimales de sous-problèmes se chevauchant. Il s'agit d'une généralisation de l'approche précédente : les sous-problèmes peuvent se chevaucher, dépendre l'un de l'autre. Notamment, quand le même sous-problème apparaît plusieurs fois, on s'arrange pour ne le résoudre qu'une seule en sauvegardant les solutions dans une table (on échange du temps de calcul contre de la mémoire). En général, on peut transformer un problème de complexité exponentielle en une classe polynomiale.

On en distingue deux cas : la programmation dynamique descendante avec mémoization (on résout le problème en partant des plus grandes instances de manière récursive en sauvegardant les résultats intermédiaires dans un tableau qui est passé à chaque appel) et la programmation dynamique ascendante (on résout d'abord les instances de petite taille jusqu'à la taille demandée, puis on retourne la valeur obtenue, sans récursivité).

Il est nécessaire de disposer de la propriété de sous-structure optimale : une solution optimale est composée de solutions optimales à des sous-problèmes.

La procédure générale consiste à définir de manière récursive la valeur à optimiser de la meilleure solution, puis à calculer ces valeurs pour reconstruire (à partir du tableau généré) une solution optimale (approche bottom-up).

On ne peut cependant pas utiliser la récursivité pour implémenter ces algorithmes de manière efficace : alors que l'approche diviser pour régner divise les problèmes en instances significativement plus petites (Image non disponible) et totalement indépendantes, la programmation dynamique n'en réduira la taille que de très peu (Image non disponible) tout en gardant une certaine dépendance.

VI-D. Approche gloutonne

On construit incrémentalement la solution en optimisant localement pour obtenir un optimum global. On doit donc effectuer à chaque fois un choix, alors que la programmation dynamique explore tous les choix possibles. En fonction des problèmes, des entrées et des paramètres, on pourrait n'obtenir qu'une bonne solution pas forcément optimale (on doit explorer tous les choix pour s'en assurer : programmation dynamique). Dans tous les cas, on ne récupérera qu'une solution optimale au problème.

Quand on a un choix local à faire, on effectue un choix glouton qui semble le meilleur immédiatement (sans jamais le remettre en question). Pour que l'algorithme soit correct, il faut donc prouver la propriété des choix gloutons optimaux (en effectuant ce choix de manière locale, on arrive toujours à une solution optimale). Pour que l'approche fonctionne, il faut aussi prouver la propriété de sous-structure optimale : une solution optimale du problème est composée de solutions optimales à des sous-problèmes. Si ces propriétés ne sont pas vérifiées, l'approche ne donnera pas forcément un optimal mais bien une approximation (on peut, dans certains cas, en caractériser la distance à l'optimal).

Quand un tel algorithme existe, il est très efficace et simple à implémenter. Cependant, quand il existe, sa correction peut être assez difficile à établir.

Par rapport à la programmation dynamique, on doit prouver la propriété des choix gloutons optimaux. Grâce à celle-ci, on n'aura pas besoin de résoudre plusieurs sous-problèmes : il est effectué avant de résoudre un sous-problème. Il n'y a pas besoin de stocker les résultats intermédiaires, la solution obtenue ne doit pas être recomposée.

VII. Graphes

VII-A. Définitions

Un graphe est un couple Image non disponible, où Image non disponible est un ensemble de nœuds (sommets) et Image non disponible un ensemble d'arcs (ou arêtes). Une arête est un ensemble de deux sommets Image non disponible. Un graphe non dirigé (ou non orienté) est caractérisé par une relation symétrique entre les sommets.

Deux nœuds sont adjacents s'ils sont liés par une même arête ; cette arête sera incidente à ces deux nœuds. Le degré d'un nœud est le nombre de ses arêtes incidentes. Le degré d'un graphe est le nombre maximal d'arêtes incidentes à un sommet.

Un graphe sera connexe s'il existe un chemin de tout sommet à tout autre (en suivant le sens des arêtes, le cas échéant). Une composante connexe d'un graphe non orienté est un sous-ensemble connexe maximal de ce graphe (si on ajoute un nœud du graphe étudié, il ne sera plus connexe).

Dans un graphe dirigé, une arête Image non disponible possède l'origine Image non disponible et la destination Image non disponible. Cette arête sera sortante pour Image non disponible et entrante pour Image non disponible. On définit ainsi les degrés entrant et sortant. Un graphe acyclique n'a aucun cycle : il n'est pas possible de suivre les arêtes du graphe à partir d'un sommet et de revenir à ce même sommet.

Un graphe simple ne possède pas de boucle composée d'une seule arête : Image non disponible. Un arbre est un graphe acyclique connexe. Un multigraphe est une généralisation des graphes pour laquelle il est permis de définir plus d'une arête liant un sommet à l'autre. Un graphe pondéré aura des arêtes annotées par des poids.

Un sommet Image non disponible est accessible à partir de Image non disponible si Image non disponible, Image non disponible est adjacent à Image non disponible ou si Image non disponible est adjacent à un sommet de Image non disponible accessible à partir de Image non disponible.

VII-B. Représentations

De manière très naïve, on pourrait représenter un graphe comme une liste de nœuds et d'arêtes, mais cette solution n'est pas la plus efficace.

On peut utiliser, pour chaque nœud, une liste d'adjacence : des listes liées pour chaque nœud indiquant les autres extrémités des arêtes. Si on associe un poids à chaque élément de la liste, on peut représenter un graphe pondéré ; on peut représenter indifféremment un graphe dirigé ou non (on insérera chaque arête deux fois). Pour un graphe Image non disponible, on aura donc la liste de nœuds Image non disponible (Image non disponible éléments) et un tableau Image non disponible de listes d'adjacence, tel que chaque sommet est représenté par un élément de ce tableau.

On peut aussi utiliser une matrice d'adjacence, le graphe étant alors entièrement représenté par une matrice Image non disponible de dimension Image non disponible. Cette matrice est telle que

Image non disponible

Si le graphe est non dirigé, elle sera symétrique. On peut également représenter des graphes pondérés en mettant le poids à la place du booléen.

  Complexité en espace Complexité en temps d'accès à un sommet Complexité en temps du parcours des sommets Complexité en temps du parcours des arêtes Complexité en temps de la vérification de l'existence d'une arête
Liste d'adjacence Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible
Matrice d'adjacence Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible
Optimal Image non disponible Image non disponible Image non disponible Image non disponible Image non disponible

On préférera les listes d'adjacence pour des graphes creux (Image non disponible) ou de degré faible, alors qu'on utilisera des matrices d'adjacence pour des graphes denses (Image non disponible) ou pour des algorithmes désirant accéder aléatoirement aux arêtes.

VII-C. Parcours de sommets

On cherche à parcourir tous les sommets accessibles à partir d'un sommet donné. Dans un graphe non dirigé, seule la composante connexe contenant Image non disponible est visitée ; s'il est dirigé, seule une partie de cette composante sera visitée.

VII-C-1. En largeur

On parcourt les sommets par ordre croissant de distance par rapport au sommet argument Image non disponible : on visite Image non disponible, puis ses voisins, puis les voisins des voisins, etc., jusqu'à avoir parcouru tous les sommets accessibles.

On devra retenir les sommets déjà visités pour éviter de partir en boucle infinie. De même, on doit retenir les sommets visités dont on n'a pas encore visité les voisins. Aussi, on devra retenir la distance d'un sommet Image non disponible à Image non disponible, Image non disponible : elle sera finie si le sommet Image non disponible a été visité. La file (structure LIFO) contiendra les sommets qui ont été visités, mais pas leurs voisins.

Chaque sommet sera visité au plus une fois (sa distance à Image non disponible sera alors finie et il ne sera plus parcouru). La boucle principale s'exécutera Image non disponible fois, la boucle interne Image non disponible fois en tout. La complexité totale sera de Image non disponible.

Parcours en largeur : GraphBreadthFirstSearch(G, s)
Sélectionnez
for each vertex u in G.V n fsg
	u.d = infinity
s.d = 0
Q = new create empty Queue
Enqueue(Q, s)
while not QueueEmpty(Q)
	u = Dequeue(Q)
	for each v in G.Adj[u]
		if v.d = 1
			v.d = u.d + 1
			Enqueue(Q, v)

VII-C-2. En profondeur

On part d'un sommet et on suit toutes les arêtes incidentes sans les mettre en attente ; on revient en arrière dès que le sommet visité n'a plus de sommet adjacent.

On retient les sommets visités ; chacun sera empilé au plus une fois.

La boucle principale s'exécutera Image non disponible fois, la boucle interne Image non disponible fois en tout. La complexité totale sera de Image non disponible.

Parcours en profondeur : GraphDepthFirstSearch(G, s)
Sélectionnez
for each vertex u in G.V n fsg
	u.visited = False
S = new create empty stack
Push(S, s)
while not StackEmpty(Q)
	u = Pop(S)
	if u.visited == False
		u.visited = True
		for each v in G.Adj[u]
			if v.visited == False
				Push(S, v)
Initialisation du parcours en profondeur récursif : DFS(G, s)
Sélectionnez
for each vertex u in G.V
	u.visited = False
DFSRec(G, s)
Parcours en profondeur récursif : DFSRec(G, s)
Sélectionnez
s.visited = True
for each v in G.Adj[s]
	if v.visited == False
		DFSRec(G, v)

VII-D. Plus court chemin

Avec le graphe dirigé Image non disponible et la fonction de poids associée Image non disponible (le poids peut être négatif, sauf pour certains algorithmes), on définit un chemin du sommet Image non disponible à Image non disponible comme une séquence de nœuds Image non disponible telle que chaque paire consécutive de ces nœuds forme une arête du graphe. Le poids associé à un chemin Image non disponible sera la somme des poids des arêtes qui le composent :

Image non disponible

Ainsi, un plus court chemin entre deux sommets sera le chemin de poids le plus faible. On note Image non disponible le poids associé au plus court chemin entre Image non disponible et Image non disponible ; s'il n'existe pas de tel chemin, ce poids sera infini ; on peut définir ce symbole comme

Image non disponible

On recense divers variantes du problème de recherche de plus court chemin :

  • origine unique : trouver tous les chemins les plus courts d'un sommet à tous les autres (algorithmes de Dijkstra et de Bellman-Ford ; pour un graphe dirigé acyclique : relâchement selon un ordre topologique, Image non disponible ; graphe dirigé et poids positifs : Dijkstra et Image non disponible ; graphe dirigé et poids quelconques : Bellman-Ford et Image non disponible) ;
  • destination unique : trouver tous les chemins les plus courts de tous les sommets vers un sommet donné ;
  • paire unique : trouver le plus court chemin entre deux sommets (tous les algorithmes connus ont la même complexité asymptotique dans le pire cas que le problème d'origine unique) ;
  • toutes les paires : trouver tous les chemins les plus courts entre toutes les paires de sommets du graphe (algorithme de Floyd-Warshall, Image non disponible).

VII-D-1. Propriétés

VII-D-1-a. Propriété de sous-structure optimale

Tout sous-chemin d'un chemin le plus court est un chemin le plus court entre ses extrémités.

On peut le prouver par l'absurde : on prend un plus court chemin Image non disponible entre Image non disponible et Image non disponible et un sous-chemin Image non disponible défini entre ses extrémités Image non disponible et Image non disponible. S'il existe un chemin plus court que Image non disponible entre Image non disponible et Image non disponible, on pourrait remplacer la portion Image non disponible de Image non disponible par ce chemin plus court et ainsi obtenir un chemin plus court que Image non disponible entre Image non disponible et Image non disponible.

VII-D-1-b. Cycles

En cas de cycle de poids négatif (on parle également de cycle absorbant), on peut réduire autant que l'on veut le poids d'un chemin en y passant aussi souvent que nécessaire. Ainsi, si un chemin de Image non disponible à Image non disponible passe par un cycle négatif, on posera

Image non disponible

Un chemin le plus court ne peut pas contenir de cycle. S'il a un poids négatif, on ne définit pas de chemin le plus court. S'il a un poids nul, il n'y a pas de raison d'utiliser ces cycles (et on ne les utilisera pas). S'il a un poids positif, on peut obtenir un chemin plus court en les supprimant.

VII-D-1-c. Inégalité triangulaire

Pour tous Image non disponible et Image non disponible dans Image non disponible, on a

Image non disponible

En effet, si on a un plus court chemin entre Image non disponible et Image non disponible, passer par un nouveau nœud supplémentaire ne peut être qu'indifférent ou négatif.

On dispose aussi d'un corollaire : l'origine Image non disponible étant fixée, pour tout Image non disponible,

Image non disponible

VII-D-2. Problème d'origine unique

D'un graphe dirigé Image non disponible et pondéré par la fonction de poids Image non disponible, d'un sommet Image non disponible (l'origine), on veut imposer à chaque sommet deux attributs : la plus grande distance de Image non disponible à ce nœud (Image non disponible) et le prédécesseur dans un plus court chemin (Image non disponible), pour former l'arbre des plus courts chemins partant de Image non disponible et reconstruire la solution optimale (par la propriété de sous-structure optimale, cette information est suffisante : on connaît un nœud, on y ajoute le chemin le plus court pour le nœud précédent et on a le chemin total ; par application récursive, on trouve le chemin optimal).

Par force brute, la résolution n'est pas forcément aisée : si on essaie tous les chemins possibles dans un graphe, on risque de tomber sur un cycle ; or, dans ce cas, le nombre de chemins est infini ! De même, on peut avoir un nombre de chemins exponentiel par rapport au nombre de sommets et d'arêtes (si on a Image non disponible nœuds et que presque tous ont un degré deux, on aura Image non disponible chemins, d'où la complexité de l'algorithme dans ce cas précis ; dans le pire cas, on peut monter à une complexité de Image non disponible, si chaque nœud a un degré Image non disponible, soit pour un graphe hyperconnexe).

VII-D-2-a. Schéma général d'un algorithme

On cherche d'abord à calculer les distances par rapport à un nœud. On se basera sur l'inégalité triangulaire. Après initialisation de toutes les distances à Image non disponible, Image non disponible contiendra à chaque fois une estimation d'un plus court chemin de Image non disponible à Image non disponible ; on maintiendra l'invariant

Image non disponible

Chaque itération tentera d'améliorer l'estimation Image non disponible pour converger vers la longueur du chemin le plus court.

Pour améliorer une arête, on utilisera une routine de relâchement (terme hérité de la programmation linéaire), afin de mettre à jour l'approximation si on se rapproche de l'optimum. L'algorithme verra sa complexité varier fortement en fonction du choix de l'arête : notamment, à la première itération, tout choix de nœud qui n'est pas directement accessible depuis l'itération conduira à ne rien faire (la longueur depuis l'origine étant infinie par initialisation).

La fonction de poids Image non disponible est intégrée dans la structure de graphe.

Algorithme général de recherche de plus court chemin depuis une origine unique : SingleSource(G, s)
Sélectionnez
// Initialisation
for each v in G.V
	v.d = infinity
	v.p = NIL
s.d = 0

while there is one edge (u, v) such that v.d > u.d + w(u; v)
	Pick one edge (u,v)
	// Relaxation
	if v.d > u.d + G.w(u; v)
		v.d = u.d + w(u; v)
		v.p = u

Grâce aux propriétés ci-après, pour montrer qu'un algorithme de plus court chemin basé sur ce squelette est correct, il suffira de montrer que le choix des arêtes mènera bien à

Image non disponible

On note que, si le gardien de la boucle autorisait l'égalité, l'algorithme partirait en boucle infinie, vu qu'il est attendu que Image non disponible atteigne Image non disponible sans descendre plus bas.

L'algorithme général maintient toujours l'invariant.

On peut le prouver par induction sur le nombre d'itérations. Après l'initialisation, l'invariant est respecté ; ensuite, pour chaque itération, avant le relâchement, on considère l'invariant respecté. Par l'inégalité triangulaire, on a alors

Image non disponible

Après l'assignation, si elle a lieu,

Image non disponible

l'invariant est toujours respecté, car

Image non disponible

L'algorithme général ne modifie plus Image non disponible une fois l'optimum atteint.

On a toujours

Image non disponible

et la relaxation ne peut que diminuer la valeur de Image non disponible.

L'algorithme général s'arrête à des chemins d'au plus Image non disponible arêtes après la Image non disponible itération.

En d'autres termes,

Image non disponible

On doit imposer un graphe sans cycle de poids négatif.

Avant la première itération,

Image non disponible

Ensuite, on suppose qu'on a, avant l'itération Image non disponible,

Image non disponible

Cette propriété reste vraie pendant toute l'itération, puisque le relâchement ne peut que faire diminuer Image non disponible ; cette itération considère tous les chemins avec Image non disponible arêtes ou moins en relaxant les arêtes entrantes en Image non disponible, les poids ayant été calculés pour Image non disponible arêtes.

VII-D-2-b. Algorithme de Bellman-Ford

L'algorithme de Bellman-Ford se base sur la relaxation pour effectuer son travail et est l'algorithme le plus général pour résoudre ce problème. On considère les arêtes Image non disponible dans un ordre quelconque et on effectue Image non disponible relaxations dans cet ordre précis. On aura donc le pseudocode suivant.

Algorithme de Bellman-Ford
Sélectionnez
// Initialisation
for each v in G.V
	v.d = infinity
	v.p = NIL
s.d = 0

for i=1 to |G:V| - 1
	for each edge (u, v) in G.E
		// Relaxation
		if v.d > u.d + G.w(u, v)
			v.d = u.d + w(u, v)
			v.p = u

En supposant qu'on puisse parcourir les arêtes en Image non disponible, puisque la boucle interne est exécutée exactement Image non disponible fois, l'algorithme aura une complexité Image non disponible.

Cet algorithme implémente une approche par programmation dynamique de manière itérative. Si on note Image non disponible la longueur du plus court chemin de Image non disponible à Image non disponible utilisant au plus Image non disponible arêtes, on a la formule récursive

Image non disponible
VII-D-2-b-i. Correction

Si le graphe ne contient pas de cycle négatif, l'algorithme de Bellman-Ford est correct. En d'autres termes, on a à la fin

Image non disponible

Le graphe n'ayant pas de cycle de poids négatif, tout plus court chemin doit être simple (acyclique). Un tel chemin a au plus Image non disponible sommets, donc Image non disponible arêtes. Après Image non disponible itérations, on a

Image non disponible

Or, par l'invariant, on a

Image non disponible

d'où

Image non disponible
VII-D-2-b-ii. Détection des cycles négatifs

On peut implémenter une recherche de cycles de poids négatif à la fin de l'algorithme ; il renverra une valeur booléenne vraie en cas de cycle négatif accessible depuis Image non disponible.

Algorithme de Bellman-Ford et détection des cycles négatifs
Sélectionnez
// Initialisation
for each v in G.V
	v.d = infinity
	v.p = NIL
s.d = 0

for i=1 to |G:V| - 1
	for each edge (u, v) in G.E
		// Relaxation
		if v.d > u.d + G.w(u, v)
			v.d = u.d + w(u, v)
			v.p = u

for each edge (u, v) in G.E
	if v.d > u.d + w(u, v)
		return False
return true
VII-D-2-b-iii. Graphe dirigé acyclique

On peut rendre l'algorithme plus efficace dans le cas d'un graphe dirigé acyclique.

Algorithme de Bellman-Ford pour des graphes dirigés acycliques
Sélectionnez
// Initialisation
L = TopSort(G)
for each v in G.V
	v.d = infinity
	v.p = NIL
s.d = 0

for each vertex u, taken in their order in L
	for each vertex v in G.Adj[u]
		// Relaxation
		if v.d > u.d + G.w(u, v)
			v.d = u.d + w(u, v)
			v.p = u

VII-D-2-c. Parcours en largeur

Si les poids sont tous égaux à l'unité, un parcours en largeur suffit pour déterminer le plus court chemin en Image non disponible. Pour simuler des chemins plus longs, on peut ajouter des nœuds intermédiaires ; si les poids sont des entiers dans l'intervalle Image non disponible, la complexité sera alors de Image non disponible, soit déjà un grand gain par rapport à l'algorithme de Bellman-Ford. On ira ainsi des nœuds adjacents à l'origine aux nœuds les plus excentrés.

Parcours en largeur et chemins les plus courts
Sélectionnez
for each vertex u in G.V\{s}
	u.d = 1
s.d = 0
Q = new empty Queue

Enqueue(Q, s)
while not QueueEmpty(Q)
	u = Dequeue(Q)
	for each v in G:Adj[u]
		if v.d = 1
			v.d = u.d + 1
			Enqueue(Q, v)

VII-D-2-d. Algorithme de Dijkstra

Partant de la structure d'un parcours en largeur, on peut utiliser une approche gloutonne en généralisant au passage à des poids positifs non entiers. On maintient un ensemble Image non disponible de sommets dont le poids d'un plus court chemin à partir de Image non disponible est connu (utilité surtout théorique) ; à chaque étape, on ajoute un sommet Image non disponible à Image non disponible dont la distance à Image non disponible est minimale. On met alors à jour les distances estimées des sommets adjacents à Image non disponible, en maintenant une file à priorité minimale Image non disponible pour déterminer l'ordre des éléments à traiter.

Algorithme de Dijkstra
Sélectionnez
// Initialisation
for each v in G.V
	v.d = infinity
	v.p = NIL
s.d = 0
S = empty set
Q = new empty min priority queue from G.V

while not QueueEmpty(Q)
	u = QueueExtractMin(Q)
	S = union of S and {u}
	for each v 2 G:Adj[u]
		if v.d > u.d + G.w(u, v)
			v.d = u.d + w(u, v)
			v.p = u
			QueueSetPriority(v, v.d)

Si la file à priorité est implémentée par un tas, l'extraction et l'ajustement de la clé sont réalisés en Image non disponible. Chaque sommet est extrait de la file à priorité une et une seule fois, d'où une boucle principale en Image non disponible, sans compter le relâchement. Chaque arête est parcourue une et une seule fois, ce qui entraîne au plus un ajustement de clé, d'où une boucle interne en Image non disponible. En tout, on aura un algorithme de complexité Image non disponible ; si on considère le graphe connexe, on peut la simplifier en Image non disponible.

VII-D-2-d-i. Correction

On cherche à prouver que l'algorithme de Dijkstra se termine avec

Image non disponible

On remarque tout d'abord que, lorsqu'un nœud Image non disponible est extrait de la file Image non disponible, son champ Image non disponible n'est plus modifié. On montre donc que la propriété ci-dessus est respectée quand on extrait un nœud de la file. L'invariant de l'algorithme général est toujours

Image non disponible

On procède par l'absurde en supposant qu'il existe un nœud Image non disponible tel que

Image non disponible

lors de son extraction et qu'il s'agisse du premier nœud satisfaisant cette propriété. On considère alors Image non disponible, le premier nœud d'un plus court chemin de Image non disponible à Image non disponible se trouvant dans la file avant l'extraction de Image non disponible. Image non disponible en est le prédécesseur. Image non disponible étant le premier nœud violant l'invariant, on doit avoir

Image non disponible

Par la propriété de sous-structure optimale, le sous-chemin de Image non disponible à Image non disponible est un plus court chemin, Image non disponible a été assigné, lors de l'extraction de Image non disponible, à

Image non disponible

Or, on doit avoir, puisqu'on s'apprête à extraire Image non disponible de la file,

Image non disponible

On doit donc avoir

Image non disponible

ce qui contredit l'hypothèse.

VII-D-3. Problème de recherche pour toutes les paires

D'un graphe dirigé Image non disponible et de sa fonction de poids Image non disponible, on cherche à produire une matrice Image non disponible de taille Image non disponible, où

Image non disponible

VII-D-3-a. Réutilisation des algorithmes de Bellman-Ford ou Dijkstra

Dans le cas général, on peut appliquer l'algorithme de Bellman-Ford sur chaque sommet pour obtenir une complexité de Image non disponible (si le graphe est dense, Image non disponible et on a la complexité Image non disponible.

Si on n'a pas de poids négatif, on peut utiliser l'algorithme de Dijkstra et améliorer la complexité en Image non disponible (ou, pour un graphe dense, Image non disponible).

VII-D-3-b. Algorithme de Floyd-Marshall

En appliquant les principes de la programmation dynamique, on peut réduire la complexité à Image non disponible par l'algorithme de Floyd-Marshall.

Pour un chemin Image non disponible, un sommet intermédiaire sera un sommet qui n'est ni origine ni extrémité de ce chemin. On notera Image non disponible le poids d'un plus court chemin en Image non disponible et Image non disponible n'utilisant qu'un sous-ensemble des Image non disponible premiers nœuds comme sommets intermédiaires.

L'algorithme reviendra à implémenter le fait que, si Image non disponible n'est pas un sommet intermédiaire de Image non disponible, alors tous les sommets intermédiaires de Image non disponible sont dans Image non disponible, sinon, tous les sommets intermédiaires des sous-chemins entre Image non disponible et Image non disponible et entre Image non disponible et Image non disponible appartiennent à Image non disponible. De manière récursive,

Image non disponible

Ci-dessous, une implémentation ascendante basée sur la matrice d'adjacence pondérée (Image non disponible si l'arête n'est pas dans le graphe, son poids sinon).

Algorithme de Floyd-Warshall
Sélectionnez
D[0] = W
for k = 1 to n
	let D[k] = (d[k][i][j]) be a new n * n matrix
	for i = 1 to n
		for j = 1 to n
			d[k][i][j] = min{d[k-1][i][j], d[k-1][i][k] + d[k-1][k][j]}
return D[n]

VII-E. Arbre couvrant

Un arbre couvrant pour un graphe connexe non dirigé Image non disponible est un arbre (graphe acyclique) Image non disponible tel que

  • l'ensemble des nœuds de Image non disponible est Image non disponible ;
  • l'ensemble des arcs de Image non disponible est un sous-ensemble de Image non disponible.

Il sera dit de poids minimal pour un graphe pondéré par la fonction Image non disponible si, de plus, on a la valeur minimale de

Image non disponible

VII-E-2. Approche générique

Un arbre couvant minimal est un sous-ensemble d'arêtes du graphe initial ; ainsi, on part avec un ensemble Image non disponible vide auquel on ajoute des arêtes en respectant l'invariant qu'il existe un arbre couvrant minimal qui contienne ces arêtes. À cette fin, on définit la notion d'arête sûre : une arête Image non disponible sera sûre pour Image non disponible si et seulement s'il existe un arbre couvrant minimal qui contient les arêtes de Image non disponible.

On se retrouve donc avec l'algorithme générique suivant, il faudra encore caractériser plus avant les arêtes sûres.

Arbre couvrant minimal et approche générique
Sélectionnez
A = empty set
while A is not a spanning tree
	find an edge (u, v) that is safe for A
	A = union of A and {(u, v)}
return A

VII-E-3. Caractérisation des arêtes sûres

Avec Image non disponible et Image non disponible, on définit la coupure Image non disponible comme une partition des sommets en deux ensembles disjoints Image non disponible et Image non disponible, l'arête traverse d'une coupure Image non disponible comme une arête dont une extrémité est dans Image non disponible et l'autre dans Image non disponible. Une coupure respecte Image non disponible si et seulement s'il n'y a pas d'arête dans Image non disponible qui traverse la coupure.

VII-E-3-a. Propriété des choix gloutons optimaux

Soit Image non disponible, un sous-ensemble d'un arbre couvrant minimal ; Image non disponible, une coupure qui respecte Image non disponible ; Image non disponible, une arête de poids minimal qui traverse la coupure Image non disponible ; ainsi, Image non disponible est une coupure sûre pour Image non disponible.

On considère Image non disponible, un arbre couvrant minimal qui inclut Image non disponible. On suppose que Image non disponible ne contient pas Image non disponible et on montre qu'il est possible de construire un arbre Image non disponible qui inclut Image non disponible.

Puisque Image non disponible est un arbre, le chemin Image non disponible de Image non disponible à Image non disponible est unique, il traverse la coupure Image non disponible. Soit Image non disponible, une arête de Image non disponible qui traverse cette coupure. Puisque Image non disponible est une arête de poids minimum qui traverse la coupure,

Image non disponible

Puisque la coupure respecte Image non disponible, l'arête Image non disponible ne fait pas partie de Image non disponible.

On définit alors Image non disponible comme

Image non disponible

Image non disponible est un arbre couvrant et

Image non disponible

Image non disponible est donc bien un arbre couvrant minimal tel que Image non disponible et Image non disponible est bien une arête sûre pour Image non disponible.

VII-E-4. Algorithme de Kruskal

On construit une forêt, en ajoutant progressivement des arêtes à un graphe dépourvu d'arcs initialement. On maintient en permanence une partition du graphe en cours de construction en ses composantes connexes. Pour relier des composantes connexes, on choisit à chaque fois l'arête de poids minimal qui les connecte. On s'arrête dès qu'il ne reste plus qu'une composante connexe.

Cet algorithme est correct : puisqu'on connecte à chaque fois deux composantes connexes disjointes, on forme un arbre ; à la fin, on forme un arbre de recouvrement. Puisqu'on sélectionne une arête de poids minimal à chaque étape, la propriété des choix gloutons optimaux garantit que le résultat sera bien un arbre de recouvrement minimal.

On peut choisir les composantes connexes à fusionner de manière totalement arbitraire.

Algorithme de Kruskal
Sélectionnez
A = empty set
P = empty set
for each vertex v 2 G:V
	P = union of P and {{v}}
for each (u, v) in G.E taken into nondecreasing order of weight
	P1 = subset in P containing u
	P2 = subset in P containing v
	if P1 != P2
		A = union of A and {(u, v)}
		P = P1 merged with P2
return A

VIII. Conclusion

Au bout de ce cheminement relativement ardu, vous voilà armés pour partir dans vos développements en connaissance de cause : vous aurez le bagage théorique pour comprendre pourquoi votre algorithme est lent, pour prouver à quiconque que cette partie du programme ne peut être que fausse et que l'erreur doit venir des paramètres donnés. Ces algorithmes sont aussi utiles en eux-mêmes : qui n'a jamais rêvé de programmer son propre jeu ? Parmi les algorithmes que l'on rencontre le plus souvent, on retrouve bien évidemment le problème de plus court chemin à origine unique, sous un nom plus onirique : la recherche de chemin (ou path finding). On utilisera cependant plus généralement un algorithme plus rapide, mais qui ne donne pas toujours la solution optimale : A*, une extension de l'algorithme de Dijkstra.

IX. Références et remerciements

Ce cours se base essentiellement sur le cours oral de structures de données et algorithmes de Pierre Geurts (INFO0902), donné à l'ULg pendant l'année académique 2011-2012. Les livres Introduction to Algorithms (troisième édition) et Structures de données avancées avec la STL, première édition, de Philippe Gabrini ont été utilisés comme compléments occasionnels.

Merci à Kevin Vanaertenryck pour ses remarques sur le contenu et à Claude Leloup pour sa relecture orthographique !