Chapter 4

Algorithmes Gloutons (Voraces)

(Greedy)

Un algorithme glouton arrive à une solution en prenant une séquence de décisions, où chaque
décision est simplement la meilleure sur le moment.
Pour qu’un algorithme glouton soit correct, « localement optimal » doit se traduire par «
globalement optimal ».

4.1 Rendre la monnaie

Voici un problème simple qui est une bonne illustration du principe glouton.
Comment rendre un montant d’argent donné avec le moins de pièces possible ? (On suppose
qu’on a une quantité illimitée de pièces de chaque dénomination (!))

Algorithm RendreLaM onnaie(x)

1: P ieces = {5, 10, 25, 100, 200}
2: Somme = 0
3: while Somme →= x do
4: Soit c ↑ P ieces la plus grande dénomination telle que Somme + c ↓ x.
5: if une telle dénomination n’existe pas then
6: return « Pas de solution »
7: end if
8: Ajouter c à la monnaie à retourner.
9: Somme = Somme + c
10: end while

Je dois rendre 3,65$ au client. Je commence par prendre une pièce de deux dollars (*tooney*),

137
puis une pièce d’un dollar (*looney*), puis deux pièces de 25 cents (*quarters*), puis une
pièce de 10 cents (*dime*) et enfin une pièce de 5 cents (*nickel*).
Question : Dans la République d’Informatique, les seules dénominations disponibles sont 1,
4 et 6 cents. Est-ce que RendreLaM onnaie produit une solution optimale pour toutes les
entrées possibles ?
Alors pourquoi cela fonctionne-t-il pour les pièces canadiennes ? Voir l’exercice BLAH.

4.2 Le Problème du Sac à Dos [0,1]

Imaginons qu’on nous donne un ensemble d’objets et qu’on veuille remplir un sac (un sac
à dos) avec certains de ces objets. Notre but est de maximiser la valeur totale des objets
qu’on met dans notre sac, mais on ne peut pas transporter un poids total de plus de W .
Cependant, on a le droit de casser les objets en morceaux. Par exemple, si on veut mettre un
tiers d’un objet dans notre sac, on est autorisé à le faire. On se réfère parfois à ce problème
comme le Problème du Sac à Dos [0,1] ou le Problème du Sac à Dos Continu.
Formellement, on définit le problème comme suit.

INPUT:
• n objets tels que l’objet i (1 ↓ i ↓ n) a une valeur positive vi > 0 et un poids positif
wi > 0.
• Un poids maximum W .
OUTPUT: Un vecteur X = (x1 , x2 , ..., xn ) tel que
• 0 ↓ xi ↓ 1 pour tout 1 ↓ i ↓ n,
• le poids total n’est pas trop lourd :
n
!
xi wi = x1 w1 + x2 w2 + ... + xn wn ↓ W,
i=1

• la valeur totale n
!
xi vi = x1 v1 + x2 v2 + ... + xn vn
i=1

est maximisée.

Cela peut paraître e!rayant à première vue, mais c’est simplement une description mathé-
matique du paragraphe précédent.
La première contrainte 0 ↓ xi ↓ 1 qui doit être satisfaite par le résultat signifie qu’on a une
copie de l’objet i et qu’on peut en prendre n’importe quelle fraction 0 ↓ xi ↓ 1. Une solution
(x1 , x2 , ..., xn ) satisfaisant les deux premières contraintes (0 ↓ xi ↓ 1 et x1 w1 + x2 w2 + ... +
xn wn ↓ W ) est dite réalisable. Ce que ce problème demande, c’est de calculer la solution
réalisable qui a la valeur totale maximale.

138
Essayons de voir comment on peut utiliser un algorithme glouton pour résoudre ce problème.
Considérons l’exemple suivant où W = 100.

i 1 2 3 4 5
vi 20 30 66 40 60
wi 10 20 30 40 50

Puisqu’on veut maximiser la valeur totale, une approche raisonnable serait de faire des choix
gloutons par rapport aux valeurs. Dans ce cas, après avoir trié les objets en ordre décroissant
(par rapport aux valeurs), on obtient la solution réalisable suivante.

i 3 5 4 2 1
vi 66 60 40 30 20
wi 30 50 40 20 10

i xi Valeur totale Poids total

3 1 66 30
5 1 126 80
1
4 2
146 100

