Université du Québec

École de technologie supérieure

Département de génie logiciel et des TI

LOG-320
Structures de données et algorithmes
Structures de données IV
Graphes
 Plan du cours
Exercices sur le dernier cours
Graphes
• Définitions
• Types de parcours
Exercices
• Préparation pour l’intra

2
 Exercice 2
Supprimer les nœuds R-E-D-S de l’arbre suivant:

E U

C O S X

B D S

3
 Exercice 1 (suite)
Supprimer les nœuds R-E-D-S de l’arbre obtenu
Règle 4, cas #1: Frère rouge
Règle #1: Nœud est une feuille rouge - Changement de couleur, parent devient rouge, frère devient noir
-Le nœud est simplement enlevé -Appliquer une rotation de telle sorte qu’un nœud noir devienne le
Règle #2: Le nœud à un seul enfant nouveau frère.
-Appliquer la bonne règle pour un frère noir
-Le nœud est remplacé par son enfant et il Règle 4, cas#2: Frère et enfants du frère noirs
devient noir. -frère devient rouge
Règle #3: Le nœud à deux enfants -parent devient noir ou double noir
-Le nœud est remplacé par son prédécesseur -Si le parent devient un double noir, poursuivre le processus à du
Si le prédécesseur est rouge, celui-ci est partir du parent
simplement éliminé Règle 4, cas#3: Frère noir mais enfant gauche du frère est rouge et
Si le prédécesseur à un seul enfant, la règle #2 enfant droit noir (+ cas symétrique)
x
-Frère devient rouge, enfant gauche devient noir
est appliquée -Appliquer une rotation droite sur le nœud frère
y
Sinon, il faut passer à la règle 4 -Devient le cas #4
z
Règle #4: Le nœud est une feuille noire ou le
prédécesseur est une feuille noire Règle 4 cas #4: Frère noir mais enfant droit du frère est
-Pour x, il faut le remplacer par un pointeur rouge(+cas symétrique) x
NULL qui devient un double noir -Enfant droit du frère devient noir
-Frère devient la couleur du parent y
-Parent devient noir
-Appliquer une rotation gauche sur le parent
z
du nœud double noir
4
Structures de données

GRAPHES

5
 Introduction aux graphes
Définition
• Un graphe est défini par G = (V,E) où:
• V est un ensemble de nœuds
• E est un ensemble de transitions entre les noeuds

V1 V2

V={V1, V2, V3, V4, V5 }

V5 E={(V1,V2), (V1,V3), (V2,V4) ,(V2,V5) ,(V3,V4) ,(V4,V5) }
V3 V4

6
 Introduction aux graphes
Type de graphes
• Orienté : une transition (u,v) permet une
transition de u à v seulement.
• Non-orienté: une transition (u,v) permet une
transition de u à v et de v à u.

V1 V2 V1 V2

V5 V5

V3 V4 V3 V4

Graphe non-orienté Graphe orienté

7
 Introduction aux graphes
Graphe pondéré
Graphe où un coût (poids) est associé à chacune
des transitions.

3
V1 V2
4

5 3 V5
1 2
V3 V4

8
 Introduction aux graphes
Chemin (path) : un chemin p , aussi noté v1~v4 , est une
séquence de transitions consécutives reliant v1 à v4.
Cycle : chemin v1~v1

V1 V2
v1~v4 = (v1,v2),(v2,v5),(v5,v4)
V5
ou
(v1,v3),(v3,v4)
V3 V4

9
 Introduction aux graphes
Noeuds adjacents (voisins): un noeud v2 est adjacent
à v1 s’il existe une transition (v1,v2).

Noeuds successeurs : un noeud v2 est un successeur

de v1 s’il existe un chemin v1~v2

V1 V2
Adjacents à V1: V2 et V3
V5

V3 V4 Successeurs de V1 : V2,V3,V4,V5

10
 Représentation
Matrice
Les transitions sont représentées par un tableau à deux
dimensions.
• M[i,j] représente la transition entre vi et vj
V1 V2 3
V1 V2
4

V5 5 3 V5
1 2
V3 V4 V3 V4
Destination Destination
v1 v2 v3 v4 v5 v1 v2 v3 v4 v5
v1 F V V F F v1 ∞ 3 5 ∞ ∞
v2 V F F V V v2 ∞ ∞ ∞ ∞ 4
Source
Source

