Université Aboubekr Belkaïd – Tlemcen Département Génie Industriel

Faculté de Technologie Filière Génie Industriel

Année universitaire : 2025–2026 Niveau : Master 1

Programmation avancée sous Python

Chapitre 3 : Algorithmique des graphes

M. Bessenouci Hakim Nadhir

[Link]@[Link]

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

• Définitions & généralités
• Représentation des graphes
• Algorithmes d’exploration
◦ Parcours en largeur
◦ Parcours en profondeur
• Algorithmes d’optimisation
◦ Problèmes d’optimisation courants dans les graphes
◦ Exemples d’application concrètes
◦ Calcul de distances (plus cours chemin)
◦ Arbre couvrant le moins cher
◦ Optimisation de flot
• Exemple détaillé d’un algorithme d’optimisation (Dijkstra)
• Introduction à la bibliothèque matplotlib

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Définitions et généralités
Définition
On appelle graphe un ensemble fini V de points (sommets, nœuds ou
vertices en anglais) et un ensemble E de liens (edges en anglais), vu comme
une relation R sur V × V , reliant ces points.

G = (V , E )

Types de graphes
▶ Graphe non orienté : la relation est symétrique, c’est-à-dire que
l’existence d’un lien entre un sommet s1 et un sommet s2 est
réciproque. Un lien est alors appelé une arête.
▶ Graphe orienté : la relation n’est pas symétrique. On parle alors
d’un arc entre deux sommets.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Graphe non orienté simple
Définition
Un graphe non orienté simple G est un couple ordonné (V , E ), où :
▶ V est un ensemble fini non vide de sommets.
▶ E est un ensemble d’arêtes, où chaque arête est un ensemble non
ordonné de deux sommets distincts.

Propriétés
Dans un graphe non orienté simple :
▶ Il n’y a pas d’arêtes multiples entre deux sommets (au plus une
seule arête entre deux sommets donnés).
▶ Il n’y a pas de boucles, c’est-à-dire qu’une arête ne peut pas relier
un sommet à lui-même.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Exemple de graphe non orienté simple
Définition du graphe
Soit le graphe non orienté simple G = (V , E ) défini par :

V = {A, B, C , D, E , F , G}

E = {{A, B}, {A, C }, {B, D}, {C , D}, {C , E }, {E , F }, {F , G}, {D, G}}

Représentation graphique

A D G

C F

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Exemples d’erreurs dans un graphe non orienté
simple

Arêtes multiples interdites

Boucle interdite A B

Légende
▶ Boucle (auto-connexion) : un sommet relié à lui-même, interdite.
▶ Arêtes multiples : deux arêtes identiques entre les mêmes sommets,
interdites.
▶ Dans un graphe non orienté simple : aucune boucle ni arête
multiple.
M. Bessenouci Hakim Nadhir Programmation avancée sous Python
1.2 Graphe orienté simple
Définition
Un graphe orienté simple G est un couple ordonné G = (V , A), où :
▶ V est un ensemble fini non vide de sommets (ou nœuds).
▶ A est un ensemble d’arcs (ou flèches), où chaque arc est un couple
ordonné de deux sommets distincts.

Propriétés
▶ Les relations entre les sommets sont directionnelles.
▶ Il n’y a pas d’arcs multiples ayant la même direction entre deux
sommets.
▶ Il n’y a pas de boucles, c’est-à-dire qu’une arête ne peut pas relier
un sommet à lui-même.

Remarque
Les relations sont donc unidirectionnelles entre les sommets, sans redon-
dance ni boucle.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Exemple de graphe orienté simple
Définition du graphe
Soit le graphe orienté simple G = (V , A) défini par :

V = {A, B, C , D, E , F , G}

A = {(A, B), (A, C ), (B, D), (C , E ), (C , F ), (D, F ), (E , F ), (E , G), (F , G)}

Représentation graphique

A D G

C F

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Exemples d’erreurs dans un graphe orienté simple

Redondance interdite

Boucle interdite A B

Légende
▶ Boucle (auto-connexion) : un sommet relié à lui-même, interdite.
▶ Redondance : deux arcs identiques dans la même direction,
interdite.
▶ Dans un graphe orienté simple : aucune boucle ni arc multiple.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Terminologie – Graphe orienté
Relations entre arcs et sommets
▶ Deux arcs sont adjacents s’ils ont au moins une extrémité
commune.
▶ Pour un arc (x , y ) :
▶ y est successeur de x , et x est prédécesseur de y .
▶ x et y sont voisins ou adjacents.
▶ L’arc (x , y ) est incident extérieurement à x et incident
intérieurement à y .
▶ Demi-degré extérieur d + (x ) : nombre d’arcs sortants de x .
▶ Demi-degré intérieur d − (x ) : nombre d’arcs entrants vers x .
▶ Degré total d(x ) = d + (x ) + d − (x ).

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Arcs adjacents
Définition
Deux arcs sont dits adjacents s’ils partagent au moins un sommet com-
mun.

Exemple
Si l’on a les arcs (A, B) et (B, C ), ces deux arcs sont adjacents car ils
partagent le sommet B.

