Graphes : Rappel

Ali CHOUKRI

ENSAS

Université Cadi Ayad

Mars 2018

Graphes : Rappel 1 / 32
Définition : Graphe = dessin ?

Définition
Un graphe est constitué :
de sommets (vertices en anglais), représentés par des points
d’arêtes (edges en anglais), représentés par des traits entre les points

Graphes : Rappel 2 / 32
Définition : Graphe = dessin ?

Définition
Un graphe est constitué :
de sommets (vertices en anglais), représentés par des points
d’arêtes (edges en anglais), représentés par des traits entre les points

Graphes : Rappel 2 / 32
Définition formelle

Définition
Un graphe (non orienté) est un couple G = (V, E ) où :
V est un ensemble fini (de sommets)
E est un ensemble dont chaque élément, appelé arête, est un
ensemble de 2 sommets

Graphes : Rappel 3 / 32
Exemple

Ici

Graphes : Rappel 4 / 32
Exemple

Ici V = {0, 1, 2, 3, 4, 5, 6} et
E = {{0, 6}, {1, 2}, {1, 3}, {1, 4}, {2, 4}, {2, 5}, {3, 4}, {4, 5}}.

Graphes : Rappel 4 / 32
Graphe orienté

Définition
⃗ = (V, E
Un graphe orienté est un couple G ⃗ ) où :
V est un ensemble fini (de sommets)
⃗ ⊆ V × V est un ensemble de couples de sommets (appelés arcs)
E

Graphes : Rappel 5 / 32
Graphe orienté

Définition
⃗ = (V, E
Un graphe orienté est un couple G ⃗ ) où :
V est un ensemble fini (de sommets)
⃗ ⊆ V × V est un ensemble de couples de sommets (appelés arcs)
E

Graphes : Rappel 5 / 32
Exemple

Ici

Graphes : Rappel 6 / 32
Exemple

Ici V = {0, 1, 2, 3, 4, 5, 6} et
⃗ = {(0, 6), (6, 0), (1, 2), (1, 3), (4, 1), (2, 4), (2, 5), (3, 4), (5, 4)}.
E

Graphes : Rappel 6 / 32
Vocabulaire

Soit G = (V, E ) un graphe non orienté.

Si e = {u, v} ∈ E on dit que u et v sont les extrémités de e et que u et v
sont voisins (ou adjacents).

Graphes : Rappel 7 / 32
Vocabulaire

Soit G = (V, E ) un graphe non orienté.

Si e = {u, v} ∈ E on dit que u et v sont les extrémités de e et que u et v
sont voisins (ou adjacents).
Le degré d’un sommet v ∈ V , noté deg(v), est son nombre de voisins.
Si deg(v) = 1, v est une feuille.

Graphes : Rappel 7 / 32
Vocabulaire

Soit G = (V, E ) un graphe non orienté.

Si e = {u, v} ∈ E on dit que u et v sont les extrémités de e et que u et v
sont voisins (ou adjacents).
Le degré d’un sommet v ∈ V , noté deg(v), est son nombre de voisins.
Si deg(v) = 1, v est une feuille.
P
Formule des degrés v∈V deg(v) = 2|E |

Graphes : Rappel 7 / 32
Vocabulaire

Soit G = (V, E ) un graphe non orienté.

Si e = {u, v} ∈ E on dit que u et v sont les extrémités de e et que u et v
sont voisins (ou adjacents).
Le degré d’un sommet v ∈ V , noté deg(v), est son nombre de voisins.
Si deg(v) = 1, v est une feuille.
P
Formule des degrés v∈V deg(v) = 2|E |
Pour un graphe orienté : deg+ (v) = deg− (v) = |E ⃗|
P P

Graphes : Rappel 7 / 32
Vocabulaire

Soit G = (V, E ) un graphe non orienté.

Si e = {u, v} ∈ E on dit que u et v sont les extrémités de e et que u et v
sont voisins (ou adjacents).
Le degré d’un sommet v ∈ V , noté deg(v), est son nombre de voisins.
Si deg(v) = 1, v est une feuille.
P
Formule des degrés v∈V deg(v) = 2|E |
Pour un graphe orienté : deg+ (v) = deg− (v) = |E ⃗|
P P

un chemin est une suite d’arêtes consécutives différentes.