1
x1 = 0 x2 = 0 x3 = 1 x4 = x5 = 1
2
On obtient donc une valeur totale de 146 avec cette approche. Maintenant, la question est :
est-ce optimal ? Y a-t-il un moyen de trouver une solution réalisable avec une plus grande
valeur totale ?
Puisqu’on veut s’assurer que notre sac n’est pas trop lourd, une autre approche raisonnable
serait de prendre des décisions gloutonnes par rapport aux poids, c’est-à-dire qu’on veut
toujours choisir l’objet disponible le plus léger. Dans ce cas, après avoir trié les objets en
ordre croissant (par rapport aux poids), on obtient la solution réalisable suivante.

i 1 2 3 4 5
vi 20 30 66 40 60
wi 10 20 30 40 50

i xi Valeur totale Poids total

1 1 20 10
2 1 50 30
3 1 116 60
4 1 156 100

x1 = 1 x2 = 1 x3 = 1 x4 = 1 x5 = 0

139
Et on obtient une valeur totale de 156 avec cette approche, une solution réalisable avec une
plus grande valeur totale par rapport à la précédente ! Mais... cela ne garantit pas que
cette solution réalisable est optimale. Cependant, cela montre qu’en général, faire des choix
gloutons par rapport aux valeurs n’est pas la bonne approche.
Faisons un essai de plus. D’une certaine manière, ce qu’on veut faire, c’est maximiser la
valeur totale et minimiser le poids total. Alors pourquoi ne pas faire des choix gloutons par
rapport à la valeur par unité de poids ? Dans ce cas, après avoir trié les objets en ordre
décroissant (par rapport à la valeur par unité de poids), on obtient la solution réalisable
suivante.

i 3 1 2 5 4
vi 66 20 30 60 40
wi 30 10 20 50 40
vi
wi
2.2 2 1.5 1.2 1

i xi Valeur totale Poids total

3 1 66 30
1 1 86 40
2 1 116 60
4
5 5
164 100

4
x1 = 1 x2 = 1 x3 = 1 x4 = 0 x5 =
5
Cela mène à une solution réalisable avec une plus grande valeur totale ! Mais... cela ne
garantit pas que cette solution réalisable est optimale. Cependant, cela montre que la «
valeur » n’est pas le bon critère glouton et que le « poids » n’est pas le bon critère glouton.
Maintenant... peut-on faire mieux ? On va montrer que quelle que soit l’entrée, le critère
glouton de la valeur par unité de poids mène toujours à une solution optimale (référez-vous
au Lemme 8).
Voici donc l’algorithme qu’on a.

Algorithm SacADosContinu(v[1..n], w[1..n], W )

Input: Deux tableaux v[1..n] et w[1..n] tels que l’objet i a une valeur v[i] > 0 et un poids
w[i] > 0 (où 1 ↓ i ↓ n) ainsi qu’un poids maximum" W.
Output: Une solution réalisable x[1..n] qui maximise ni=1 x[i]v[i].
1: for i = 1 à n do
2: vw[i] = v[i]/w[i]
3: end for
4: Trier les objets en ordre décroissant par rapport à vw.
5: Construire le résultat en appliquant le critère glouton par rapport à la valeur par unité
de poids (en utilisant le tableau vw).

140
On doit maintenant répondre à deux questions : cet algorithme est-il correct ? Quel est son
temps de calcul ? Argumentons d’abord que cet algorithme est correct. On discutera ensuite
de son temps de calcul.
Lemma 8. Considérons n objets, où l’Objet i a une valeur vi > 0 et un poids wi > 0 (pour
1 ↓ i ↓ n). De plus, considérons un poids total W > 0. Alors SacADosContinu(v[1..n], w[1..n], W )
calcule une solution optimale au problème du sac à dos continu. En d’autres termes, si les
objets sont sélectionnés en ordre décroissant de valeur par unité de poids, alors la stratégie
gloutonne trouve une solution optimale.

Proof. On peut supposer sans perte de généralité que

v1 v2 v3 vn→1 vn
↔ ↔ ↔ ... ↔ ↔
w1 w2 w3 wn→1 wn
(sinon on renomme les objets). Par conséquent, SacADosContinu considère l’Objet 1, puis
l’Objet 2, puis l’Objet 3, etc. Soit X = (x1 , x2 , x3 , ..., xn→1 , xn ) la solution obtenue par
SacADosContinu.
Si xi = 1 pour tout 1 ↓ i ↓ n, alors la solution doit être optimale : on pourrait mettre
littéralement tous les objets dans notre sac ! Sinon, il existe un indice 1 ↓ j ↓ n tel que