(A, B) (B, C )

A B C

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Successeur et prédécesseur
Définition
Pour un arc (x , y ) :
▶ y est le successeur de x .
▶ x est le prédécesseur de y .
▶ Les sommets x et y sont dits voisins ou adjacents.

(X , Y )

X Y

Prédécesseur Successeur

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Incidence des arcs et degré
Incidence des arcs
Pour un arc (X , Y ) :
▶ Il est incident extérieurement à X (arc sortant),
▶ Il est incident intérieurement à Y (arc entrant).

Demi-degré et degré total

▶ Demi-degré extérieur d + (X ) : nombre d’arcs sortants de X .
▶ Demi-degré intérieur d − (X ) : nombre d’arcs entrants vers X .
▶ Degré total : d(X ) = d + (X ) + d − (X ).

(X , Y )
Y
d + (X ) = 1
X
d − (X ) = 1 (Z , X )
Degré total d(X ) = 2 Z

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Terminologie – Graphe non orienté
Arêtes et sommets
▶ Une arête [x , y ] a pour extrémités x et y .
▶ x et y sont voisins ou adjacents.
▶ Le degré d’un sommet x est le nombre d’arêtes incidentes à x .

Exemple graphique

d(C ) = 3
[D, C ]
D C
d(D) = 1
[C , A] [B, C ]

[A, B]
A B
d(A) = 2 d(B) = 2

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Mesures sur un graphe
Mesures principales
▶ Ordre : nombre de sommets du graphe, noté N.
▶ Taille : nombre d’arêtes ou d’arcs.
▶ Degré d’un sommet s pour un graphe non orienté :est le nombre
d’arêtes qui relient ce sommet à d’autres sommets.
▶ Degré d’un sommet s pour un graphe orienté :
▶ Demi-degré extérieur : d + (s), nombre d’arcs sortants de s.
▶ Demi-degré intérieur : d − (s), nombre d’arcs entrants vers s.
▶ Degré total : d(s) = d + (s) + d − (s).
▶ Graphe connexe : il existe un chemin entre toute paire de sommets
distincts.
▶ Graphe déconnecté : le graphe n’est pas connexe.
▶ Graphe complet : tous les sommets sont reliés entre eux deux à
deux.
N × (N − 1)
Nombre d’arêtes (non orienté) =
2

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Densité et diamètre d’un graphe
Densité
▶ La densité D d’un graphe indique son niveau de connectivité.
▶ Rapport entre le nombre d’arêtes existantes et le nombre maximal
possible :
2·A
D=
N · (N − 1)
▶ Graphe creux : D ≈ 0, peu d’arêtes.
▶ Graphe dense : D ≈ 1, beaucoup d’arêtes.

Diamètre
▶ Le diamètre d’un graphe est la plus grande distance entre deux
sommets quelconques.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Mesures sur le graphe exemple
Exemple graphique

d(C ) = 3
[D, C ]
D C
d(D) = 1
[C , A] [B, C ]
[A, B]

A B
Mesures du graphe
▶ Ordre : N = 4 sommets d(A) = 2 d(B) = 2
▶ Taille : |E | = 4 arêtes
▶ Degré des sommets : d(A) = 2, d(B) = 2, d(C ) = 3, d(D) = 1
2|E |
▶ Densité : D = = 0.667
N(N − 1)
▶ Diamètre : 2 (plus longue distance entre deux sommets)
▶ Connexité : graphe connexe
▶ Complet : non, il faudrait 6 arêtes

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Graphe pondéré
Définition
Un graphe pondéré est un graphe dans lequel chaque arête (ou arc) est
associée à une valeur numérique, appelée poids ou coût. Ce poids peut
représenter une distance, un temps, un coût ou une capacité.

40 60

A B
50

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Longueur d’un chemin
Définition
Dans un graphe pondéré, la longueur d’un chemin est la somme des
poids des arêtes (ou arcs) qui composent ce chemin.
k−1
X
L(P) = w (xi , xi+1 )
i=1

où P = (x1 , x2 , . . . , xk ) est le chemin, et w (xi , xi+1 ) est le poids de l’arête

reliant xi à xi+1 .

Exemple
Considérons le chemin A → B → C dans le graphe ci-dessous :

L(P) = w (A, B) + w (B, C ) = 5 + 3 = 8

L(A → B → C ) = 8

5 3
A B C

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Applications des graphes
Exemples d’utilisation
▶ Un graphe représente les relations entre les sommets. C’est la
représentation naturelle pour les réseaux sociaux (sommets =
personnes) ou les réseaux internet (sommets = routeurs).
▶ Pages web : chaque page est un sommet et le lien d’une page A
vers une page B est représenté par une arête orientée. Le Web peut
ainsi être modélisé par un graphe. Les moteurs de recherche utilisent
ce type de représentation pour organiser et classer les pages.
▶ Plan de métro : les stations représentent les sommets du graphe,
reliées entre elles par une ligne de métro (les arêtes).
▶ Plan routier : les marqueurs (villes, intersections) sont reliés par des
routes. Contrairement au graphe du métro, le graphe routier est
pondéré : chaque arête indique une distance (en km). La longueur
d’un chemin correspond alors à la somme des longueurs de ses
arêtes.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Activité