v3 V F F V F v3 ∞ ∞ ∞ 1 ∞
v4 F V V F V v4 ∞ 3 ∞ ∞ ∞
v5 F V F V F v5 ∞ ∞ ∞ 2 ∞

11
 Représentation
Liste d’adjacences
Chaque nœud possède une liste de ses nœuds adjacents

V1 V2 3
V1 V2
4

V5 5 3 V5
1 2
V3 V4 V3 V4

v1 v2 v3 v1 (v2,3) (v3,5)
v2 v1 v4 v5 v2 (v5,4)
v3 v1 v4 v3 (v4,1)
v4 v2 v3 v5 v4 (v2,3)
v5 v2 v4 v5 (v4,2)
12
 Représentation
Liste d’adjacences
– Bonne performance pour tous les graphes
– Un peu plus compliquée à implémenter
• Mais plus de flexibilité

Matrice d’adjacences
– Meilleur choix lorsque le graphe est dense
• |E| est O(|V|2), ça fait de longues listes
– Difficile de faire des modifications
• Préférable lorsqu’il y peu d’insertion et de suppression de
nœuds.

13
 Parcourir un graphe
Largeur d’abord: à partir d’un nœud v, on visite
d’abord tous les voisins de v avant d’aller plus
en profondeur dans le graphe.

Profondeur d’abord: recherche tous les

successeurs possibles d’un nœud avant de
parcourir les autres voisins de ce nœud.

14
 Parcourir un graphe
BFS(G,s)
1. pour chaque u dans G.V – {s}
V1 V2
2. [Link] = blanc
3. [Link] ← gris
V5
4. F ← {}
5. Enqueue(F,s) V3 V4
6. tant que F n’est pas vide
7. u = Dequeue(F)
8. pour chaque v dans [Link]
9. si [Link] == blanc
10. [Link] = gris
11. Enqueue(F,v)
12. [Link] = noir

[Link]

15
 Parcourir un graphe
BFS(G,s)
1. pour chaque u dans G.V – {s}
V1 V2
2. [Link] = blanc
3. [Link] ← gris
V5
4. F ← {}
5. Enqueue(F,s) V3 V4
6. tant que F n’est pas vide
7. u = Dequeue(F)
8. pour chaque v dans [Link] F v1
9. si [Link] == blanc
10. [Link] = gris
11. Enqueue(F,v)
12. [Link] = noir

[Link]

16
 Parcourir un graphe
BFS(G,s)
1. pour chaque u dans G.V – {s}
V1 V2
2. [Link] = blanc
3. [Link] ← gris
V5
4. F ← {}
5. Enqueue(F,s) V3 V4
6. tant que F n’est pas vide
7. u = Dequeue(F)
8. pour chaque v dans [Link] F v2 v3
9. si [Link] == blanc
10. [Link] = gris
11. Enqueue(F,v)
12. [Link] = noir

[Link]

17
 Parcourir un graphe
BFS(G,s)
1. pour chaque u dans G.V – {s}
V1 V2
2. [Link] = blanc
3. [Link] ← gris
V5
4. F ← {}
5. Enqueue(F,s) V3 V4
6. tant que F n’est pas vide
7. u = Dequeue(F)
8. pour chaque v dans [Link] F v3 v5
9. si [Link] == blanc
10. [Link] = gris
11. Enqueue(F,v)
12. [Link] = noir

[Link]

18
 Parcourir un graphe
BFS(G,s)
1. pour chaque u dans G.V – {s}
V1 V2
2. [Link] = blanc
3. [Link] ← gris
V5
4. F ← {}
5. Enqueue(F,s) V3 V4
6. tant que F n’est pas vide
7. u = Dequeue(F)
8. pour chaque v dans [Link] F v3 v5
9. si [Link] == blanc
10. [Link] = gris
11. Enqueue(F,v)
12. [Link] = noir

[Link]

19
 Parcourir un graphe
BFS(G,s)
1. pour chaque u dans G.V – {s}
V1 V2
2. [Link] = blanc
3. [Link] ← gris
V5
4. F ← {}
5. Enqueue(F,s) V3 V4
6. tant que F n’est pas vide
7. u = Dequeue(F)
8. pour chaque v dans [Link] F v5 v4
9. si [Link] == blanc
10. [Link] = gris
11. Enqueue(F,v)
12. [Link] = noir