x1 = 1, x2 = 1, ..., xj→1 = 1,

0 ↓ xj < 1,
xj+1 = 0, xj+2 = 0, ..., xn = 0.
En e!et, il y a un indice j tel que tous les objets de 1 à j ↗ 1 sont mis dans le sac, puis
éventuellement une fraction de l’Objet j est mise dans le sac, après quoi le sac est plein.
D’après la définition de SacADosContinu, on obtient
n
!
xi wi = W. (4.1)
i=1

Soit Y = (y1 , y2 , y3 ..., yn→1 , yn ) une solution réalisable arbitraire. En tant que telle, on a

0 ↓ yi ↓ 1 pour tout 1 ↓ i ↓ n, (4.2)

! n
yi wi ↓ W. (4.3)
i=1

En combinant (4.1) et (4.3), on trouve

n
!
(xi ↗ yi ) wi ↔ 0. (4.4)
i=1

141
On veut montrer que X est au moins aussi bonne que Y . Par conséquent, on veut montrer
que
!n n
!
x i vi ↔ yi vi .
i=1 i=1

On a
n
! n
!
xi vi ↗ yi vi
i=1 i=1
!n
= (xi ↗ yi ) vi
i=1
!n
wi
= (xi ↗ yi ) vi
i=1
wi
n
! vi
= (xi ↗ yi ) wi
i=1
wi
j→1 n
! vi vj ! vi
= (xi ↗ yi ) wi + (xj ↗ yj ) wj + (xi ↗ yi ) wi . (4.5)
i=1
wi wj i=j+1 wi

Concentrons-nous sur le terme de la première sommation dans (4.5). Pour tout 1 ↓ i ↓ j ↗1,
on a

xi ↗ yi = 1 ↗ yi ↔ 0 (4.6)

par (4.2). De plus, puisque les vi

wi
sont en ordre décroissant, on a
vi vj
↔ (4.7)
wi wj
pour tout 1 ↓ i ↓ j ↗ 1. En combinant (4.6) et (4.7) (et en multipliant des deux côtés par
wi ), on trouve
vi vj
(xi ↗ yi ) wi ↔ (xi ↗ yi ) wi . (4.8)
wi wj

Regardons maintenant le terme de la deuxième sommation dans (4.5). Pour tout j + 1 ↓

i ↓ n, on a

xi ↗ yi = 0 ↗ yi ↓ 0 (4.9)

par (4.2). De plus, puisque les vi

wi
sont en ordre décroissant, on a
vi vj
↓ (4.10)
wi wj

142
pour tout j + 1 ↓ i ↓ n. En combinant (4.9) et (4.10) (et en multipliant des deux côtés par
wi ), on trouve
vi vj
(xi ↗ yi ) wi ↔ (xi ↗ yi ) wi . (4.11)
wi wj

Par conséquent, on obtient

n
! n
!
xi vi ↗ yi vi
i=1 i=1
j→1 n
! vi vj ! vi
= (xi ↗ yi ) wi + (xj ↗ yj ) wj + (xi ↗ yi ) wi par (4.5),
i=1
wi wj i=j+1 wi
j→1 n
! vj vj ! vj
↔ (xi ↗ yi ) wi + (xj ↗ yj ) wj + (xi ↗ yi ) wi par (4.8) et (4.11),
i=1
wj wj i=j+1 wj
! n
vj
= (xi ↗ yi ) wi
i=1
wj
n
vj !
= (xi ↗ yi ) wi
wj i=1
↔0

par (4.4), et puisque vj > 0 et wj > 0.

Par conséquent, pour toute solution réalisable Y , on a
n
! n
!
x i vi ↔ yi vi .
i=1 i=1

En d’autres termes, X est optimale.

On sait maintenant que cette approche gloutonne est correcte. La question suivante est :
quel est le temps de calcul de SacADosContinu ? Combien de temps cela prend-il ?
• Le calcul des valeurs par unité de poids prend un temps de O(n).
• Le tri prend un temps de O(n log(n)) en utilisant le tri fusion.
• Et ensuite la construction de la solution optimale prend un temps de O(n).
Donc au total, SacADosContinu prend un temps de O(n)+O(n log(n))+O(n) = O(n log(n)).
Maintenant, qu’en pensez-vous ? Existe-t-il un algorithme plus rapide ? Quand on y pense,
lorsqu’on construit la solution, ce qu’on a « réellement » besoin de découvrir, c’est cet indice
j (référez-vous à la preuve du Lemme 8). Si on pouvait déterminer quel est cet indice j,