Pour chacun des exemples suivants, choisissez le type de graphe adapté

parmi : graphe orienté / non orienté, pondéré, non connexe, sans
cycle. Précisez également ce que représentera :
▶ un sommet,
▶ une arête (ou un arc dans le cas orienté).

Exemples
1. Un réseau de villes reliées par des routes, comportant l’information
de leur longueur (en km). Toutes les villes sont reliées par au moins
une route. Ces routes sont en double sens.
2. Un réseau social de type Facebook, où les participants ont des liens
d’amitié réciproques. Les sous-réseaux ne sont pas tous reliés entre
eux (au moins deux groupes indépendants).
3. Un réseau social de type Twitter, où les participants ont des
followers. Cette relation n’est pas réciproque : un utilisateur peut
suivre un autre sans être suivi en retour.
M. Bessenouci Hakim Nadhir Programmation avancée sous Python
Solutions
1. Réseau de villes (routes)
▶ Type : non orienté, pondéré, connexe.
▶ Sommets : villes.
▶ Arêtes : routes (double sens), poids = longueur (km).

2. Réseau social (Facebook)

▶ Type : non orienté,non connexe (plusieurs communautés).
▶ Sommets : personnes / utilisateurs.
▶ Arêtes : amitié (réciproque), souvent non pondérée.

3. Réseau social (Twitter)

▶ Type : orienté (arcs followers), non connexe.
▶ Sommets : utilisateurs.
▶ Arcs : (u → v ) signifie « u suit v ».

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

1. Représentation des graphes
Introduction
Il existe plusieurs modes de représentation permettant de stocker et
manipuler un graphe en mémoire. Le choix de la représentation dépend du
type de graphe (orienté, non orienté, pondéré, etc.) et des opérations à
effectuer.

Principales représentations
▶ Liste des voisins (ou d’adjacence) : applicable à tous les types de
graphes.
▶ Matrice d’adjacence : représentation universelle, utile pour les
petits graphes.
▶ Matrice de distance : adaptée aux graphes pondérés.
▶ Dictionnaire : utilisé pour les graphes étiquetés.
▶ Listes de successeurs/prédécesseurs : conçues pour les graphes
orientés.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Liste d’adjacence
Définition
On appelle liste d’adjacence (ou liste de voisins) du graphe une liste
de listes où la i ème sous-liste contient la liste des sommets adjacents au
sommet i. L’ordre des sommets dans chaque sous-liste est arbitraire.

Principe de représentation en Python

Une représentation en Python correspond à une liste de listes L, où chaque
élément L[i] contient la liste des sommets voisins du sommet i.

Exemple
Pour un graphe non orienté comportant les arêtes : (0, 1), (0, 2), (1, 2) et (2, 3),
on obtient :
L = [[1, 2], [0, 2], [0, 1, 3], [2]]

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Exemple : Représentation d’un graphe par une liste
d’adjacence
Représentation graphique Liste d’adjacence
B correspondante

A G


A : [B, C ]
D 


B : [A, D, G]
F 
C : [A, E , F ]


L= D : [B, F ]
C 

E : [C , F ]


F : [C , D, E , G]