[Link]

20
 Parcourir un graphe
BFS(G,s)
1. pour chaque u dans G.V – {s}
V1 V2
2. [Link] = blanc
3. [Link] ← gris
V5
4. F ← {}
5. Enqueue(F,s) V3 V4
6. tant que F n’est pas vide
7. u = Dequeue(F)
8. pour chaque v dans [Link] F v4
9. si [Link] == blanc
10. [Link] = gris
11. Enqueue(F,v)
12. [Link] = noir

[Link]

21
 Parcourir un graphe
BFS(G,s)
1. pour chaque u dans G.V – {s}
V1 V2
2. [Link] = blanc
3. [Link] ← gris
V5
4. F ← {}
5. Enqueue(F,s) V3 V4
6. tant que F n’est pas vide
7. u = Dequeue(F)
8. pour chaque v dans [Link] F
9. si [Link] == blanc
10. [Link] = gris
11. Enqueue(F,v)
12. [Link] = noir

[Link]

22
 Parcourir un graphe
BFS(G,s)
1. pour chaque u dans G.V – {s}
2. [Link] = blanc
O(V)
3. [Link] ← gris
4. F ← {}
5. Enqueue(F,s)
6. tant que F n’est pas vide
7. u = Dequeue(F)
O(V)
8. pour chaque v dans [Link]

O(å E[v]) = O( E )
9. si [Link] == blanc
10. [Link] = gris
11. Enqueue(F,v) vÎV
12. [Link] = noir

BFS: O(V+E)
23
 Parcourir un graphe
(Profondeur d’abord)
DFS(G)
1. pour chaque u dans G.V
2. [Link] = blanc
3. pour chaque u dans G.V
4. si [Link] == blanc V1 V2
5. DFS-Visit(G,u)

V5
DFS-Visit(G,u)
1. [Link] = gris V3 V4
2. pour chaque v dans adj[u]
3. si [Link] == blanc
4. DFS-Visit(G,v)
5. [Link] = noir

24
 Parcourir un graphe
(Profondeur d’abord)
DFS(G)
1. pour chaque u dans G.V
2. [Link] = blanc
3. pour chaque u dans G.V
4. si [Link] == blanc V1 V2
5. DFS-Visit(G,u)

V5
DFS-Visit(G,u)
1. [Link] = gris V3 V4
2. pour chaque v dans adj[u]
3. si [Link] == blanc
4. DFS-Visit(G,v)
5. [Link] = noir

25
 Parcourir un graphe
(Profondeur d’abord)
DFS(G)
1. pour chaque u dans G.V
2. [Link] = blanc
3. pour chaque u dans G.V
4. si [Link] == blanc V1 V2
5. DFS-Visit(G,u)

V5
DFS-Visit(G,u)
1. [Link] = gris V3 V4
2. pour chaque v dans adj[u]
3. si [Link] == blanc
4. DFS-Visit(G,v)
5. [Link] = noir

26
 Parcourir un graphe
(Profondeur d’abord)
DFS(G)
1. pour chaque u dans G.V
2. [Link] = blanc
3. pour chaque u dans G.V
4. si [Link] == blanc V1 V2
5. DFS-Visit(G,u)

V5
DFS-Visit(G,u)
1. [Link] = gris V3 V4
2. pour chaque v dans adj[u]
3. si [Link] == blanc
4. DFS-Visit(G,v)
5. [Link] = noir

27
 Parcourir un graphe
(Profondeur d’abord)
DFS(G)
1. pour chaque u dans G.V
2. [Link] = blanc
3. pour chaque u dans G.V
4. si [Link] == blanc V1 V2
5. DFS-Visit(G,u)

V5
DFS-Visit(G,u)
1. [Link] = gris V3 V4
2. pour chaque v dans adj[u]
3. si [Link] == blanc
4. DFS-Visit(G,v)
5. [Link] = noir

28
 Parcourir un graphe
(Profondeur d’abord)
DFS(G)
1. pour chaque u dans G.V
2. [Link] = blanc
3. pour chaque u dans G.V
4. si [Link] == blanc V1 V2
5. DFS-Visit(G,u)

