Aller au contenu principal

TP2 – Algorithmes sur les graphes

Objectifs
  • Mettre en œuvre des algorithmes classiques sur les graphes.
  • Comprendre la différence entre parcours en largeur et parcours en profondeur.
  • Savoir détecter l’existence d’un chemin ou d’un cycle dans un graphe.
Pré-requis
  • Connaître la représentation d’un graphe par liste d’adjacence.
  • Savoir utiliser une file et une pile (TP précédents).
  • Maîtriser les notions suivantes en Python : listes, dictionnaires, fonctions, classes.
Documentation
  • Les méthodes demandées doivent être ajoutées à la classe GrapheOriente. Grâce à l’héritage, elles seront automatiquement utilisables avec GrapheNonOriente.
  • Écrire la documentation des fonctions demandées.

Parcours en largeur (BFS)​

Principe

Le parcours en largeur explore le graphe niveau par niveau à partir d’un sommet donné.

Pour cela :

  • on utilise une file ;
  • on mémorise les sommets déjà visités à l’aide d’un dictionnaire afin d’éviter les boucles.
Algorithme

  1. On initialise une file puis on y ajoute le sommet de départ ;

  2. On initialise une structure qui permettra de mémoriser les sommets déjà rencontrés (dictionnaire). On ajoute également le sommet de départ à la structure ;

  3. Tant que la file n’est pas vide :

    • On retire le sommet courant depuis la file (on le stocke dans une variable) ;
    • On affiche le sommet courant (print) ;
    • Pour chaque voisin du sommet courant :
      • si le voisin n’a pas déjà été rencontré (vérification avec le dictionnaire) :
        • on l’ajoute à la file ;
        • on l’ajoute comme clé du dictionnaire pour mémoriser qu’on a déjà rencontré ce sommet.

On peut utiliser le dictionnaire en associant le sommet à la valeur True pour indiquer qu’il a déjà été rencontré. L’utilisation d’un dictionnaire (au lieu d’une liste) est justifiée pour des raisons de complexité temporelle.

sommets_rencontres = {}
#Quand on rencontre un nouveau "sommet" :
sommets_rencontres[sommet] = True
#Pour vérifier si on a déjà rencontré un "sommet"
if sommet in sommets_rencontres:
    ...
  1. Importer la classe File (codée lors d’un précédent TP) : 
    from ... import File
  2. Implémenter la méthode parcours_largeur(self, sommet) qui :
    • effectue un parcours en largeur à partir du sommet donné ;
    • affiche (avec print) les sommets dans l’ordre de visite.
  3. Tester la méthode sur les graphes créés dans le TP1, à partir du sommet "A".

Parcours en profondeur (DFS)​

Principe

Le parcours en profondeur explore un chemin du graphe jusqu’au bout avant de revenir en arrière.

Différences avec le parcours en largeur :

  • on utilise une pile au lieu d’une file ;
  • l’ordre d’empilement des voisins est important : on utilisera reversed.
  1. Importer la classe Pile : 
    from ... import Pile
  2. Implémenter la méthode parcours_profondeur(self, sommet) qui :
    • effectue un parcours en profondeur à partir du sommet donné ;
    • affiche les sommets visités dans l’ordre.
  3. Tester la méthode sur les graphes créés dans le TP1, à partir du sommet "A".

Trouver un chemin entre deux sommets​

On souhaite maintenant déterminer un chemin possible entre deux sommets du graphe, sans passer deux fois par le même sommet.

La méthode utilisée est récursive et s’appuie sur une liste chemin représentant le chemin en cours de construction.

Algorithme

On va gérer une liste chemin qui sera modifiée et transmise lors des appels récursifs.

  1. Au début, on ajoute le sommet de départ dans la liste chemin.
  2. Si le sommet de départ et le sommet de destination sont identiques, on retourne la liste (cas d'arrêt).
  3. Sinon, pour tous les voisins du sommet de départ :
    • Si le voisin n’est pas déjà dans le chemin :
      • on calcule un nouveau chemin (que l’on stocke donc dans une variable) avec un appel récursif avec comme paramètre : voisin, sommet de destination, chemin.
    • Si ce nouveau chemin calculé n’est pas nul (None), cela signifie qu’on a un chemin allant du départ à la destination, on le retourne.
  4. Quand on sort de la boucle, à partir du sommet de départ donné en paramètre, on n’a pas trouvé de chemin allant jusqu’au sommet désiré. On retire donc le sommet de départ de la liste, et on retourne None.
  1. Implémenter la méthode récursive : 
    trouver_chemin_recursif(self, sommet_depart, sommet_destination, chemin)
    Elle doit retourner :
    • une liste de sommets représentant un chemin valide ;
    • ou None s’il n’existe aucun chemin.
  2. Implémenter la méthode "enveloppe" : 
    def trouver_chemin(self, sommet_depart, sommet_destination):
        return self.trouver_chemin_recursif(sommet_depart, sommet_destination, [])
  3. Tester sur les graphes créés dans le TP1.

Détection de cycles​

Dans un graphe :

  • on parle de cycle pour un graphe non orienté ;
  • de circuit pour un graphe orienté.

L’objectif est de détecter si un cycle est atteignable depuis un sommet donné.

Principe
  • On effectue un parcours en profondeur à l’aide d’une pile.
  • Si un sommet déjà rencontré est rencontré à nouveau, alors un cycle existe.
  1. Implémenter la méthode detecte_cycle(self, sommet) qui retourne :
    • True si un cycle est détecté à partir de ce sommet ;
    • False sinon.
  2. Tester sur les graphes créés dans le TP1.
  3. Implémenter la méthode contient_cycle(self) qui :
    • teste la présence d’un cycle à partir de tous les sommets du graphe ;
    • retourne True si le graphe contient au moins un cycle, False sinon.