Structures de donnéesIFT-2000

Abder AlikacemAbder Alikacem

Arbres de recouvrement minimum

Département d’informatique et de génie logiciel

Édition Septembre 2009

JFK

BOS

MIA

ORD

LAXDFW

SFO BWI

PVD

8672704

187

1258

849

144740

1391

184

946

1090

1121

2342

1846 621

802

1464

1235

337

Définitions L’algorithme de Prim-JarnikAlgorithme de Kruskal

Plan

Définitions

Un sous-graphe couvrant d’un graphe G est un sous-graphe contenant tous les sommets

de G.

Un arbre couvrant d’un graphe est un sousgraphe couvrant qui est un arbre.

Arbre couvrant minimal (minimum spanning tree):

Arbre couvrant d’un graphe avec poids dont le poids total des arêtes est minimal.

ORD

PIT

ATL

STL

DEN

DFW

DCA

101

9

8

6

3

25

7

4

Propriétés

Propriété de cycle: Soit T un arbre couvrant d’un

graphe avec poids G Soit e une arête de G

n’appartenant pas à T et soit C, le cycle obtenu

lorsqu’on ajoute e à T Si T est minimal, alors on a

pour toutes arêtes f dans C poids(f) poids (e)

Preuve: Par contradiction Si poids(f) > poids(e), on

obtient un arbre couvrant de plus petit poids en remplaçant

l’arête f par l’arête e dans notre arbre T

84

2 36

7

7

9

8e

C

f

84

2 36

7

7

9

8

C

e

f

Remplacer f par e donne un arbrecouvrant de plus petit poids total

U V

Propriété de partition des ACM

Propriétés de partition: Considérons une partition des

sommets de G en deux ensembles U et V

Soit e une arête de poids minimal entre U et V

Alors, il existe un arbre couvrant minimal de G contenant e

Preuve: Soit T un arbre couvrant minimal

de G Si T ne contient pas e, soit C le

cycle formé par l’addition de e à l’arbre T et soit f, une arête entre U et V

Par la propriété de cycles, on a,poids(f)

poids(e) Comme on avait pris e de poids

minimal, on a que poids(f) = poids(e) et alors on obtient un autre ACM en remplaçant f par e

74

2 85

7

3

9

8 e

f

74

2 85

7

3

9

8 e

f

Remplacer f par e nousdonne un autre ACM

U V

Algorithme de Prim-Jarnik’s

Algorithme similaire à l”algorithme de Dijkstra (dans le cas des graphes connexes).On choisit un sommet s aléatoirement qu’on met dans un “nuage” et on

construit l’arbre couvrant minimal en faisant grossir le “nuage” d’un

sommet à la fois.On garde en mémoire à chaque sommet v, une étiquette d(v) qui ici est égale au poids minimal parmi les poids des arêtes reliant v à un sommet à l’intérieur du nuage.À chaque étape:

On ajoute au nuage le sommet u extérieur ayant la plus petite étiquette d(u)

On met à jour les étiquettes des sommets adjacents à u

Algorithme de Prim-Jarnik’s

A priority queue stores the vertices outside the cloud

Key: distance Element: vertex

Locator-based methods insert(k,e) returns a

locator replaceKey(l,k)

changes the key of an item

We store three labels with each vertex:

Distance Parent edge in MST Locator in priority

queue

Algorithm PrimJarnikMST(G)Q new heap-based priority queues a vertex of Gfor all v G.vertices()

if v ssetDistance(v, 0)

else setDistance(v, )

setParent(v, )l Q.insert(getDistance(v), v)

setLocator(v,l)while Q.isEmpty()

u Q.removeMin() for all e G.incidentEdges(u)

z G.opposite(u,e)r weight(e)if r getDistance(z)

setDistance(z,r)setParent(z,e)

Q.replaceKey(getLocator(z),r)

Exemple

BD

C

A

F

E

74

28

5

7

3

9

8

07

2

8

BD

C

A

F

E

74

28

5

7

3

9

8

07

2

5

7

BD

C

A

F

E

74

28

5

7

3

9

8

07

2

5

7

BD

C

A

F

E

74

28

5

7

3

9

8

07

2

5 4

7

BD

C

A

F

E

74

28

5

7

3

9

8

03

2

5 4

7

BD

C

A

F

E

74

28

5

7

3

9

8

03

2

5 4

7

Exemple..suite

Analyse de la complexité

Opérations sur les graphes: On appelle l’opération Incidentes(v) une fois pour chaque sommet v. Donc,

temps total si on utilise une liste d’adjacence de O(m)

Étiquettage: On peut changer l’étiquette D(u) d’un sommet u jusqu’à O(deg(u)) fois.

Donc, au total, l’étiquettage prend un temps O(m)

Opérations de liste avec priorités Chaque sommet est inséré une fois dans la liste et retiré une fois. Chaque

insertion et suppresion prend un temps O(log n). Total O(n log n) La clé de chaque sommet u est modifiée au plus O(deg(u)) et prend un

temps O(log n) chaque fois. Total O(m log n)

La complexité en temps de Prim-Jarník est donc de O((n+m) log n)ou O(m log n) si le graphe est simple et connexe

Kruskal’s Algorithm