V5
DFS-Visit(G,u)
1. [Link] = gris V3 V4
2. pour chaque v dans adj[u]
3. si [Link] == blanc
4. DFS-Visit(G,v)
5. [Link] = noir

29
 Parcourir un graphe
(Profondeur d’abord)
DFS(G)
1. pour chaque u dans G.V
2. [Link] = blanc
3. pour chaque u dans G.V
4. si [Link] == blanc V1 V2
5. DFS-Visit(G,u)

V5
DFS-Visit(G,u)
1. [Link] = gris V3 V4
2. pour chaque v dans adj[u]
3. si [Link] == blanc
4. DFS-Visit(G,v)
5. [Link] = noir

30
 Parcourir un graphe
(Profondeur d’abord)
DFS(G)
1. pour chaque u dans G.V
2. [Link] = blanc
3. pour chaque u dans G.V
4. si [Link] == blanc V1 V2
5. DFS-Visit(G,u)

V5
DFS-Visit(G,u)
1. [Link] = gris V3 V4
2. pour chaque v dans adj[u]
3. si [Link] == blanc
4. DFS-Visit(G,v)
5. [Link] = noir

31
 Parcourir un graphe
(Profondeur d’abord)
DFS(G)
1. pour chaque u dans G.V
2. [Link] = blanc
3. pour chaque u dans G.V
4. si [Link] == blanc V1 V2
5. DFS-Visit(G,u)

V5
DFS-Visit(G,u)
1. [Link] = gris V3 V4
2. pour chaque v dans adj[u]
3. si [Link] == blanc
4. DFS-Visit(G,v)
5. [Link] = noir

32
 Parcourir un graphe
(Profondeur d’abord)
DFS(G)
1. pour chaque u dans G.V
2. [Link] = blanc
3. pour chaque u dans G.V
4. si [Link] == blanc V1 V2
5. DFS-Visit(G,u)

V5
DFS-Visit(G,u)
1. [Link] = gris V3 V4
2. pour chaque v dans adj[u]
3. si [Link] == blanc
4. DFS-Visit(G,v)
5. [Link] = noir

33
 Parcourir un graphe
(Profondeur d’abord)
DFS(G)
1. pour chaque u dans G.V
2. [Link] = blanc
3. pour chaque u dans G.V
4. si [Link] == blanc V1 V2
5. DFS-Visit(G,u)

V5
DFS-Visit(G,u)
1. [Link] = gris V3 V4
2. pour chaque v dans adj[u]
3. si [Link] == blanc
4. DFS-Visit(G,v)
5. [Link] = noir

34
 Parcourir un graphe
DFS(G)
1. pour chaque u dans G.V
2. [Link] = blanc
O(V)
3. pour chaque u dans G.V
4. si [Link] == blanc O(V)
5. DFS-Visit(G,u)

DFS-Visit(G,u)
1. [Link] = gris

O(å E[v]) = O( E )
2. pour chaque v dans adj[u]
3. si [Link] == blanc
vÎV
4. DFS-Visit(G,v)
5. [Link] = noir

DFS: O(V+E)

35
 Tri topologique
Le tri topologique d’un graphe G = (V,E) est une liste
linéaire des noeuds telle que s’il existe une transition
(u,v), u précède v dans la liste.

Le tri topologique peut être appliqué au graphe

acyclique (sans cycle) seulement.

Le tri topologique peut être vu comme un alignement

de ses sommets le long d’une ligne horizontale de
manière que tous les arcs soient orientés de gauche à
droite.
36
Tri topologique

37
 Tri topologique
TriTopologique(G) DFS-Visit(G,u)
1. pour chaque u dans G.V 1. [Link] = gris
2. [Link] = blanc 2. pour chaque v dans adj[u]
3. P ← {} 3. si [Link] == blanc
4. pour chaque u dans G.V 4. DFS-Visit(G,v)
5. si [Link] == blanc 5. Push(P,u)
6. DFS-Visit(G,u) 6. [Link] = noir

1 2 3 4 5

6 7 8 9 10

38
 Tri topologique
TriTopologique(G)
1. pour chaque u dans G.V
2. couleur[u] ← blanc O(V)
3. P ← {}
4. pour chaque u dans G.V
5. si couleur[u] = blanc O(V)
6. DFS-Visit(G,u)