Graphes : Rappel 7 / 32
Vocabulaire

Soit G = (V, E ) un graphe non orienté.

Si e = {u, v} ∈ E on dit que u et v sont les extrémités de e et que u et v
sont voisins (ou adjacents).
Le degré d’un sommet v ∈ V , noté deg(v), est son nombre de voisins.
Si deg(v) = 1, v est une feuille.
P
Formule des degrés v∈V deg(v) = 2|E |
Pour un graphe orienté : deg+ (v) = deg− (v) = |E ⃗|
P P

un chemin est une suite d’arêtes consécutives différentes.

La longueur d’un chemin est son nombre d’arêtes.

Graphes : Rappel 7 / 32
Vocabulaire

Soit G = (V, E ) un graphe non orienté.

Si e = {u, v} ∈ E on dit que u et v sont les extrémités de e et que u et v
sont voisins (ou adjacents).
Le degré d’un sommet v ∈ V , noté deg(v), est son nombre de voisins.
Si deg(v) = 1, v est une feuille.
P
Formule des degrés v∈V deg(v) = 2|E |
Pour un graphe orienté : deg+ (v) = deg− (v) = |E ⃗|
P P

un chemin est une suite d’arêtes consécutives différentes.

La longueur d’un chemin est son nombre d’arêtes.
La distance de u à v est la plus petite longueur d’un chemin de u à v (
∞ si il n’y a pas de chemin) : c’est une distance au sens mathématique.

Graphes : Rappel 7 / 32
Graphe complet

Un graphe complet

Graphes : Rappel 8 / 32
Graphe complet

Un graphe complet est un graphe non orienté possédant toutes les arêtes
possibles.

Graphes : Rappel 8 / 32
Graphe complet

Un graphe complet est un graphe non orienté possédant toutes les arêtes
possibles.

Graphes : Rappel 8 / 32
Graphe complet

Un graphe complet est un graphe non orienté possédant toutes les arêtes
possibles.

¶ µ
n
Un graphe complet avec n sommets a arêtes : c’est le nombre
2
maximum d’arêtes d’un graphe à n sommets.

Graphes : Rappel 8 / 32
Graphe complet

Un graphe complet est un graphe non orienté possédant toutes les arêtes
possibles.

µ
¶
n
Un graphe complet avec n sommets a arêtes : c’est le nombre
2
maximum d’arêtes d’un graphe à n sommets.
De façon générale, tout graphe à n sommets et m arêtes vérifie m = O n 2
¡ ¢

Graphes : Rappel 8 / 32
Connexité
Un graphe non orienté est connexe

Graphes : Rappel 9 / 32
Connexité
Un graphe non orienté est connexe s’il possède un chemin de n’importe
quel sommet à n’importe quel autre.

Graphes : Rappel 9 / 32
Connexité
Un graphe non orienté est connexe s’il possède un chemin de n’importe
quel sommet à n’importe quel autre.

Graphe non connexe

Graphes : Rappel 9 / 32
Connexité
Un graphe non orienté est connexe s’il possède un chemin de n’importe
quel sommet à n’importe quel autre.

Graphe non connexe

Graphes : Rappel 9 / 32
Connexité
Un graphe non orienté est connexe s’il possède un chemin de n’importe
quel sommet à n’importe quel autre.

Graphe non connexe

Graphe connexe
Graphes : Rappel 9 / 32
cycle
Un cycle est un chemin revenant au sommet de départ.

Graphes : Rappel 10 / 32
cycle
Un cycle est un chemin revenant au sommet de départ.

Cycle non orienté

Graphes : Rappel 10 / 32
cycle
Un cycle est un chemin revenant au sommet de départ.

Cycle non orienté

Cycle orienté
Graphes : Rappel 10 / 32
Graphe acyclique

Un graphe est acyclique (ou : sans cycle)

Graphes : Rappel 11 / 32
Graphe acyclique

Un graphe est acyclique (ou : sans cycle) s’il ne contient pas de cycle.

Graphes : Rappel 11 / 32
Graphe acyclique

Un graphe est acyclique (ou : sans cycle) s’il ne contient pas de cycle.

Graphe contenant un cycle

Graphes : Rappel 11 / 32
Graphe acyclique

Un graphe est acyclique (ou : sans cycle) s’il ne contient pas de cycle.

Graphe contenant un cycle