A priority queue stores the edges outside the cloud

Key: weight Element: edge

At the end of the algorithm

We are left with one cloud that encompasses the MST

A tree T which is our MST

Algorithm KruskalMST(G)for each vertex V in G do

define a Cloud(v) of {v}let Q be a priority queue.Insert all edges into Q using

their weights as the keyT while T has fewer than n-1

edges do edge e = T.removeMin()

Let u, v be the endpoints of eif Cloud(v) Cloud(u) then

Add edge e to TMerge Cloud(v) and

Cloud(u)return T

Structure de données pour Kruskal

L’algorithme maintient une forêt d’arbresUne arête est acceptée, si elle relit deux arbres distinctsOn a besoin d’une structure de données qui maintient une partition i.e une collection d’ensembles disjoints, avec les opérations

Trouver(u): retourne l’ensemble contenant u Union(u,v): remplace les ensemblescontenant u et v par

leur union

Représentation d’une Partition

Chaque élément d’un ensemble est mis enmémoire dans une séquence (l’ensemblepointe vers la séquence contenant ceséléments).

Chaque élément à un pointeur vers l’ensemble L’opération trouver(u) se fait en O(1) et retourne

l’ensemble dont u fait partie Pour l’opération union(u,v), on bouge les éléments du

plus petit ensemble dans la séquence du plus grand ensemble et on met à jour leur pointeur

La complexité en temps de union(u,v), est min(nu, nv) où nu est la taille de l’ensemble contenant u et nv, la taille de l’ensemble contenant v

Kruskal - partition

Algorithme Kruskal(G):Entrée: un graphe avec poids G.Sortie: Un ACM T pour G.Soit P une partition des sommets de G, où chaque sommet est dans un ensemble séparé.Soit Q une liste avec priorités gardant en mémoire les arêtes de G, ordonnéesselon leur poidsSoit T un arbre initialement videTant que Q n’est pas vide faire

(u,v) Q.enleverMin()si P.trouver(u) != P.trouver(v) alors

Ajouter (u,v) à TP.union(u,v)

retourner T

Complexité en temps:O((n+m)log n)

Exemple Kruskal

JFK

BOS

MIA

ORD

LAXDFW

SFO BWI

PVD

8672704

187

1258

849

144740

1391

184

946

1090

1121

2342

1846 621

802

1464

1235

337

JFK

BOS

MIA

ORD

LAXDFW

SFO BWI

PVD

8672704

187

1258

849

144740

1391

184

946

1090

1121

2342

1846 621

802

1464

1235

337

Exemple Kruskal

JFK

BOS

MIA

ORD

LAXDFW

SFO BWI

PVD

8672704

187

1258

849

144740

1391

184

946

1090

1121

2342

1846 621

802

1464

1235

337

Exemple Kruskal

JFK

BOS

MIA

ORD

LAXDFW

SFO BWI

PVD

8672704

187

1258

849

144740

1391

184

946

1090

1121

2342

1846 621

802

1464

1235

337

Exemple Kruskal

JFK

BOS

MIA

ORD

LAXDFW

SFO BWI

PVD

8672704

187

1258

849

144740

1391

184

946

1090

1121

2342

1846 621

802

1464

1235

337

Exemple Kruskal

JFK

BOS

MIA

ORD

LAXDFW

SFO BWI

PVD

8672704

187

1258

849

144740

1391

184

946

1090

1121

2342

1846 621

802

1464

1235

337

Exemple Kruskal

JFK

BOS

MIA

ORD

LAXDFW

SFO BWI

PVD

8672704

187

1258

849

144740

1391

184

946

1090

1121

2342

1846 621

802

1464

1235

337

Exemple Kruskal

JFK

BOS

MIA

ORD

LAXDFW

SFO BWI

PVD

8672704

187

1258

849

144740

1391

184

946

1090

1121

2342

1846 621

802

1464

1235

337

Exemple Kruskal

JFK

BOS

MIA

ORD

LAXDFW

SFO BWI

PVD

8672704

187

1258

849

144740

1391

184

946

1090

1121

2342

1846 621

802

1464

1235

337

Exemple Kruskal

JFK

BOS

MIA

ORD

LAXDFW

SFO BWI

PVD

8672704

187

1258

849

144740

1391

184

946

1090

1121

2342

1846 621

802

1464

1235

337

Exemple Kruskal

JFK

BOS

MIA

ORD

LAXDFW

SFO BWI

PVD

8672704

187

1258

849

144740

1391

184

946

1090

1121

2342

1846 621

802

1464

1235

337

Exemple Kruskal

JFK

BOS

MIA

ORD

LAXDFW

SFO BWI

PVD

8672704

187

1258

849

144740

1391

184

946

1090

1121

2342

1846 621

802

1464

1235

337

Exemple Kruskal

JFK

BOS

MIA

ORD

LAXDFW

SFO BWI

PVD

8672704

187

1258

849

144740

1391

184

946

1090

1121

2342

1846 621

802

1464

1235

337

Exemple Kruskal

JFK

BOS

MIA

ORD

LAXDFW

SFO BWI

PVD

8672704

187

1258

849

144740

1391

184

946

1090

1121

2342

1846 621

802

1464

1235

337

Exemple Kruskal