143
alors on pourrait simplement parcourir les objets et rejeter tous ceux pour lesquels la valeur
par unité de poids est inférieure à celle de l’Objet j. Ensuite, on pourrait remplir notre sac.
En d’autres termes, connaître l’indice j nous permettrait de trouver une solution optimale
en temps O(n). Peut-on trouver j en temps O(n) ? Cela ressemble beaucoup au calcul
du k-ième plus petit élément pour une certaine valeur de k. Le défi est le suivant. Dans
l’algorithme de sélection, on doit donner le rang en entrée. Ici, on est en fait à la recherche
du rang. Supposons un instant qu’on connaisse l’ordre
v1 v2 vn
↔ ↔ ... ↔
w1 w2 wn
(comme dans la preuve du Lemme 8). Alors on cherche l’indice j tel que w1 +w2 +...+wj→1 <
W et w1 +w2 +...+wj→1 +wj ↔ W . Mais bien sûr, on ne connaît pas l’ordre. Pour trouver cet
indice j, on a besoin de ce qu’on appelle l’algorithme de sélection pondérée. Cet algorithme
prend également un temps de O(n) et l’approche est très similaire à celle de la Sélection
(référez-vous à la Section 2.5). Donc en utilisant la sélection pondérée, on peut résoudre
le problème du sac à dos continu en O(n). Maintenant : comment fonctionne la sélection
pondérée ? On ne présentera pas les détails ici, peut-être dans la prochaine édition de ces
notes. :-)
Voici une autre question intéressante. Que fait-on si la solution (x1 , x2 , x3 , ..., xn→1 , xn ) doit
satisfaire xi ↑ {0, 1} au lieu de xi ↑ [0, 1] ? En d’autres termes, que se passe-t-il si on n’est
pas autorisé à casser les objets en morceaux ? Pour chaque 1 ↓ i ↓ n, soit on met l’Objet
i dans le sac, soit on ne le met pas. C’est la version discrète du problème du sac à dos. On
peut montrer que l’approche gloutonne ne fonctionne pas dans ce cas, mais en utilisant ce
qu’on appelle la programmation dynamique, on peut le résoudre (référez-vous au Chapitre 5)
!

4.3 Arbres Couvrants de Poids Minimum

Considérons un graphe G = (V, E) non orienté, pondéré et connexe. Un arbre couvrant T
de G est un sous-graphe de G tel que T est un arbre dont l’ensemble de sommets est V
(référez-vous à CSI-2101). Un arbre couvrant de poids minimum (ACPM) de G est un arbre
couvrant de G dont le poids total est minimum (référez-vous à CSI-2110). Voici un exemple
de graphe non orienté pondéré G avec un ACPM de G (en bleu).

B 8 C 7 D

4 9
2
11 J 4 14
A E

7 6 10
8

H 1 G 2 F

144
Observez qu’un graphe peut avoir plusieurs ACPM di!érents. Par exemple, dans l’exemple
précédent, on pourrait remplacer l’arête {B, C} par l’arête {A, H} et on obtiendrait toujours
un arbre couvrant de poids minimum. Dans cette section, on étudie le problème suivant.

INPUT: Un graphe G = (V, E) non orienté, pondéré et connexe.

OUTPUT: Un arbre couvrant de poids minimum de G. Le résultat doit être une liste
contenant les arêtes de l’ACPM.

Dans cette section, on suppose que tout arbre couvrant de poids minimum T
retourné par un algorithme d’ACPM est stocké dans une liste contenant les
arêtes de T (dans un ordre arbitraire).
On va étudier deux algorithmes d’arbre couvrant de poids minimum : Kruskal (référez-vous
à la Sous-section 4.3.1) et Prim (référez-vous à la Sous-section 4.3.2). Les deux algorithmes
sont des algorithmes gloutons et ils sont tous deux basés sur le lemme suivant.
Lemma 9. Soit G = (V, E) un graphe non orienté et connexe, où chaque arête {u, v} ↑ E a
un poids wt(u, v). On divise V en A et B. Soit {u, v} ↑ E une arête la plus légère connectant
A et B.

u B