Graphe acyclique

Graphes : Rappel 11 / 32
Arbre

Définition
Théorème / définition
Un graphe T à n sommets est un arbre s’il est connexe et acyclique. C’est
équivalent aux conditions suivantes :
T est connexe et a n − 1 arêtes.
T est acyclique et a n − 1 arêtes.
II existe un unique chemin entre 2 sommets quelconques de T .

Graphes : Rappel 12 / 32
Exemple d’arbre :

Application : relier (en électricité, fibre optique...) plusieurs maisons avec le

moins de fil possible.

Graphes : Rappel 13 / 32
Représentation des en Python

L’objectif de cette partie est de modéliser les graphes en Python. Nous

explorerons deux approches différentes : l’une utilise les matrices (une
approche mathématique), tandis que l’autre utilise la structure de
données de liste en Python.

Graphes : Rappel 14 / 32
Représentation

Première façon : Matrice d’adjacence

On peut représenter un graphe non orienté (V, E ), où V = {0, . . . , n − 1} par
une matrice d’adjacence A de taille n × n définie par :
A i , j = 1 ⇐⇒ {i , j } ∈ E
A i , j = 0 ⇐⇒ {i , j } ∉ E

Graphes : Rappel 15 / 32
Représentation

Première façon : Matrice d’adjacence

On peut représenter un graphe non orienté (V, E ), où V = {0, . . . , n − 1} par
une matrice d’adjacence A de taille n × n définie par :
A i , j = 1 ⇐⇒ {i , j } ∈ E
A i , j = 0 ⇐⇒ {i , j } ∉ E
Remarque : A est symétrique.

Graphes : Rappel 15 / 32
Représentation

Première façon : Matrice d’adjacence

On peut représenter un graphe non orienté (V, E ), où V = {0, . . . , n − 1} par
une matrice d’adjacence A de taille n × n définie par :
A i , j = 1 ⇐⇒ {i , j } ∈ E
A i , j = 0 ⇐⇒ {i , j } ∉ E
Remarque : A est symétrique.
Pour un graphe orienté (V, E ⃗) :
⃗
A i , j = 1 ⇐⇒ (i , j ) ∈ E
⃗
A i , j = 0 ⇐⇒ (i , j ) ∉ E

Graphes : Rappel 15 / 32
Représentation

Première façon : Matrice d’adjacence

On peut représenter un graphe non orienté (V, E ), où V = {0, . . . , n − 1} par
une matrice d’adjacence A de taille n × n définie par :
A i , j = 1 ⇐⇒ {i , j } ∈ E
A i , j = 0 ⇐⇒ {i , j } ∉ E
Remarque : A est symétrique.
Pour un graphe orienté (V, E ⃗) :
⃗
A i , j = 1 ⇐⇒ (i , j ) ∈ E
⃗
A i , j = 0 ⇐⇒ (i , j ) ∉ E
Remarque : A n’est pas symétrique (a priori).

Graphes : Rappel 15 / 32
Exemple : Par matrice d’adjacence

Graphes : Rappel 16 / 32
Exemple : Par matrice d’adjacence

En Python, On utilise soit une liste des listes ou bien un tableau (array) de
numpy.
Graphes : Rappel 16 / 32
Liste d’adjacence

Deuxième façon : Liste d’adjacence

Graphes : Rappel 17 / 32
Liste d’adjacence

Deuxième façon : Liste d’adjacence

La représentation par liste d’adjacence consiste à stocker, pour chaque
sommet, la liste de ses voisins. On utilise pour cela une liste G de listes, telle
que G[u] soit la liste des voisins de u.

Graphes : Rappel 17 / 32
Exemple : Liste d’adjacence

Graphes : Rappel 18 / 32
Parcours de Graphes

L’une des notions fondamentales en théorie des graphes est celle des
parcours de graphes. Les parcours permettent d’explorer et de naviguer à
travers les sommets et les arêtes d’un graphe, ce qui est essentiel dans de
nombreux problèmes et applications informatiques (Recherche de
Chemins et Navigation, Algorithmes de Jeux, Recherche d’Amis
Communs...).

Graphes : Rappel 19 / 32
Parcours de graphe : Définitions
Voici les deux principaux parcours, visitant les sommets de proche en
proche :

