Terminale NSI

Chapitre 18 : Algorithmes sur les graphes

I - Rappels sur les graphes

Définition.

Un graphe est la donnée d’un ensemble de points appelés sommets et d’un ensemble de lignes
appelés arêtes reliant certains sommets entre eux.

Définition.

1) L’ordre d’un graphe est son nombre de sommets.

2) Le degré d’un sommet est le nombre d’arêtes issues de ce sommet.
3) Deux sommets sont dits adjacents ou voisins s’ils sont reliés par une arête.
4) Un sommet est dit isolé s’il n’est adjacent à aucun autre sommet du graphe.
5) Un graphe est dit complet si deux sommets quelconque distincts sont adjacents. Autrement
dit, un graphe est complet si et seulement si tous les couples de sommets sont reliés par une
arête.

E XEMPLE . On considère les graphes suivants :

Compléter le tableau suivant :

Graphe Ordre de A, A et B A et C Sommets Graphe

B et C sont-ils sont-ils isolés ? Si oui complet ?
adjacents ? adjacents ? le(s)quel(s) ?

Graphe
1

Graphe
2

Graphe
3

Page 1 sur 13
 Définition.

• Une chaîne ou un chemin est une liste ordonnée de sommets, deux sommets consécutifs étant
reliés par une arête. La longueur de la chaîne est le nombre d’arêtes parcourues dans cette
chaîne.
• Un cycle est une chaîne dont l’origine et l’extrémité de cette chaîne sont confondus et lorsque
toutes les arêtes sont distinctes.
• Un graphe est dit connexe s’il existe au moins une chaîne entre deux sommets quelconques de
ce graphe.
• Un graphe est dit pondéré si toutes les étiquettes des arêtes sont des réels positifs ou nuls. Ces
réels sont les poids des liaisons entre deux sommets.
• Le poids d’une chaîne est la somme des poids des arêtes composant la chaîne.

II - Algorithmes de parcours des graphes

L’idée ici est de visiter tous les sommets d’un graphe en partant d’un sommet quelconque.
Les algorithmes de parcours des graphes sont à la base de nombreux algorithmes très utilisés comme le
routage des paquets de données dans un réseau, chemin le plus cours d’une ville à une autre (Algorithme de
Dijkstra).
Il existe deux méthodes pour parcourir un graphe :
• le parcours en largeur d’abord
• le parcours en profondeur d’abord

1 - Le parcours en largeur d’abord.

a) Description de l’algorithme
Cet algorithme consiste à partir d’un sommet, de visiter le sommet puis ses enfants, puis les enfants de
ses enfants. Pour cela, on utilisera une file et une liste pour marquer les sommets visités. Considérons en
exemple ce graphe :

Le principe de l’algorithme est le suivant :

1) En entrée, on donnera un graphe G et un sommet de départ du graphe.
2) Pour le fonctionnement de l’algorithme, nous aurons besoin d’une liste de sommets visités SOM -
METS _ VISITES et d’une file f .

L’algorithme de parcours en largeur est alors :

Page 2 sur 13
Appliquons l’algo au graphe précédent en partant du sommet B .

Page 3 sur 13
Page 4 sur 13
Au final, le parcours en largeur du graphe est : [B,A,D,E,C,F,G,H].

b) Implémentation en Python
Voir TP1

2 - Le parcours en profondeur d’abord.

a) Description de l’algorithme
On considère un graphe et un sommet S de départ. L’algorithme de parcours en profondeur fonctionne
comme suit :
— On poursuit un chemin dans le graphe jusqu’à un cul-de-sac ou jusqu’à atteindre un sommet déjà
visité.
— On revient alors sur le dernier sommet où on pouvait suivre un autre chemin et on explore un autre
chemin.
Pour cela, on utilise une pile et deux listes pour marquer les sommets visités et les sommets fermés (qui n’ont
plus de voisins non visités) Prenons l’exemple du graphe précédent :

Le principe de l’algorithme est le suivant :

1) Un graphe G et un sommet de départ seront donnés en entrée.
Page 5 sur 13
 2) On considère deux listes sommets_visites pour les sommets visités et sommets_fermes pour les sommets
fermés. On aura également besoin d’une pile p.

