Niveau : Terminale générale, enseignement de spécialité NSI
Les graphes sont employés par exemple par les GPS pour trouver le chemin le plus court entre deux villes
On a des sommets et des arrêtes ou arcs si la liaison n'est pas bidirectionnelle. Les sommets de notre graphe se sont les villes, les arrêtes représentent le poids : ici, la distance séparant deux villes entre elles.
Pour aller à Mulhouse à Nancy, quel sera le chemin le plus court :
Les successeurs de Mulhouse sont : Strasbourg, Nancy, Epinal et Vesoul
Les prédécesseurs de Vesoul sont : Nancy, Epinal et Mulhouse qui
sont également ses successeurs.
Pour trouver le chemin le plus court dans ce graphe il existe
l'algorithme de Dijkstra ou Prim traité à la fin du chapitre.
Oublions un moment le poids des arrêtes. La matrice d'adjacence
permet de répertorier les prédécesseurs et les successeurs de
chaque sommet. De Strasbourg je peux aller directement vers Mulhouse,
Epinal ou Nancy
mais pas Vesoul. Donc Mulhouse, Epinal et Nancy sont les successeurs de
Strasbourg. On place la valeur 1 si c'est le successeur, 0 si ce n'est
pas le successeur. On obtient la matrice suivante :
Pour connaître :
![]() |
Dans les piles, on empile les données commne une pile de livres La première donnée qui sortira de la pile sera la dernière empilée LIFO : Last In First Out |
![]() |
Dans une file, on enfile les données les unes après les autres La première donnée qui sortira de la file sera la première enfilée. FIFO : First In First
Out |
A partir de notre graphe des villes on peut constituer la file des successeurs FS :
Commençons par Mulhouse comme sommet en se référant à la matrice d'adjacence, Mulhouse a pour successeurs Strasbourg, Vesoul, Epinal et Nancy et c'est tout (-).
On enfile les autres lignes de ma matrice d'adjacence et obtient la file FS suivante :
Il est conseillé de construire une liste APS contenant les Adresses des Premiers Successeurs.
Traitement des piles avec python
Traitement des files avec python
Cette fois, on construit la matrice qui permet de donner le nombre
d'arrêtes
minimales séparant deux sommets
Partons de Strasbourg : On marque le sommet pour indiquer qu'il a
été visité puis on cherche les voisins. On marque les voisins et
progressivement on enlève les arrêtes des sommets déjà visités. Quand
tous les sommets sont marqués on obtient un arbre. Si On recommence en
partant d'un autre sommet (ville) on aura un arbre différent.
Vidéo : introduction-aux-graphes
On désirer trouver le chemin le plus court pour sortir d'un
labyrinthe la distance séparant chaque sommet de son voisin est 1.
Le joueur (j) se trouve sur le sommet n°9 et la sortie (s) est au
n°32
Le graphe partiel du labyrinthe est le suivant :
Matrice d'adjacence partielle du labyrinthe :
9
|
10 | 11 | 12 | 13 | 18 | 20 | 21 | 25 | 26 | 29 | 32 | 33 | 34 | 35 | 36 | 37 | |
9 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
10 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
11 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
12 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
13 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
18 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
20 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
21 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
25 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
26 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
29 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
32 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
33 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
34 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 |
35 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |
36 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
37 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 |
Télécharger puis décompresser le fichier Labyrinthe.zip. Ouvrir le fichier
Labyrinthe_EL.py et ajouter y les fonctions permettant de trouver le chemin le plus court vers la sortie, en appliquant la théorie les
graphes.
Ajouter une fonction liste_sommets() qui retourne la liste des sommets à partir des coordonnées des cases espace, du joueur et de la sortie. La fonction recherche(objet) renvoie une liste contenant les coordonnées des objets recherchés : espace, j ou s. Le nombre de colonnes est stocké dans la variable larg_laby.
Algorithme
Fonction liste_sommetsAjoutez temporairement print(sommets) avant return
paramètres :
aucun
Résultat :
Liste contenant les n° des sommets des cases espace, du joueur et de la sortie
DEBUT
sommets ← []
coordonnees ← liste retournée par la recherche de la case du joueur 'j'
ajouter à la coordonnees la liste retournée par la recherche des cases espaces ' '
ajouter à la coordonnees la liste retournée par la recherche de la case sortie 's'
pour chaque coordonnee se trouvant dans la liste des coordonnees
calculer le numéro du sommet de la coordonnee
ajouter ce numéro de sommet dans la liste des sommets
retourne la liste des sommets
FIN
Fonction matrice_adjacence
paramètres :
la liste des sommets
Résultat :
Liste contenant la matrice d'adjacence
DEBUT
matrice ← []
ligne ← []
Pour chaque sommet dans la liste des sommets
Pour chaque som dans la liste des sommets
si le sommet = som-1 ou sommet = som+1 ou sommet = som+larg_laby ou sommet = som-larg_laby
empiler 1 dans la liste ligne
sinon
empiler 0 dans la liste ligne
empiler la ligne à la matrice
ligne ← []
affiche_matrice(sommets,matrice) # appel de la fonction qui affiche la matrice pour vérifier le résultat
retourne matrice
Fin
Algorithme
Fonction File_successeurs
paramètres :
matrice : liste matrice d'adjacence
sommets : liste des sommets
Résultats :
FS : la liste contenant la file des successeurs
APS : la liste des adresses des premiers successeurs
DEBUT
FS ← []
APS ← []
pour i variant de 0 à la hauteur de la matrice
empiler la longueur de FS dans la liste APS
pour j variant de 0 à la largeur de la matrice
si matrice[i][j]=1
empiler sommets[j] à la liste FS
empiler 0 à la liste FS
empiler la longueur de FS dans la liste APS
retourne la liste des successeurs et les adresses des 1er successeurs
Fin
On désire stocker la liste des sommets selon leur distance par rapport au nœud :
Ex : pour le nœud 10, on souhaite générer une liste de l'arbre
suivant : [[10],[9,18,11],[12,26],[13,20,25,34],[14,...],...]
Fonction parcours_largeur
paramètres :
noeud : représente la case du joueur
Résultat:
arbre : liste contenant les distances du noeud à chaque sommet
Debut:
arbre ← [[noeud]]
file ← [0,noeud]
visites ← [] # liste des sommets déjà visités
Tant que la longueur de la file contient plus d'un élément
rang ← [] # liste qui permet de stocker les successeurs du sommet courant
Tant que le premier élément de la file est >0: # la valeur 0 permet d'indiquer la fin de la file courante
sommet ← défiler la file # sommet = file.pop()
Empiler le sommet à la liste visites
indice ← sommets.index(sommet) # recherche de la position du sommet courant dans la liste des sommets
pour i variant de APS[indice] à APS[indice+1]-1: # recherche des voisins du sommet dans FS en excluant 0
si FS[i] n'est pas dans la liste visites
Enfiler FS[i] dans rang # rang.insert(0,FS[i])
Enfiler FS[i] dans file
Empiler FS[i] dans visite
Défiler la file (qui doit être 0) # condition d'arrêt du tant que
Empiler à l'arbre la liste rang
Enfiler la valeur 0 dans la file
retourne la liste arbre
Fin
Chercher la case de sortie dans l'arbre puis trouver le prédécesseur dans la matrice d'adjacence. On la lira en sélectionnant la colonne et pour trouver la case dans la ligne.
Exemple le prédécesseur de 32 est 33 :
Il peut y avoir plusieurs possibilités comme les prédécesseurs de 33 du niveau 3 de l'arbre qui en a deux : 25 et 34, on ne retiendra que le premier de l'arbre donc 25.
Algorithme :
Fonction chemin
paramètres :
arbre
Résultat:
Liste : contenant le chemin le plus court vers la sortie
Début:
sortie ← rechercher dans la carte les coordonnées de la sortie 's'
case ← calculer le numéro de la sortie en fonction de la largeur de la carte
i ← 0
pour chaque rang de l'arbre # recherche de la colonne dans FS de chaque rang dans l'arbre
si la case sortie se trouve dans la liste rang
pos ← index case sortie dans la liste rang # Ex : pos=2 si case=32 rang=[50,36,32,...]
Arrêt
sinon
incrémenter i # Compter les rangs passés
indice ← index de case dans la liste des sommets # recherche des prédécesseurs du sommet trouvé
predecesseurs ← []
tant que i>1
j ← 0
pour chaque ligne de la matrice # On parcourt les lignes de la matrice
if ligne[indice]==1 et sommets[j] dans arbre[i-1]
Empiler sommets[j] à la liste predecesseurs
Arrêt
incrémenter j
décrémenter i
indice ← index de sommets[j] dans la liste des sommets
retourne predecesseurs
fin
Colez votre code python ci-dessous
Les algorithmes de recherche de chemin, travaillent sur des graphes pondérés (par exemple pour rechercher la route entre un point de départ et un point d'arrivée dans un logiciel de cartographie). Ces algorithmes recherchent aussi souvent les chemins les plus courts. On peut citer l'algorithme de Dijkstra ou encore l'algorithme de Bellman-Ford qui recherchent le chemin le plus court entre un noeud de départ et un noeud d'arrivée dans un graphe pondéré.
La vidéo ci-dessous explique le principe de fonctionnement de l'algorithme de Dijkstra.
La vidéo ci-dessous explique le principe de fonctionnement de l'algorithme de Prim.
Fond : Texte : Tables : Thème du langage:
Contenu
sous licence CC BY-NC-SA 3.0
Pascal Hassenforder 13/10/2020
MAJ le 11/08/2022
Cours sur la théorie des graphes du DUI-NSI de Mr ELBAZ Mounir