Graphes : Rappel 20 / 32
Parcours de graphe : Définitions
Voici les deux principaux parcours, visitant les sommets de proche en
proche :
Le parcours en profondeur (Depth-First Search, DFS) est une
technique de parcours qui explore le graphe aussi profondément que
possible le long d’une branche avant de revenir en arrière. En d’autres
termes, il explore un sommet autant que possible avant de passer au
sommet suivant. Le DFS est souvent implémenté récursivement et est
utile pour trouver des composantes connexes, des cycles, et d’autres
propriétés du graphe.

Graphes : Rappel 20 / 32
Parcours de graphe : Définitions
Voici les deux principaux parcours, visitant les sommets de proche en
proche :
Le parcours en profondeur (Depth-First Search, DFS) est une
technique de parcours qui explore le graphe aussi profondément que
possible le long d’une branche avant de revenir en arrière. En d’autres
termes, il explore un sommet autant que possible avant de passer au
sommet suivant. Le DFS est souvent implémenté récursivement et est
utile pour trouver des composantes connexes, des cycles, et d’autres
propriétés du graphe.
Le parcours en largeur (Breadth-First Search, BFS) est une technique
de parcours qui explore le graphe en explorant tous les voisins d’un
sommet avant de passer aux voisins de ses voisins. Il explore le graphe
en "largeur" à partir de la source initiale. Le BFS est souvent utilisé
pour trouver le plus court chemin entre deux sommets, la recherche
de la solution la plus courte, ou la recherche dans un graphe non
pondéré.
Graphes : Rappel 20 / 32
Parcours en profondeur (DFS)

Un parcours en profondeur sur un graphe G = (V, E ) depuis un sommet u

consiste à visiter u puis visiter récursivement chaque voisin de u qui n’a
pas déjà été vu.

Graphes : Rappel 21 / 32
Exemple

sommet pas encore visité

sommet en cours de traitement

appel récursif en pause

visite du sommet terminé

Exemple

sommet pas encore visité

sommet en cours de traitement

appel récursif en pause

visite du sommet terminé

Exemple

sommet pas encore visité

sommet en cours de traitement

appel récursif en pause

visite du sommet terminé

Exemple

sommet pas encore visité

sommet en cours de traitement

appel récursif en pause

visite du sommet terminé

Exemple

sommet pas encore visité

sommet en cours de traitement

appel récursif en pause

visite du sommet terminé

Exemple

sommet pas encore visité

sommet en cours de traitement

appel récursif en pause

visite du sommet terminé

Exemple

sommet pas encore visité

sommet en cours de traitement

appel récursif en pause

visite du sommet terminé

Exemple

sommet pas encore visité

sommet en cours de traitement

appel récursif en pause

visite du sommet terminé

Exemple

sommet pas encore visité

sommet en cours de traitement

appel récursif en pause

visite du sommet terminé

Exemple

sommet pas encore visité

sommet en cours de traitement

appel récursif en pause

visite du sommet terminé

Exemple

sommet pas encore visité

sommet en cours de traitement

appel récursif en pause

visite du sommet terminé

Parcours en profondeur (DFS)

Un parcours en profondeur sur un graphe G = (V, E ) depuis un sommet u

consiste à visiter u puis visiter récursivement chaque voisin de u qui n’a
pas déjà été vu.

Question : Programmer le parcours en profondeur en Python ?

Graphes : Rappel 22 / 32
Parcours en profondeur (DFS)

Un parcours en profondeur sur un graphe G = (V, E ) depuis un sommet u

consiste à visiter u puis visiter récursivement chaque voisin de u qui n’a
pas déjà été vu.

Question : Programmer le parcours en profondeur en Python ?

visited[u] vaut True si u a déjà été visité.

Graphes : Rappel 22 / 32
Parcours en largeur (BFS)

Définition (Parcours en largeur )

Parcours en largeur (ou BFS pour Breadth-First Search) : est une technique
de parcours qui explore le graphe en explorant tous les voisins d’un
sommet avant de passer aux voisins de ses voisins. Il explore le graphe en
"largeur" à partir de la source initiale.

Graphes : Rappel 23 / 32
Parcours en largeur (BFS)

Définition (Parcours en largeur )