Faisons tourner l’algorithme sur le graphe précédent en commençant par le sommet G.

Page 6 sur 13
Page 7 sur 13
Page 8 sur 13
Au final, on obtient donc le parcours [D,C,A,B,F,E,H,G]
R EMARQUE . Les choix dans la liste étant aléatoires, il y a plusieurs parcours possibles.

b) Implémentation en Python
. Voir TP2

III - Algorithme de Welsh et Powell

Cet algorithme consiste à colorer séquentiellement le graphe en visitant les sommets par ordre de degré
décroissant.
L’idée est que les sommets ayant beaucoup de voisins seront les plus difficiles à colorer. Il faut donc les
colorer en premier.
L’algorithme est le suivant :
1) Repérer le degré de chaque sommet.
2) Ranger les sommets par ordre de degrés décroissants (dans certains cas, il y a plusieurs possibilités).
3) Attribuer au premier sommet A de la liste une couleur.
4) Suivre la liste en attribuant la même couleur au premier sommet B qui ne soit pas adjacent à A.
5) Suivre si possible la liste jusqu’au prochain sommet C qui ne soit ni adjacent à A ni à B.
6) Continuer ainsi de suite jusqu’à c que la liste soit finie.
7) Prendre une deuxième couleur pour le premier sommet non encore colorié de la liste.
8) Répéter les opérations 4 à 7.
9) Continuer jusqu’à avoir colorié tous les sommets.
E XEMPLE . On considère le graphe suivant :

En utilisant l’algorithme de Welsh et Powell, colorier le graphe en utilisant un nombre minimal de

couleurs.
On trouve les degrés de chacun des sommets :
Sommet 1 2 3 4 5 6 7 8

Degré 1 3 2 2 3 1 2 2
Page 9 sur 13
 Trions par ordre de degrés décroissants.
Sommet 2 5 3 4 7 8 1 6

Degré 3 3 2 2 2 2 1 1

Couleur Noir Noir Rouge Bleu Rouge Bleu Rouge Rouge

R EMARQUE . L’algorithme de Welsh et Powell n’est pas optimale. En effet, pour colorier le graphe précédent, 2
couleurs auraient suffi :

IV - Algorithme de Dijkstra
Si on souhaite déterminer le plus court chemin entre deux sommets d’un graphe, on peut essayer d’énumérer
tous les chemins possibles entre ces deux sommets et calculer leurs longueurs. Mais, avec un graphe de taille
importante, ceci risque de devenir rapidement impossible.
De ce fait, pour répondre à ce problème, on utilise des algorithmes.
On étudiera ici que le cas particulier où les poids de tous les arcs sont des réels positifs.
En 1959, Edsger Wybe Dijkstra (mathématicien et informaticien néerlandais, 1930 - 2002) propose un
algorithme qui permet de déterminer le plus court chemin entre deux sommets d’un graphe connexe
pondéré (orienté ou non) dont le poids lié aux arêtes est positif.
L’algorithme dit de Dijkstra est basé sur le principe suivant :

Algorithme.

Supposons que l’on cherche le plus court chemin entre une ville A et une ville J .
Tout au long de l’algorithme, on va garder en mémoire le chemin le plus court depuis A pour
chacune des autres villes dans un tableau.
On répète ainsi toujours le même processus :
• On choisit le sommet accessible de distance minimale comme sommet à explorer.
• A partir de ce sommet, on explore ses voisins et on met à jour les distances pour chacun. On ne
met à jour la distance que si elle est inférieure à celle que l’on avait auparavant.
• On répète cela jusqu’à ce que l’on arrive au point d’arrivée ou jusqu’à ce que tous les sommets
aient été explorés.

R EMARQUE . Edsger Wybe Dijkstra a trouvé cet algo en 20 minutes alors qu’il cherchait la meilleure façon
d’aller de Rotterdam à Groningen à la terrasse d’un café.
Implémentons cela de manière formelle : Soit G un graphe connexe dont les arêtes sont pondérées par des
nombres positifs. On note :
• S la liste des sommets du graphe.
• s 0 le sommet du graphe à partir duquel on veut déterminer les plus courts chemins aux autres sommets.
• l (x ; y) le poids de l’arête entre deux sommets x et y.
• δs (x) la longueur d’un chemin du sommet s 0 au sommet x.
• V + (x) la liste des successeurs du sommet x.
• p(x) le prédécesseur du sommet x.
• X la liste des sommets restants à traiter.
Page 10 sur 13
• E la liste des sommets déjà traités.