Alors il existe un ACPM de G qui contient {u, v}.

Proof. Soit T un ACPM de G. Si T contient déjà {u, v}, on a terminé !

Supposons que T ne contient pas {u, v}. Puisque T est connexe, il y a un chemin entre u et
v dans T qui contient une arête {a, b}, où a ↑ A et b ↑ B.

A a T b

u B

145
Considérons T ↑ = T ↘ {a, b} ≃ {u, v}. Par construction, T ↑ est connexe et l’ensemble de
sommets de T ↑ est V . De plus, on a

wt(T ) ↓ wt(T ↑ ) puisque T est un ACPM,

= wt(T ) ↗ wt({a, b}) + wt({u, v})
↓ wt(T ),

où la dernière inégalité découle du fait que {u, v} est une arête la plus légère connectant A
et B, c’est-à-dire qu’on doit avoir wt({u, v}) ↓ wt({a, b}). Par conséquent, wt(T ↑ ) = wt(T ).
Puisque le poids de T ↑ est le même que le poids d’un ACPM, et puisque T ↑ est un arbre
couvrant, alors T ↑ est un ACPM. De plus, T ↑ contient {u, v}.
D’après le lemme précédent, tout algorithme qui suit le schéma glouton suivant est garanti
de fonctionner :
• X=⊋ // arêtes choisies jusqu’à présent
• Répéter jusqu’à ce que |X| = |V | ↗ 1
– Choisir un ensemble S tel que X n’ait aucune arête entre S et V \ S.
– Soit e ↑ E une arête de poids minimum entre S et V \ S.
– X = X ⇐ {e}

4.3.1 Algorithme de Kruskal (1956)

Le premier algorithme d’ACPM qu’on étudie est l’algorithme de Kruskal. L’idée générale
derrière cet algorithme est la suivante. On veut maintenir une forêt. À chaque étape, le but
est d’ajouter une arête de poids minimum qui ne crée pas de cycle. Ainsi, on trie d’abord les
arêtes par ordre croissant de poids. On considère ensuite les arêtes dans l’ordre, de la plus
légère à la plus lourde.
Au début, chaque sommet est un arbre (trivial).

À chaque itération, on combine deux arbres en utilisant une arête de poids minimum.

edge of
minimum weight

146
Considérons l’exemple suivant.

6 5
A C E
4
5 2 3 4
1
B 2 D 4 F

On commence par trier les arêtes par poids :

BC, BD, CD, CF, AD, DF, EF, AB, CE, AC.

Puis on insère les arêtes, une par une, par ordre croissant de poids, tant qu’aucun cycle n’est
créé.

6 5 6 5
A C E A C E
4 4
5 2 3 4 5 2 3 4
1 1
B 2 D 4 F B 2 D 4 F

En suivant l’ordre des arêtes, on a d’abord inséré BC. Ensuite, on insère BD. On n’insérera
pas CD sinon cela créerait le cycle B, C, D, B. Et on continue à parcourir la liste.

6 5 6 5
A C E A C E
4 4
5 2 3 4 5 2 3 4
1 1
B 2 D 4 F B 2 D 4 F

6 5 6 5
A C E A C E
4 4
5 2 3 4 5 2 3 4
1 1
B 2 D 4 F B 2 D 4 F

On obtient un arbre couvrant de poids minimum avec un poids total de 14.

Quel est le temps de calcul d’une telle approche ? Trier les arêtes au début peut être
fait e"cacement en utilisant le tri fusion. Comment vérifie-t-on (e"cacement) si l’insertion
d’une arête va créer un cycle ou non ? On a besoin d’une astuce qui peut être exécutée
e"cacement puisqu’on va vérifier chaque arête. L’astuce consiste à utiliser la structure de
données suivante.

147
À propos de la structure de données Union-Find On ouvre une parenthèse et on
étudie une structure de données appelée Union-Find.