E 
G : [B, F ]

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Matrice d’adjacence
Définition
Pour un graphe non orienté simple G avec n sommets, la matrice d’adja-
cence M est une matrice carrée de taille n × n, où l’élément aij est défini
comme suit :
(
1 si une arête existe entre les sommets i et j,
aij =
0 sinon.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Exemple : Matrice d’adjacence
Représentation graphique
Matrice d’adjacence
B correspondante
A G 0 1 1 0 0 0 0

D
F 1 0 0 1 0 0 1
1 0 0 0 1 1 0
 
0 1
M= 0 0 0 1 0

C 0 0 1 0 0 1 0
0 0 1 1 1 0 1
 
E 0 1 0 0 0 1 0

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Représentation d’un graphe orienté par une matrice
d’adjacence
Représentation graphique
Matrice d’adjacence
B correspondante
A G 0 1 0 0 0 0 0

D
F 0 0 0 1 0 0 0
1 0 0 0 1 0 0
 
0 0
M= 0 0 0 1 0

C 0 0 0 0 0 1 0
0 0 1 0 0 0 1
 
E 0 1 0 0 0 0 0

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Matrice des distances entre sommets
Définition
Pour un graphe pondéré, la matrice d’adjacence peut être adaptée en rem-
plaçant les valeurs 1 par le poids de l’arête correspondante. L’élément
aij indique donc la distance (ou le coût) entre les sommets i et j.
À partir de cette matrice, on peut calculer le diamètre du graphe, c’est-
à-dire la plus grande longueur minimale entre deux sommets.

Exemple
 
0 15 18 0 0
15 0 30 20 0
 
18
M= 30 0 10 10
0 20 10 0 0
0 0 10 0 0
Ici, M12 = 15 indique que la distance entre le sommet 1 et le sommet 2
est de 15 unités.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Graphe pondéré : représentation graphique et liste
d’adjacence
Représentation graphique avec poids Liste d’adjacence
sur les arcs pondérée
B 6 correspondante
2
1
A G

 A : [(B, 2), (C , 5)]
D 1 

 B : [(D, 1), (G, 6)]
1 

5 F 
C : [(E , 3), (F , 2)]


2 4 L= D : [(F , 1)]
C 

 E : [(F , 4)]


3 F : [(G, 1)]



E 
G : []

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Graphe pondéré et matrice d’adjacence
Graphe pondéré Matrice d’adjacence
B 6 pondérée
2
1
A G  
0 2 5 0 0 0 0
D 1 0
1 0 0 1 0 0 6
5 F 
0 0 0 0 3 2 0

 
2 4 0
M= 0 0 0 0 1 0
C

0 0 0 0 0 4 0
 
3 0 0 0 0 0 0 1
E 0 0 0 0 0 0 0

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Graphes avec étiquettes
Définition
Pour un graphe avec étiquettes, chaque sommet est identifié par une clé
unique. On peut utiliser un dictionnaire Python pour représenter les som-
mets et leurs voisins :

D = {’a’ : [′ b ′ ,′ c ′ ], ’b’ : [′ a′ ,′ c ′ ,′ d ′ ], ’c’ : [′ a′ ,′ b ′ ,′ d ′ ], ’d’ : [′ b ′ ,′ c ′ ]}

Ici, les clés sont les étiquettes des sommets, et les valeurs représentent la
liste des sommets adjacents.

a d

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Liste de successeurs
Définition
La liste de successeurs est particulièrement adaptée aux graphes orientés.
Pour chaque sommet, on liste uniquement les sommets vers lesquels il a
un arc sortant.

Exemple
Pour le même graphe, si l’on considère des arcs orientés :

S = {’a’ : [′ b ′ ,′ c ′ ], ’b’ : [′ c ′ ,′ d ′ ], ’c’ : [′ d ′ ], ’d’ : []}

Ici, ’a’ a pour successeurs ’b’ et ’c’, ’d’ n’a aucun successeur.

a d

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Liste chaînée des successeurs

Concept
On peut représenter un graphe avec une liste chaînée des successeurs
(sommet ⇒ liste de sommets liés suivants) :
▶ 0 ⇒ 1, 2 (Le sommet 0 a pour successeurs les sommets 1 et 2)
▶ 1 ⇒ 2, 3
▶ 2⇒3
▶ 3⇒2
Chaque sommet peut avoir plusieurs successeurs. Cette structure est adap-
tée aux graphes orientés.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Implémentation Python

Classe Sommet avec plusieurs successeurs

class Sommet:
def __init__(self, val, suiv1=None, suiv2=None, suiv3=None):
[Link] = val # étiquette du sommet
self.suiv1 = suiv1
self.suiv2 = suiv2
self.suiv3 = suiv3

# Exemple de sommets
S2 = Sommet(2)
S1 = Sommet(1)
S0 = Sommet(0, 1, 2)

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Classe Sommet avec successeurs pondérés
Définition en Python
class Sommet:
def __init__(self, val):
[Link] = val # Étiquette du sommet
[Link] = {} # Dictionnaire {sommet_suivant:

def ajouter_successeur(self, sommet, poids=1):

[Link][sommet] = poids

def __str__(self):
return f"{[Link]}: {[Link]}"

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Classe Graphe utilisant la classe Sommet

class Graphe:
def __init__(self):
[Link] = {} # Dictionnaire {val: Sommet}

def ajouter_sommet(self, val):

if val not in [Link]:
[Link][val] = Sommet(val)

def ajouter_arc(self, source, destination, poids=1):

self.ajouter_sommet(source)
self.ajouter_sommet(destination)
[Link][source].ajouter_successeur(destination, poids)

def liste_adjacence(self):
L = {}
for val, sommet in [Link]():
L[val] = [(s, p) for s, p in [Link]()]
return L

def afficher(self):
for val, sommet in [Link]():
print(f"{val}: {[Link]}")
M. Bessenouci Hakim Nadhir Programmation avancée sous Python
Exemple d’utilisation de la classe Graphe

Code Python
# Création du graphe
G = Graphe()
G.ajouter_arc(’A’, ’B’, 2)
G.ajouter_arc(’A’, ’C’, 5)
G.ajouter_arc(’B’, ’D’, 1)
G.ajouter_arc(’C’, ’E’, 3)
G.ajouter_arc(’C’, ’F’, 2)
G.ajouter_arc(’D’, ’F’, 1)
G.ajouter_arc(’E’, ’F’, 4)
G.ajouter_arc(’B’, ’G’, 6)
G.ajouter_arc(’F’, ’G’, 1)

print("Liste d’adjacence pondérée du graphe :")

[Link]()

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Algorithmes d’exploration
Définition
Parcourir (ou explorer) un graphe consiste à visiter l’ensemble de ses som-
mets. Ce parcours produit un ordre de visite dépendant de l’algorithme
utilisé. Deux méthodes principales sont généralement employées :
▶ le parcours en largeur d’abord (BFS) ;
▶ le parcours en profondeur d’abord (DFS).

Objectifs de l’exploration d’un graphe

Le parcours d’un graphe peut servir à :
▶ détecter des cycles dans le graphe ;
▶ rechercher le plus court chemin entre deux sommets ;
▶ calculer la distance entre deux sommets ;
▶ etc.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Algorithmes d’exploration
Exemples d’applications
Les algorithmes d’exploration sont utilisés dans de nombreux domaines,
tels que :
▶ le routage de paquets dans un réseau ;
▶ la recherche du chemin le plus court entre deux villes (GPS) ;
▶ la résolution de labyrinthes ou de jeux de parcours ;
▶ diverses tâches d’intelligence artificielle et d’optimisation.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Parcours en largeur (BFS)
Définition
Pour le parcours en largeur (BFS pour Breadth-First Search), on com-
mence à partir d’un nœud donné et l’on explore tous ses voisins avant
d’explorer les voisins de ces voisins. Autrement dit, l’algorithme visite le
graphe niveau par niveau, en s’étendant d’abord en largeur.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

2.1.1 Principe de l’algorithme BFS
Principe de l’algorithme
Le parcours en largeur repose sur une file (queue) utilisant le principe FIFO
(First-In First-Out), garantissant que les nœuds découverts en premier sont
explorés en premier.

Principe de l’algorithme BFS

▶ On choisit un sommet de départ ;

▶ On l’enfile dans la file ;
▶ Tant que la file n’est pas vide :
▶ On défile son premier élément ;
▶ S’il n’a pas encore été visité :
▶ On le marque comme visité ;
▶ On enfile tous ses voisins non encore visités ;
▶ Sinon, on passe à l’itération suivante.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Exemple de parcours de graphe en largeur (BFS) à
partir du sommet A

Graphe d’origine
Parcours BFS depuis A
B
A
A G
D
F B C

C
D G E F
E

Ordre du parcours BFS (depuis A)

A→B→C→D→G→E→F

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Exemple de parcours de graphe en largeur (BFS) à
partir du sommet A

Graphe non orienté

Parcours BFS depuis A
B
A
A G
D
F B C

C
D G E F
E

Ordre du parcours BFS (depuis A)

A→B→C→D→G→E→F

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Arbre de recherche généré à partir du graphe
Ci-dessous, quelques termes utilisés dans les arbres de recherche :

▶ Nœud initial : point de départ de

la recherche (A).
▶ Nœud but : objectif(s) de la
recherche (F).
▶ Feuilles : nœuds sans enfants (ex :
D, G, E, F).
▶ Parent : nœud qui possède des A
enfants (ex : B est parent de D et
G).
▶ Enfants : nœuds issus d’un parent
B C
(ex : D et G sont les enfants de B).
▶ Voisins : nœuds partageant le
même parent (ex : D et G sont
voisins). D G E F
▶ Voisins de degré n : L’ensemble
des nœuds v qui sont atteignables
depuis un nœud source u
spécifique en suivant exactement n
arêtes, via le chemin le plus court.
(ex : D et F sont voisins de degré
2)

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Pseudo-code BFS avec coloration des sommets
VARIABLES
G : un graphe
s : noeud (origine)
u : noeud
v : noeud
f : file (initialement vide)
// initialement [Link] = blanc
DEBUT
[Link] ← noir
enfiler(s, f)
tant que f non vide :
u ← defiler(f)
pour chaque sommet v adjacent au sommet u :
si [Link] != noir alors
[Link] ← noir
enfiler(v, f)
fin si
fin pour
fin tant que
FIN

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Python – BFS avec coloration des sommets

def parcours_largeur (G , s ) :
# initialement u . couleur = blanc
couleur = {}
for u in G :
couleur [ u ] = " blanc "
f = [] # file vide
couleur [ s ] = " noir "
f . append ( s ) # enfiler (s , f )
while len ( f ) != 0:
u = f . pop (0) # u = defiler ( f )
# pour chaque sommet v adjacent au sommet u
for v in G [ u ]:
if couleur [ v ] != " noir "
couleur [ v ] = " noir "
f . append ( v )
return couleur

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Exemple d’implémentation BFS en Python

def parcours_larg ( graphe , debut ) :

visites ={}
file = [ debut ]
while len ( file ) > 0:
s = file . pop (0)
if s in visites :
# si s d é j à visit é on passe à l ' i t e r a t i o n
# suivante
continue
visites [ s ]= True
for voisin in graphe [ s ]:
if voisin not in visites :
file . append ( voisin )
return visites

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Parcours en profondeur (DFS)
Définition
Le parcours en profondeur (DFS pour Depth-First Search) explore un
graphe en allant aussi loin que possible dans une branche avant de re-
venir en arrière. Autrement dit, l’algorithme visite le graphe en priorité en
profondeur.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

2.2.1 Principe de l’algorithme DFS
Principe de l’algorithme
Le parcours en profondeur (DFS pour Depth-First Search) utilise une pile
(stack) fonctionnant selon le principe LIFO (Last-In First-Out), ce qui
permet de plonger dans la profondeur du graphe. En stockant les sommets
à visiter dans une pile, on s’assure que ce sont les derniers sommets décou-
verts qui seront visités en premier. Une version abstraite de l’algorithme
de parcours en profondeur est fournie ci-dessous.

Principe de l’algorithme DFS

▶ On choisit un sommet de départ ;

▶ On l’empile dans la pile ;
▶ Tant que la pile n’est pas vide :
▶ On dépile le sommet du dessus ;
▶ S’il n’a pas encore été visité :
▶ On le marque comme visité ;
▶ On empile tous ses voisins non visités ;
▶ Sinon, on continue l’itération suivante.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Exemple de parcours de graphe en profondeur
(DFS) à partir du sommet A

Parcours DFS depuis A

Graphe d’origine
A
B
B C
A G
D
F D E

C
F
E
G

Ordre du parcours DFS (depuis A)

A→B→D→F→G→C→E
M. Bessenouci Hakim Nadhir Programmation avancée sous Python
Exemple de parcours de graphe en profondeur
(DFS) à partir du sommet A

Parcours DFS depuis A

Graphe non orienté A

B
B
A G
D D
F
F
C

E C

Ordre du parcours DFS (depuis A) E

A→B→D→F→C→E→G
G
M. Bessenouci Hakim Nadhir Programmation avancée sous Python
Pseudo-code DFS avec coloration des sommets
VARIABLES
G : un graphe
s : noeud (origine)
u : noeud
v : noeud
p : pile (initialement vide)
// initialement [Link] = blanc
DEBUT
empiler(s, p)
tant que p non vide :
u ← depiler(p)
si [Link] = blanc alors
[Link] ← noir
pour chaque v adjacent à u :
si [Link] = blanc alors
empiler(v, p)
fin si
fin pour
fin si
fin tant que
FIN
M. Bessenouci Hakim Nadhir Programmation avancée sous Python
Python – DFS avec coloration des sommets

def par c o u rs _ p ro fondeur (G , s ) :

# initialement u . couleur = blanc
couleur = {}
for u in G :
couleur [ u ] = " blanc "
p = [] # pile vide
p . append ( s ) # empiler (s , p )
while len ( p ) != 0:
u = p . pop () # depiler ( p )
if couleur [ u ] == " blanc " :
couleur [ u ] = " noir "
for v in G [ u ]:
if couleur [ v ] == " blanc " :
p . append ( v )
return couleur

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Exemple d’implémentation DFS en Python

def parcours_prof ( graphe , debut ) :

visites = {}
pile = [ debut ]
while len ( pile ) > 0:
s = pile . pop ()
if s in visites :
continue
visites [ s ] = True
for voisin in graphe [ s ]:
if voisin not in visites :
pile . append ( voisin )
return visites

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Algorithmes d’optimisation

En théorie des graphes, les algorithmes d’optimisation permettent de trou-

ver la meilleure solution possible à un problème modélisé sous forme de
graphe. Cela implique de maximiser ou minimiser une certaine valeur en
fonction de l’objectif et des contraintes du problème. Les graphes sont des
outils puissants pour modéliser des réseaux complexes, et l’optimisation
est essentielle pour résoudre de nombreux problèmes concrets dans divers
domaines.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Problèmes d’optimisation courants dans les graphes
Les problèmes suivants sont des exemples classiques d’optimisation résolus par
des algorithmes spécifiques :
1. Problème du plus court chemin : Calculer le chemin le plus court entre
deux sommets ou entre un sommet source et tous les autres sommets
d’un graphe pondéré (algorithmes : Dijkstra pour poids non négatifs,
Bellman-Ford pour poids négatifs).
2. Problème du voyageur de commerce : Trouver le plus court circuit
hamiltonien qui passe exactement une fois par chaque sommet d’un
graphe. C’est un problème difficile à résoudre de manière exacte pour les
grands graphes, souvent traité par des algorithmes d’approximation.
3. Problème de l’arbre couvrant de poids minimum (ACPM) : Trouver un
sous-graphe qui connecte tous les sommets avec un poids total minimal
(algorithmes : Kruskal, Prim, Sollin).
4. Problème de flot maximum : Déterminer le débit maximal d’un flux que
l’on peut faire circuler de la source au puits dans un réseau (algorithme :
Ford-Fulkerson).
5. Problème de coloration de graphe : Attribuer un nombre minimal de
couleurs aux sommets d’un graphe de manière que deux sommets reliés
n’aient jamais la même couleur. Ce problème est souvent utilisé pour
l’allocation de ressources ou la planification.
M. Bessenouci Hakim Nadhir Programmation avancée sous Python
Exemple de graphe pondéré orienté

1
8
B D F
5 6 4 6
1

A 6 1 3 6 3 H
10 2
1
7
2 5 1
C E G
5 1

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Exemple du plus court chemin

1
8
B D F
5 6 4 6
1

A 6 1 3 6 3 H
10 2
1
7
2 5 1
C E G
5 1

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Exemple d’un circuit hamiltonien

1
8
B D F
5 4 6
6
1

A 6 1 3 6 3 H
10 2
1
7
2 5 1
C E G
5 1

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Exemple de graphe pondéré non-orienté

8 1
B D F
5 6 6
1

A 6 3 6 H
10 1 2

C E G
5 1

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Exemple d’un Arbre couvrant de poids minimal

8 1
B D F
5 6
6
1

A 6 3 6 H
10 1 2

C E G
5 1

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Exemple de graphe pondéré non-orienté –
Coloration

B D F

A H

C E G

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Exemples d’applications concrètes

Les algorithmes d’optimisation sur les graphes sont utilisés dans de nom-
breuses applications pratiques :
▶ Réseaux routiers et GPS : déterminer l’itinéraire le plus rapide ou
le plus court en modélisant les intersections comme des sommets et
les routes comme des arêtes pondérées.
▶ Logistique et transport : optimiser les tournées de véhicules pour
la livraison de marchandises afin de minimiser le temps ou le coût de
déplacement.
▶ Réseaux informatiques : améliorer les chemins de données et
acheminer les informations de manière optimale pour maximiser
l’efficacité.
▶ Planification urbaine : concevoir des réseaux de transport efficaces.
▶ Réseaux sociaux : analyser les connexions entre les utilisateurs.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Algorithme de Dijkstra
Description générale
L’algorithme de Dijkstra est utilisé pour trouver le chemin le plus court
dans un graphe pondéré. Il fonctionne en initialisant la distance de départ
à 0 et les autres à l’infini, puis en parcourant itérativement le graphe pour
mettre à jour les distances les plus courtes vers chaque sommet, jusqu’à
ce que tous les sommets aient été traités.

Objectif
Trouver le plus court chemin depuis un sommet source vers tous les autres
sommets d’un graphe pondéré. On peut aussi l’utiliser pour calculer un
plus court chemin entre un sommet de départ et un sommet d’arrivée.

Fonctionnement
L’algorithme explore le graphe en visitant les sommets dans l’ordre crois-
sant de leur distance par rapport à la source. Il met à jour les distances
des sommets voisins à chaque étape.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Principe de l’algorithme de Dijkstra
Initialisation
▶ Créez une structure de données pour stocker les distances les plus courtes.
▶ Fixez la distance du sommet de départ à 0 et toutes les autres distances à
l’infini.
▶ Créez un ensemble pour les sommets visités et un ensemble pour les
sommets non visités (ou initialisez un dictionnaire des précurseurs).

Itération
1. Tant qu’il existe des sommets non visités :
▶ Sélectionnez le sommet non visité avec la plus petite distance
actuelle (nœud actuel).
▶ Pour chaque voisin du nœud actuel :
▶ Calculez la distance cumulée du nœud actuel vers ce voisin.
▶ Si cette distance est inférieure à la distance actuelle du voisin, mettez
à jour la distance.
▶ Marquez le nœud actuel comme visité et retirez-le de l’ensemble des
sommets non visités.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Algorithme de Dijkstra
Pseudo-code
1: function DIJKSTRA(G, w, s)
2: for tout v ∈ G do
3: v .dist ← +∞ // initialisation de la distance
4: v .pred ← NIL // initialisation du prédécesseur
5: end for
6: [Link] ← 0 // distance de la source
7: E ← ∅ // nœuds visités
8: F ← G.S // file des nœuds à visiter
9: while F ̸= ∅ do
10: u ← Extraire-Min(F )
11: E ← E ∪ {u} // ajouter u aux nœuds visités
12: for tout v ∈ Adj[u] do
13: if v .dist > [Link] + w (u, v ) then
14: v .dist ← [Link] + w (u, v )
15: v .pred ← u // mettre à jour le prédécesseur
16: end if
17: end for
18: // E = {nœuds visités}, F = {nœuds à visiter}
19: end while
20: return distance, predecessor

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Algorithme de Dijkstra (Python)
Code Python
import heapq

def dijkstra ( graphe , source ) :

distances = { n : float ( ' inf ' ) for n in graphe .
sommets }
pred = { n : None for n in graphe . sommets }
distances [ source ] = 0
pq = [(0 , source ) ]
while pq :
dist_u , u = heapq . heappop ( pq )
for v , w in graphe . sommets [ u ]. successeurs .
items () :
if distances [ u ] + w < distances [ v ]:
distances [ v ] = distances [ u ] + w
pred [ v ] = u
heapq . heappush ( pq , ( distances [ v ] , v ) )

return distances , pred

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

3.3 Arbre couvrant de poids minimum (ACPM)
Définition
En théorie des graphes, un arbre couvrant de poids minimum (ACPM),
appelé aussi arbre couvrant le moins cher, est un sous-ensemble d’arêtes
d’un graphe pondéré qui relie tous les sommets sans former de cycle, et
dont la somme des poids est la plus faible possible. Les algorithmes de
Kruskal et Prim sont couramment utilisés pour trouver un ACPM dans
un graphe connexe et non-orienté.

Algorithmes classiques
▶ Algorithme de Kruskal : sélectionne les arêtes par ordre de poids
croissant, en ajoutant une arête si elle ne forme pas de cycle avec les
arêtes déjà choisies.
▶ Algorithme de Prim : commence par un sommet arbitraire et
construit l’arbre en ajoutant progressivement l’arête de poids
minimum qui relie un sommet de l’arbre à un sommet extérieur,
jusqu’à inclure tous les sommets.

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Algorithme de Dijkstra appliqué à un graphe pondéré non
orienté
Étape 0

8 1 Sommet Dist. Pred.

B D F
5 A 0 –
6 0 6 B ∞ –
C ∞ –
A 6 3 6 H D ∞ –
E ∞ –
1
10 F ∞ –
2
G ∞ –
C E G H ∞ –
5 1

A,0

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Algorithme de Dijkstra appliqué à un graphe pondéré non
orienté
Étape 1

8 1 Sommet Dist. Pred.

B D F
5 A 0 –
6 0 6 B ∞ –
C ∞ –
A 6 3 6 H D ∞ –
E ∞ –
1
10 F ∞ –
2
G ∞ –
C E G H ∞ –
5 1

A,0

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Algorithme de Dijkstra appliqué à un graphe pondéré non
orienté
Étape 2

8 1 Sommet Dist. Pred.

B D F
A 0 –
0+5 6 B 5 A
6 0
C ∞ –
A 6 3 6 H D ∞ –
E ∞ –
1
10 F ∞ –
2
G ∞ –
C E G H ∞ –
5 1

B,5

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Algorithme de Dijkstra appliqué à un graphe pondéré non
orienté
Étape 3

8 1 Sommet Dist. Pred.

B D F
A 0 –
0+5 6 B 5 A
6 0
C 10 A
A 6 3 6 H D ∞ –
E ∞ –
1
0+10 F ∞ –
2
G ∞ –
C E G H ∞ –
5 1

B,5 C,10

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Algorithme de Dijkstra appliqué à un graphe pondéré non
orienté
Étape 4

8 1 Sommet Dist. Pred.

B D F
A 0 –
0+5 6 B 5 A
6 0
C 10 A
A 6 3 6 H D 13 B
E 11 B
1
0+10 F ∞ –
2
G ∞ –
C E G H ∞ –
5 1

B,5 C,10 D,13 E,11

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Algorithme de Dijkstra appliqué à un graphe pondéré non
orienté
Étape 5

8 1 Sommet Dist. Pred.

B D F
A 0 –
0+5 6 B 5 A
6 0
C 10 A
A 6 3 6 H D 11 C
E 11 B
1
0+10 F ∞ –
2
G ∞ –
C E G H ∞ –
5 1

C,10 D,11 E,11

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Algorithme de Dijkstra appliqué à un graphe pondéré non
orienté
Étape 6

8 1 Sommet Dist. Pred.

B D F
A 0 –
0+5 6 B 5 A
6 0
C 10 A
A 6 3 6 H D 11 C
E 11 B
1
0+10 F 12 D
2
G ∞ –
C E G H ∞ –
5 1

D,11 E,11 F,12

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Algorithme de Dijkstra appliqué à un graphe pondéré non
orienté
Étape 7

8 1 Sommet Dist. Pred.

B D F
A 0 –
0+5 6 B 5 A
6 0
C 10 A
A 6 3 6 H D 11 C
E 11 B
1
0+10 F 11 E
2
G 12 E
C E G H ∞ –
5 1

E,11 F,11 G,12

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Algorithme de Dijkstra appliqué à un graphe pondéré non
orienté
Étape 8

8 1 Sommet Dist. Pred.

B D F
A 0 –
0+5 6 B 5 A
6 0
C 10 A
A 6 3 6 H D 11 C
E 11 B
1
0+10 F 11 E
2
G 12 E
C E G H 17 F
5 1

F,11 G,12 H,17

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Algorithme de Dijkstra appliqué à un graphe pondéré non
orienté
Étape 9

8 1 Sommet Dist. Pred.

B D F
A 0 –
0+5 6 B 5 A
6 0
C 10 A
A 6 3 6 H D 11 C
E 11 B
1
0+10 F 11 E
2
G 12 E
C E G H 14 G
5 1

G,12 H,14

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Algorithme de Dijkstra appliqué à un graphe pondéré non
orienté
Étape 10

8 1 Sommet Dist. Pred.

B D F
A 0 –
0+5 6 B 5 A
6 0
C 10 A
A 6 3 6 H D 11 C
E 11 B
1
0+10 F 11 E
2
G 12 E
C E G H 14 G
5 1

H,14

M. Bessenouci Hakim Nadhir Programmation avancée sous Python

Algorithme de Dijkstra appliqué à un graphe pondéré non
orienté
Étape 10

8 1 Sommet Dist. Pred.

B D F
A 0 –
5 6 0 6 B 5 A
C 10 A
A 6 3 6 H D 11 C
E 11 B
1
10 F 11 E
2
G 12 E
C E G H 14 G
5 1

M. Bessenouci Hakim Nadhir Programmation avancée sous Python