Initialisation : Pour chaque x ∈ S faire

#On attribue un poids ∞ à chacun des sommets x

δs (x) ← ∞ # le poids du sommet s 0 est nul.

δs (x 0 ) ← 0

#La liste des sommets restants à traiter est initialisée à S.

X ←S

# la liste des sommets déjà traités est vide

E ←;

#On initialise la liste des sommets contenant le plus court chemin depuis s 0 .

chemin =[x 0 ]

Traitement : Tant que X ̸= ; faire # Tant que la liste des sommets restants à traiter n’est pas vide

Sélectionner dans la liste X le sommet x avec δs (x) minimum.

Retirer le sommet x de la liste X

Ajouter le sommet x à) la liste E

#On examine tous les successeurs y du sommet x qui ne sont pas traités

Pour chaque y ∈ V + (x) ∩ X faire :

Si δs (y) >δs (x) + l (x ; y) alors :

#la distance du sommet s 0 au sommet y est minimale

δs (y) ← δs (x) + l (x ; y)

# Le sommet x est le prédécesseur du sommet y

Insérer y dans chemin

p(y) ← x

Fin Si

Fin Pour

Fin Tant que

Sortie : Afficher d el t a s (y) et chemin

E XEMPLE . On considère le graphe connexe suivant représentant le réseau routier d’un région. Chaque arc
représente une route dont le poids est la distance en kilomètres entre deux sommets. Déterminer
l’itinéraire le plus court pour aller de A à H .

Pour faciliter la recherche du plus court chemin, on représente les résultats dans un tableau :

Page 11 sur 13
A B C D E F G H Sommet Commentaires
sélec-
tionné

0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ A(0) On affecte le poids 0 au sommet de

départ et on attribue
provisoirement un poids ∞ aux
autres sommets. Le sommet A de
poids à est donc sélectionné.

7(A) ∞ ∞ 14(A) ∞ ∞ ∞ B (7) Le sommet A de poids 0 ayant été

sélectionné, on marque
provisoirement les sommets
B (0 + 7 < ∞) et E (0 + 14 < ∞)
adjacents à A. On sélectionne le
sommet B de poids minimal. Le
prédécesseur de B est A.

15(B ) ∞ 14(A) ∞ ∞ ∞ E (14) Le sommet B de poids 7 ayant été

sélectionné, on marque
provisoirement le sommet
C (7 + 8 < ∞). Le sommet de poids
minimal étant E , on le marque.
Son prédécesseur est A.

15(B ) ∞ 33(E ) ∞ ∞ C (15) Le sommet E de poids 14 ayant été

sélectionné, on marque
provisoirement le sommet
F (14 + 19 < ∞). Le sommet de
poids minimal étant C , on le
marque. Son prédécesseur est B .

21(C ) 33(E ) 20(C ) 24(C ) G(17) Le sommet C de poids 15 ayant été

sélectionné, on marque
provisoirement le sommet
D(15 + 6 < ∞), G(15 + 5 < ∞) et
H (15 + 9 < ∞). Le sommet de
poids minimal étant G, on le
marque. Son prédécesseur est C .

21(C ) 24(G) 24(C ) D(21) Le sommet G de poids 20 ayant été

sélectionné, on marque
provisoirement le sommet
F (20 + 4 < 33). Le sommet de poids
minimal étant DS, on le marque.
Son prédécesseur est C .

24(G) 24(C ) F (24) On a sélectionné D. Aucun

sommet n’a un poids inférieur à
celui déjà existant. Le sommet de
poids minimal est ici F . Son
prédécesseur est G.

24(C ) C (24) On a sélectionné C . Le poids

existant de H est 24. Le sommet de
poids minimal est ici H . Son
prédécesseur est C .

Page 12 sur 13
Le chemin le plus court pour aller de A vers H est donc A → B → C → H . Sa distance minimale est
24 kilomètres.

Page 13 sur 13