(
On nous donne les n singletons suivants
A1 = {1}, A2 = {2}, ··· An = {n}.
On veut traiter une séquence d’opérations, où chaque opération est soit Union soit Find,
où
Union(A, B, C) : Définit
C = A ⇐ B,
A = ⊋,
B = ⊋.

Find(x) : Retourne le nom de l’ensemble qui contient x

La séquence d’opérations qu’on veut traiter se compose de
• n ↗ 1 opérations Union,
• m opérations Find,
qui peuvent être e!ectuées dans n’importe quel ordre.
Voici une solution possible. Stocker chaque ensemble dans une liste.
• La liste a un pointeur vers la tête et un pointeur vers la queue.
• Le premier nœud stocke le nom de l’ensemble.
• Chaque autre nœud stocke un élément de l’ensemble.
• Chaque nœud u stocke deux pointeurs :
– next(u) le nœud suivant dans la liste,
– back(u) le premier nœud de la liste.
Par exemple, voici la représentation de l’ensemble A = {1, 4, 5, 7, 9} avec cette structure de
données.

148
 tail

head
A 5 9 1 4 7

Au début, c’est-à-dire avant de commencer à traiter la séquence d’opérations, chaque ensem-

ble Ai (pour un certain 1 ↓ i ↓ n) ressemble à ceci.

Ai i

Soit A un ensemble de taille k et B un ensemble de taille ω. On peut alors e!ectuer l’opération

Union(A, B, C) de la manière suivante. On ajoute la liste B à la fin de la liste A, on e!ectue
quelques opérations de base sur les pointeurs, puis on change le nom dans la tête de la nouvelle
liste de A à C.

A a1 a2 ··· ak

B b1 b2 ··· b`

C a1 ··· ak b1 ··· b`

On a besoin d’e!ectuer environ ω opérations de base sur les pointeurs. Le temps de calcul
pour cette opération est alors de O(ω) = O(taille de B).

Pour e!ectuer l’opération Find(x), on suit simplement le pointeur ‘back‘ depuis le nœud
stockant x jusqu’à la tête de la liste et on retourne le nom stocké à la tête. Cela prend un
temps de O(1).

Quelle est l’e"cacité de cette solution ? Voici une séquence de n ↗ 1 opérations Union (dans
cet exemple, on ne se préoccupe pas de considérer les m opérations Find).

149
 Union Temps de calcul

{2}, {1} 1
{3}, {2, 1} 2
{4}, {3, 2, 1} 3
.. ..
. .
{n}, {n ↗ 1, n ↗ 2, ..., 2, 1} n↗1

Et le temps de calcul total pour cette séquence d’opérations est de 1+2+3+...+n↗1 = O(n2 ).
Voici une meilleure solution : pour chaque liste, la tête stocke
• le nom de l’ensemble
• la taille de l’ensemble
L’opération Find prend un temps de O(1), comme auparavant.
Quant à l’opération Union, voici comment on e!ectue Union(A, B, C). Si |A| ↔ |B|, on
met B à la fin.

C
list for A list for B
|A| + |B|

Si |A| < |B|, on met A à la fin.

C
list for B list for A
|A| + |B|

Le temps de calcul de Union(A, B, C) devient alors

O(min{|A|, |B|}) = O(nombre de pointeurs ‘back‘ qui sont modifiés).

Quel est le temps de calcul total pour une séquence de n ↗ 1 opérations Union ?

Temps de calcul total = nombre total de changements de pointeurs ‘back‘

!n
= nombre total de fois que back(x) est changé
x=1

Considérons un élément x. Combien de fois change-t-on back(x) ?

150
 • Au début, x est dans un ensemble de taille 1.

• Première fois que back(x) est changé :

l’ensemble contenant x est fusionné avec un ensemble de taille ↔ 1.

Par conséquent, le nouvel ensemble contenant x a une taille ↔ 2.

• Deuxième fois que back(x) est changé :

l’ensemble contenant x est fusionné avec un ensemble de taille ↔ 2.

Par conséquent, le nouvel ensemble contenant x a une taille ↔ 4.

• Troisième fois que back(x) est changé :

l’ensemble contenant x est fusionné avec un ensemble de taille ↔ 4.

Par conséquent, le nouvel ensemble contenant x a une taille ↔ 8.

• etc.

Combien de fois peut-on doubler la taille de l’ensemble contenant x ? Puisqu’il y a n éléments

au total, la réponse est : au plus log2 (n) fois ! Par conséquent, back(x) est changé au plus
log2 (n) fois. Puisque c’est vrai pour tous les éléments x, le temps de calcul total pour n ↗ 1
opérations Union est de O(n log(n)). Conclusion : Toute séquence de n ↗ 1 opérations
Union et m opérations Find prend un temps de O(m + n log(n)).

)
Comment va-t-on utiliser la structure de données Union-Find dans Kruskal ? Au début,
chaque Ai contient le sommet i (ou vi ). Chaque fois qu’on veut ajouter une arête entre
deux sommets vi et vj , on utilise d’abord l’opération Find pour voir si vi et vj appartiennent
déjà au même arbre. Si c’est le cas, ajouter une arête créerait un cycle, donc on passe.
Si vi et vj n’appartiennent pas au même arbre, alors on ajoute une arête entre eux et on
e!ectue l’opération Union entre l’ensemble contenant vi et l’ensemble contenant vj . On
obtient l’algorithme suivant.