Parcours en largeur (ou BFS pour Breadth-First Search) : est une technique
de parcours qui explore le graphe en explorant tous les voisins d’un
sommet avant de passer aux voisins de ses voisins. Il explore le graphe en
"largeur" à partir de la source initiale.

Autrement dit : on visite les sommets par distance croissante depuis un

sommet de départ.

Graphes : Rappel 23 / 32
Principe

A partir d’un sommet, L’algorithme explore tous ses voisins. Puis, pour
chaque voisin, il explore tous ses voisins, et ainsi de suite...

Graphes : Rappel 24 / 32
Animation

Illustration du parcours en largeur

Graphes : Rappel 25 / 32
Graphes : Rappel 25 / 32
Ligne 2 F J K Ligne 3

G L

Ligne 1 A B C D E

H I M
 Ligne 2 F J K Ligne 3
0

G L

Ligne 1 A B C D E

H I M

File: F
Visite: F
Distance: 0
 Ligne 2 F J K Ligne 3
0 1

G L
1

Ligne 1 A B C D E

H I M

File: G J
Visite: F G J
Distance: 0 1 1
 Ligne 2 F J K Ligne 3
0 1

G L
1

Ligne 1 A B C D E
2

H I M

File: J A
Visite: F G J A
Distance: 0 1 1 2
 Ligne 2 F J K Ligne 3
0 1 2

G L
1

Ligne 1 A B C D E
2

H I M

File: A K
Visite: F G J A K
Distance: 0 1 1 2 2
 Ligne 2 F J K Ligne 3
0 1 2

G L
1

Ligne 1 A B C D E
2 3

H I M
3

File: K B H
Visite: F G J A K B H
Distance: 0 1 1 2 2 3 3
 Ligne 2 F J K Ligne 3
0 1 2

G L
1 3

Ligne 1 A B C D E
2 3

H I M
3

File: B H L
Visite: F G J A K B H L
Distance: 0 1 1 2 2 3 3 3
 Ligne 2 F J K Ligne 3
0 1 2

G L
1 3

Ligne 1 A B C D E
2 3 4

H I M
3

File: H L C
Visite: F G J A K B H L C
Distance: 0 1 1 2 2 3 3 3 4
 Ligne 2 F J K Ligne 3
0 1 2

G L
1 3

Ligne 1 A B C D E
2 3 4

H I M
3 4

File: L C I
Visite: F G J A K B H L C I
Distance: 0 1 1 2 2 3 3 3 4 4
 Ligne 2 F J K Ligne 3
0 1 2

G L
1 3

Ligne 1 A B C D E
2 3 4

H I M
3 4

File: C I
Visite: F G J A K B H L C I
Distance: 0 1 1 2 2 3 3 3 4 4
 Ligne 2 F J K Ligne 3
0 1 2

G L
1 3

Ligne 1 A B C D E
2 3 4 5

H I M
3 4 5

File: I D M
Visite: F G J A K B H L C I D M
Distance: 0 1 1 2 2 3 3 3 4 4 5 5
 Ligne 2 F J K Ligne 3
0 1 2

G L
1 3

Ligne 1 A B C D E
2 3 4 5

H I M
3 4 5

File: D M
Visite: F G J A K B H L C I D M
Distance: 0 1 1 2 2 3 3 3 4 4 5 5
 Ligne 2 F J K Ligne 3
0 1 2

G L
1 3

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

H I M
3 4 5

File: M E
Visite: F G J A K B H L C I D M E
Distance: 0 1 1 2 2 3 3 3 4 4 5 5 6
 Ligne 2 F J K Ligne 3
0 1 2

G L
1 3

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

H I M
3 4 5

File: E
Visite: F G J A K B H L C I D M E
Distance: 0 1 1 2 2 3 3 3 4 4 5 5 6
 Ligne 2 F J K Ligne 3
0 1 2

G L
1 3

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

H I M
3 4 5

File:
Visite: F G J A K B H L C I D M E
Distance: 0 1 1 2 2 3 3 3 4 4 5 5 6
Algorithme

Remarques
il faut disposer d’une structure de donnée en Python, qui ressemble à une
file d’attente :

Graphes : Rappel 26 / 32
Algorithme

Remarques
il faut disposer d’une structure de donnée en Python, qui ressemble à une
file d’attente :
D’ajouter un élément (fin de la queue)

Graphes : Rappel 26 / 32
Algorithme

