NUMERIQUE ET SCIENCES INFORMATIQUES

Niveau : Terminale générale, enseignement de spécialité NSI

Les graphes

1 - La théorie des graphes :

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.

1.1 - Matrice d'adjacence :

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 :

            
       Matrice d'adjacence               recherche des successeurs          recherche des prédécesseurs

Pour connaître :

• Son successeur, on sélectionne la ligne puis les successeurs marqués par la valeur 1 se trouvent dans les colonnes : Vesoul a pour successeurs Mulhouse, Epinal et Nancy
  
• Son prédécesseur, on sélectionne la colonne puis les prédécesseurs marqués par la valeur 1 se trouvent dans les lignes : Strasbourg a pour prédécesseurs Mulhouse, Epinal et Nancy

1.2 - PILES et FILES : LIFO / FIFO

	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

FS=["Strasbourg","Vesoul","Epinal"] print ("1:",FS) FS.append("Mulhouse") # Empile "Mulhouse" print ("2:",FS) x=FS.pop() # Dépile print ("3:",FS,"->",x) x=FS.pop() # dépile print ("4:",FS,"->",x)

Exécuter

Traitement des files avec python

FS=["Strasbourg","Vesoul","Epinal"] print ("1:",FS) FS.insert(0,"Mulhouse") # Enfile "Mulhouse" print ("2:",FS) x=FS.pop() # Défile print ("3:",FS,"->",x) x=FS.pop() # Défile print ("4:",FS,"->",x)

Exécuter

1.3 - Parcours des graphes en largeur

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.

 
A partir d'un nœud source S, il liste d'abord les voisins de S pour ensuite les explorer un par un. Ce mode de fonctionnement utilise donc une file dans laquelle il prend le premier sommet et place en dernier ses voisins non encore explorés.

Les nœuds déjà visités sont marqués afin d'éviter qu'un même nœud soit exploré plusieurs fois. Dans le cas particulier d'un arbre, le marquage n'est pas nécessaire.

Étapes de l'algorithme :

   1. Mettre le nœud source dans la file.
   2. Retirer le nœud du début de la file pour le traiter.
   3. Mettre tous les voisins non explorés dans la file (à la fin).
   4. Si la file n'est pas vide reprendre à l'étape 2.

Note : l'utilisation d'une pile au lieu d'une file transforme l'algorithme du parcours en largeur en l'algorithme de parcours en profondeur. 

Vidéo : introduction-aux-graphes

2 - MISE EN PRATIQUE

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

2.1 - Codage de la fonction liste_sommets

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.

L'exécution de la fonction recherche('j') renvoie [(2,1)]. Trouver un calcul simple ( * et + ) utilisant les coordonnées x et y de j et la largeur de labyrinthe stockée dans la variable larg_laby permettant de calculer le n° du sommet : donc 10 dans le labyrinthe ci-dessus.

Algorithme

Fonction liste_sommets   
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

Ajoutez temporairement print(sommets) avant return
il faut trouver [9, 11, 12, 13, 14, 18, 20, 21, 22, 25, 26, 29, 30, 33, 34, 35, 36, 37, 38, 41, 42, 46, 49, 50, 51, 52, 53, 54, 10, 32]

2.2 - Matrice d'adjacence :

Si on prend le sommet n° 26 : les sommets adjacents sont ceux qui sont :

• au-dessus : 26 - larg_laby
• en-dessous : 26 + larg_laby
• à gauche : 26 -1
• à droite : 26+1

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

2.3 - File des successeurs :

Il faut donc parcourir la matrice d'adjacence ligne par ligne et rechercher les 1 qui correspondent aux sommets adjacents.
On ajoute ce sommet dans la liste FS et on ajoute 0 pour terminer les successeurs. Au passage on construit la liste APS (l'Adresse des Premiers Successeurs).

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

2.4- Parcours en largeur

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,...],...]

Algorithme

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 

2.5 - Recherche du chemin vers la sortie

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

Algorithme de recherche de chemin

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: default 3024-day 3024-night abbott abcdef ambiance ayu-dark ayu-mirage base16-dark base16-light bespin blackboard cobalt colorforth darcula dracula duotone-dark duotone-light eclipse elegant erlang-dark gruvbox-dark hopscotch icecoder idea isotope juejin lesser-dark liquibyte lucario material material-darker material-palenight material-ocean mbo mdn-like midnight monokai moxer neat neo night nord oceanic-next panda-syntax paraiso-dark paraiso-light pastel-on-dark railscasts rubyblue seti shadowfox solarized dark solarized light the-matrix tomorrow-night-bright tomorrow-night-eighties ttcn twilight vibrant-ink xq-dark xq-light yeti yonce zenburn

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