DFS-Visit(G,u)
1. couleur[u] ← gris
2. pour chaque v dans adj[u]
3. si couleur[v] = blanc O(å E[v]) = O( E )
4. DFS-Visit(G,v) vÎV
5. Push(P,u)
6. couleur[u] ← noir

Tri topologique: O(V+E)

39
 Composantes fortement connectées
Définition: Une composante (graphe ou sous-graphe) est
fortement connectée s’il existe un chemin entre tous les
nœuds de ladite composante.

1 2 1 2

6 7 6 7

Graphe non Graphe fortement

fortement connecté connecté

40
 Composantes fortement connectées
Quels sont les composantes fortement
connectées?

1 2 3 4

5 6 7 8

41
 Chemin de Euler
Problème des 7 ponts de Königsberg

Existe-t-il un chemin permettant de traverser les 7 ponts

une seule fois et de revenir au point de départ?

42
 Chemin de Euler
Représentation par un graphe

Théorème de Euler :
Un chemin parcourant toutes les transitions une seule
fois est possible si et seulement si:
• tous les nœuds ont un degré pair
• si seulement deux nœuds ont un degré impair (semi-
eulérien).

43
 Chemin de Euler
Algorithme de Fleury
1. Vérifier que le graphe est entièrement connecté et que tous les
nœuds ont un degré pair ou exactement 2 nœuds avec un degré
impair
2. Démarrer à un nœud avec un degré impair sinon démarrer avec
n’importe quel nœud
3. Choisir une transition dont la suppression ne déconnecte pas
un sous-graphe non visité
4. Marquer la transition comme étant effacée
5. Retourner à l’étape 3 tant qu’il reste des transitions accessibles.

44
 Chemin de Euler

A D

C F

B E

45
Konigsberg (Kaliningrad)

46
 Chemin Hamiltonien
Problème du voyageur de commerce

source : [Link]

47
 Chemin Hamiltonien
Définition:
Un chemin Hamiltonien est un chemin qui passe
par chacun des nœuds d’un graphe seulement une
fois.

Algorithme:
Il n’y a pas d’algorithme connue qui
résout ce problème efficacement.

48
 Chemin Hamiltonien

Problème du voyageur de commerce:

• Si, par exemple, on a 21 villes alors le nombre de
solutions possibles est (n-1)! = (21-1)! = 20!.
• Si le temps de calcul de chaque solution est d’une
milliseconde alors nous aurions besoin d'environ 770
siècles pour trouver la meilleure solution!

49
 Problème du voyageur de commerce: compétition
Year Research Team Size of Instance Name

1954 G. Dantzig, R. Fulkerson, and S. Johnson 49 cities dantzig42

1971 M. Held and R.M. Karp 64 cities 64 random points
1975 P.M. Camerini, L. Fratta, and F. Maffioli 67 cities 67 random points
1977 M. Grötschel 120 cities gr120
1980 H. Crowder and M.W. Padberg 318 cities lin318
1987 M. Padberg and G. Rinaldi 532 cities att532
1987 M. Grötschel and O. Holland 666 cities gr666
1987 M. Padberg and G. Rinaldi 2,392 cities pr2392
1994 D. Applegate, R. Bixby, V. Chvátal, and W. Cook 7,397 cities pla7397
1998 D. Applegate, R. Bixby, V. Chvátal, and W. Cook 13,509 cities usa13509
2001 D. Applegate, R. Bixby, V. Chvátal, and W. Cook 15,112 cities d15112

D. Applegate, R. Bixby, V. Chvátal, W. Cook,

2004 24,978 cities sw24798
and K. Helsgaun

D. Applegate, R. Bixby, V. Chvátal, W. Cook,

2006 85,900 cities pla85900
D. Espinoza, M. Goycoolea and K. Helsgaun

World TSP Tour

2013 K. Helsgaun 1,904,711 cities (tour length (not optimal):
7,515,772,212 )

50
 Les prochains cours
Semaine 7: Intra
Semaine 8: Recherche dans les graphes
• Plus court chemin entre deux nœuds
- Algorithme de Dijkstra
- Algorithme « meilleur en premier »
- Algorithme A*
• Recherche dans un graphe de jeu
- MinMax
- Alpha-beta
- Heuristiques

51