Remarques
il faut disposer d’une structure de donnée en Python, qui ressemble à une
file d’attente :
D’ajouter un élément (fin de la queue)
D’extraire un élément (début de la queue)

Graphes : Rappel 26 / 32
Algorithme

Remarques
il faut disposer d’une structure de donnée en Python, qui ressemble à une
file d’attente :
D’ajouter un élément (fin de la queue)
D’extraire un élément (début de la queue)

L’algorithme se déroule donc ainsi :

Graphes : Rappel 26 / 32
Algorithme

Remarques
il faut disposer d’une structure de donnée en Python, qui ressemble à une
file d’attente :
D’ajouter un élément (fin de la queue)
D’extraire un élément (début de la queue)

L’algorithme se déroule donc ainsi :

Mettre le nœud de départ dans une file et le marquer comme visité

Graphes : Rappel 26 / 32
Algorithme

Remarques
il faut disposer d’une structure de donnée en Python, qui ressemble à une
file d’attente :
D’ajouter un élément (fin de la queue)
D’extraire un élément (début de la queue)

L’algorithme se déroule donc ainsi :

Mettre le nœud de départ dans une file et le marquer comme visité
Tant que la file n’est pas vide :

Graphes : Rappel 26 / 32
Algorithme

Remarques
il faut disposer d’une structure de donnée en Python, qui ressemble à une
file d’attente :
D’ajouter un élément (fin de la queue)
D’extraire un élément (début de la queue)

L’algorithme se déroule donc ainsi :

Mettre le nœud de départ dans une file et le marquer comme visité
Tant que la file n’est pas vide :
Ï Retirer le premier sommet de la file pour le traiter

Graphes : Rappel 26 / 32
Algorithme

Remarques
il faut disposer d’une structure de donnée en Python, qui ressemble à une
file d’attente :
D’ajouter un élément (fin de la queue)
D’extraire un élément (début de la queue)

L’algorithme se déroule donc ainsi :

Mettre le nœud de départ dans une file et le marquer comme visité
Tant que la file n’est pas vide :
Ï Retirer le premier sommet de la file pour le traiter
Ï Mettre tous ses voisins non visités à la fin de la file et les marquer visités

Graphes : Rappel 26 / 32
Parcours en Largeur : avec une file

En Python, nous disposons déjà d’un module qui implémente une

structure de file : la bibliothèque collections. Dans ce module, nous avons
des méthodes qui permettent de modéliser la notion de file d’attente :

Graphes : Rappel 27 / 32
 Parcours en Largeur : avec une file

En Python, nous disposons déjà d’un module qui implémente une

structure de file : la bibliothèque collections. Dans ce module, nous avons
des méthodes qui permettent de modéliser la notion de file d’attente :
1 from collections import deque
2 q = deque() # file vide
3 q.appendleft(4)
4 q.appendleft(7)
5 q.pop() # renvoie 4
6 q.appendleft(−5)
7 q.pop() # renvoie 7

Graphes : Rappel 27 / 32
 Parcours en Largeur : avec une file

En Python, nous disposons déjà d’un module qui implémente une

structure de file : la bibliothèque collections. Dans ce module, nous avons
des méthodes qui permettent de modéliser la notion de file d’attente :
1 from collections import deque
2 q = deque() # file vide
3 q.appendleft(4)
4 q.appendleft(7)
5 q.pop() # renvoie 4
6 q.appendleft(−5)
7 q.pop() # renvoie 7

La file q est toujours de la forme :

Graphes : Rappel 27 / 32
 Parcours en Largeur : avec une file

En Python, nous disposons déjà d’un module qui implémente une

structure de file : la bibliothèque collections. Dans ce module, nous avons
des méthodes qui permettent de modéliser la notion de file d’attente :
1 from collections import deque
2 q = deque() # file vide
3 q.appendleft(4)
4 q.appendleft(7)
5 q.pop() # renvoie 4
6 q.appendleft(−5)
7 q.pop() # renvoie 7

La file q est toujours de la forme :

Graphes : Rappel 27 / 32
 Parcours en Largeur : avec une file

En Python, nous disposons déjà d’un module qui implémente une

structure de file : la bibliothèque collections. Dans ce module, nous avons
des méthodes qui permettent de modéliser la notion de file d’attente :
1 from collections import deque
2 q = deque() # file vide
3 q.appendleft(4)
4 q.appendleft(7)
5 q.pop() # renvoie 4
6 q.appendleft(−5)
7 q.pop() # renvoie 7