151
Algorithm Kruskal(G)
Input: Un graphe G = (V, E) non orienté, pondéré et connexe, où V = {x1 , x2 , ..., xn } et
m = |E|.
Output: Un arbre couvrant de poids minimum de G (stocké comme une liste de ses arêtes).

1: Trier les arêtes de E par poids en utilisant le tri fusion : e1 , e2 , ..., em

2: for i = 1 à n do
3: Vi = {xi }
4: end for
5: T =⊋
6: for k = 1 à m do
7: soit uk et vk les sommets de ek .
8: soit i l’indice tel que uk ↑ Vi
9: soit j l’indice tel que vk ↑ Vj
10: if i →= j then
11: Vi = Vi ⇐ Vj
12: Vj = ⊋
13: T = T ⇐ {{uk , vk }}
14: end if
15: end for
16: return T

Analysons maintenant le temps de calcul de Kruskal.

• L’étape de tri prend

O(m log(m)) = O(m log(n2 )) = O(2m log(n)) = O(m log(n))

#n $ n(n→1)
de temps puisque pour tous les graphes non orientés, on a m ↓ 2
= 2
= O(n2 ).
• La première boucle for prend un temps de O(n).
• Analysons maintenant la deuxième boucle for.
– On stocke T dans une liste chaînée. On l’initialise comme la liste vide. Ensuite,
on insère un total de n ↗ 1 arêtes à la liste1 . Par conséquent, le temps total pour
maintenir cette liste est de O(n).
– On stocke les ensembles Vi en utilisant la structure de données Union-Find définie
ci-dessus.
Au total, dans cette deuxième boucle for, on fait
– au plus 2m opérations Find (une pour chaque sommet de chaque arête),
1
De CSI-2101, on sait qu’un arbre sur n sommets a n ↗ 1 arêtes.

152
 – n ↗ 1 opérations Union (parce qu’on insère exactement n ↗ 1 arêtes à l’arbre).
Donc au total, la deuxième boucle for prend

O(n) + 2m + n log(n) = O(m + n log(n))

de temps.
Finalement, le temps de calcul total de Kruskal est

O(m log(n)) + O(n) + O(m + n log(n)) = O(m log(n) + n + m + n log(n)) = O(m log(n)).

Dans cette dernière dérivation, on a utilisé l’inégalité n ↓ m + 1. Pourquoi cette inégalité

est-elle vraie ? Rappelez-vous que l’entrée du problème de l’ACPM est un graphe connexe.
Par conséquent, on a n ↓ m + 1 (référez-vous à CSI-2101).

4.3.2 Algorithme de Prim (1957) [Jarník (1930), Dijkstra (1959)]

L’approche générale pour l’algorithme de Prim est la suivante.
• Au début,
– A est un ensemble constitué d’exactement un sommet (arbitraire) de V .
– Q = V \ A.
– T est une liste vide d’arêtes.
A

Q=V \A

• À chaque itération, on fait ce qui suit.

– Prendre une arête {u, v} de poids minimum telle que u ↑ A et v ↑ Q.
– Ajouter l’arête {u, v} à T .
– Déplacer v de Q à A.
A
u
v Q=V \A

Répéter jusqu’à ce que A = V (ou de manière équivalente, jusqu’à ce que Q = { }).

Considérons l’exemple suivant.

153
 6 5
A C E
4
5 2 3 4
1
B 2 D 4 F

Pour la trace de l’algorithme de Prim, on doit choisir avec quel sommet commencer. Com-
mençons par le sommet A. On obtient alors la trace suivante.

6 5 6 5
A C E A C E
4 4
5 2 3 4 5 2 3 4
1 1
B 2 D 4 F B 2 D 4 F

6 5 6 5
A C E A C E
4 4
5 2 3 4 5 2 3 4
1 1
B 2 D 4 F B 2 D 4 F