La file q est toujours de la forme :

Les sommets sont donc traités par distance croissante à s : d’abord s, puis
les voisins de s, puis ceux à distance 2...
Graphes : Rappel 27 / 32
Algorithme BFS en Python avec deque de collections

Question : écrire l’algorithme du parcours en largeur en utilisant l’objet

deque du module collections

Graphes : Rappel 28 / 32
 Algorithme BFS en Python avec deque de collections

Question : écrire l’algorithme du parcours en largeur en utilisant l’objet

deque du module collections

Réponse
1 def bfs(G, s) :
2 visited = [False]∗len(G)
3 q = deque([s])
4 while len(q) > 0:
5 u = q.pop()
6 if not visited [u ]:
7 visited [u] = True
8 print(u)
9 for v in G[u]:
10 if not visited [v ]: #mais c’est possible qu’ il soit dans la file !
11 q.appendleft(v)

Graphes : Rappel 28 / 32
Application au calcul de distance

Question :
Comment connaître la distance d’un sommet s aux autres ?

Graphes : Rappel 29 / 32
Application au calcul de distance

Question :
Comment connaître la distance d’un sommet s aux autres ?
Réponse : L’idée pour calculer les distances est d’effectuer un parcours en
largeur (BFS) à partir du sommet "s", en maintenant une file de sommets à
explorer. Pour chaque sommet exploré, on met à jour sa distance par
rapport à "s" en ajoutant 1 à la distance de son sommet parent. Le résultat
final est une liste des distances de "s" à tous les autres sommets du graphe.

Graphes : Rappel 29 / 32
 Réponse :
1 def distance(G, s) :
2 n = len(G)
3 visited = [False]∗n
4 q = deque( [s] )
5 dist = [−1 for i in range(n)]
6 dist [ s ] = 0
7 while len(q) > 0:
8 u= q.pop()
9 if not visited [u ]:
10 visited [u] = True
11 for v in G[u]:
12 if not visited [v ]:
13 q.appendleft( v )
14 """ Ici , il faut faire attention , car il est possible qu’ il
soit visite ’ par un autre chemin plus court."""
15 if dist [v] == −1 :
16 dist [v] = dist[u] +1
17 return dist

Graphes : Rappel 30 / 32
Application au calcul de distance : Plus courts chemins

Question :
Comment connaître un plus court chemin d’un sommet s à un autre ?

Graphes : Rappel 31 / 32
Application au calcul de distance : Plus courts chemins

Question :
Comment connaître un plus court chemin d’un sommet s à un autre ?
Réponse : Stocker pred[v] = prédécesseur de v dans le parcours

Graphes : Rappel 31 / 32
Application au calcul de distance : Plus courts chemins

Question :
Comment connaître un plus court chemin d’un sommet s à un autre ?
Réponse : Stocker pred[v] = prédécesseur de v dans le parcours i.e en
stockant les prédécesseurs de chaque sommet visité dans le parcours dans
la liste pred.

Graphes : Rappel 31 / 32
Application au calcul de distance : Plus courts chemins

Question :
Comment connaître un plus court chemin d’un sommet s à un autre ?
Réponse : Stocker pred[v] = prédécesseur de v dans le parcours i.e en
stockant les prédécesseurs de chaque sommet visité dans le parcours dans
la liste pred.
On peut ensuite remonter les prédécesseurs de v à s :

Graphes : Rappel 31 / 32
 1 def chemin(G, s):
2 visited = [False]∗len(G)
3 q = deque( [s] )
4 pred = [−1 for i in range(len(G))]
5 pred[s ] = s
6 while len(q) > 0:
7 u = q.pop()
8 if not visited [u ]:
9 visited [u] = True
10 for v in G[u]:
11 if not visited [v ]:
12 q.appendleft( v )
13 if pred[v] == −1:
14 pred[v] = u
15 return pred
16 def plus_court_chemin(G, s, v):
17 pred = chemin(G, s)
18 L = []
19 while v != s :
20 L.append(v)
21 v = pred[v]
22 L.append(s)
23 return L[ : : −1] # inverser le chemin
Graphes : Rappel 32 / 32