6 5 6 5
A C E A C E
4 4
5 2 3 4 5 2 3 4
1 1
B 2 D 4 F B 2 D 4 F

On obtient un arbre couvrant de poids minimum avec un poids total de 14.

Une di!érence majeure entre Kruskal et Prim est qu’avec Kruskal, on maintient une forêt,
mais avec Prim, on maintient un arbre. On obtient le pseudo-code suivant.

154
Algorithm P rim(G)
Input: Un graphe G = (V, E) non orienté, pondéré et connexe.
Output: Un arbre couvrant de poids minimum de G (stocké comme une liste de ses arêtes).

1: Soit r ↑ V un sommet arbitraire.

2: A = {r}
3: T ={}
4: while A →= V do
5: trouver une arête {u, v} ↑ E de poids minimum telle que u ↑ A et v ↑ V \ A.
6: A = A ⇐ {v}
7: T = T ⇐ {{u, v}}
8: end while
9: return T

Comment peut-on exécuter la Ligne 5 e"cacement ? Comment doit-on procéder pour trouver
une telle arête {u, v} ? Si on utilise la force brute, alors cela prend un temps de O(|E|) au
total pour toute la boucle while. Donc le temps de calcul total de l’algorithme devient
O(|V | · |E|). Comparé à Kruskal, ce n’est pas très impressionnant.
Pour améliorer le temps de calcul, on va maintenir des informations supplémentaires et on
va utiliser des structures de données « plus intelligentes ». Pour chaque sommet y dans Q,
on définit

poidsmin(y) : poids minimum de toute arête entre y et un sommet de A,

plusproche(y) : sommet x dans A pour lequel wt(x, y) = poidsmin(y).

A
x
y Q=V \A

Observez que par définition, une arête la plus légère {u, v} connectant A et Q a un poids de
% &
min poidsmin(y) .
y↓Q

Disons que dans Q, les voisins de v sont x, y et z.

A z
u
y Q=V \A
v
x

Que se passe-t-il si on déplace v de Q à A ? On doit mettre à jour poidsmin(w) et

plusproche(w) pour tout w ↑ {x, y, z}.

155
 A z
u
y Q=V \A
v
x

Le pseudo-code de l’algorithme de Prim devient alors ceci.

Algorithm P rim(G)
Input: Un graphe G = (V, E) non orienté, pondéré et connexe.
Output: Un arbre couvrant de poids minimum de G (stocké comme une liste de ses arêtes).

1: Soit r ↑ V un sommet arbitraire

2: A = {r}
3: T ={}
4: for chaque sommet y →= r do
5: poidsmin(y) = ⇒
6: plusproche(y) = nil
7: end for
8: for chaque arête {r, y} do
9: poidsmin(y) = wt(r, y)
10: plusproche(y) = r
11: end for
12: Q = V \ {r}
13: k=1 // Stocke la taille de A
14: while k →= n do
15: Soit v le sommet de Q pour lequel poidsmin(v) est minimum
16: u = plusproche(v)
17: A = A ⇐ {v}
18: Q = Q \ {v}
19: T = T ⇐ {{u, v}}
20: k =k+1
21: for chaque arête {v, y} do
22: if y ↑ Q et wt(v, y) < poidsmin(y) then
23: poidsmin(y) = wt(v, y)
24: plusproche(y) = v
25: end if
26: end for
27: end while
28: return T

Quel est le temps de calcul de cette version mise à jour de Prim ? Clarifions d’abord quelles
structures de données on utilise.

156
 • On stocke les sommets de Q dans un tas-min. Pour chaque sommet v ↑ Q, la clé de v
est poidsmin(v).
• On stocke T dans une liste.
• Avec chaque sommet de V , on stocke un bit indiquant si le sommet appartient à A ou
à Q.
On peut maintenant analyser le temps de calcul.
• Jusqu’à la boucle while, cela prend un temps de O(n) (cela inclut le temps pour
construire le tas).
• À chaque itération de la boucle while, on fait
– une opération extraire_min une fois, ce qui prend un temps de O(log(n))
– et au plus deg(v) opérations diminuer_cle, ce qui prend un temps de O(deg(v) ·
log(n)).
• Par conséquent, le temps total pour la boucle while est
' (
!
O deg(v) · log(n) = O(2m log(n)) = O(m log(n)).
v↓V

En conclusion, le temps de calcul total pour l’algorithme de Prim est

O(n) + O(m log(n)) = O(m log(n)).

157