Parcours de graphes

Parcourir un graphe consiste à visiter ses sommets, en suivant les arêtes qui les relient…

Pour les algorithmes de cet article, nous utiliserons la classe Graphe suivante :

Classe Graphe
class Graphe:
    """ """
    def __init__(self, oriente = True):
        self.A = {}                # Dictionnaire d'adjacence
        self.oriente = oriente     # Graphe orienté ou pas

    def __repr__(self):
        return str(self.A)

    def ajouter_sommet(self, x):
        if not x in self.A:
            self.A[x] = set()

    def ajouter_arete(self, x, y):
        """ Ajoute une arête entre les sommets x et y
        """
        self.ajouter_sommet(x)
        self.ajouter_sommet(y)
        self.A[x].add(y)
        if not self.oriente:
            self.A[y].add(x)

    def voisins(self, x):
        """ Renvoie l'ensemble des voisins du sommet x
        """
        return self.A[x]

    def arete(self, x, y):
        """ Renvoie True s'il existe une arête entre les sommets x et y
        """
        return x in self.A[y]

Et pour les exemples, le graphe suivant :

Télécharger au format PDF : graphe.pdf
Construction d'un graphe
Écrire les instructions permettant d'obtenir une instance du graphe représenté plus haut, à l'aide de la classe Graphe  et de son interface (consulter le code) :

 

 

Parcours en profondeur

Le parcours en profondeur d’un graphe à partir d’un sommet consiste à suivre les arêtes arbitrairement, en allant le plus loin possible (« en profondeur » !).

Pour ne pas le visiter à nouveau, chaque sommet visité est aussitôt en marqué « déjà visité »

Exemple : parcours du graphe à partir du sommet A.

     

 

Les arêtes étant choisies arbitrairement, il faut s’attendre à des visites dans des ordres différents !

 

 

Parcours en profondeur
Pour chacun des graphes suivants, déterminer une séquence de lettres correspondant un un parcours en profondeur.

Règles :

    • chaîne de caractères au format suivant : séquence de lettres séparées par des espaces ;
    • la première lettre correspond au nœud de départ ;
    • lorsque plusieurs possibilités se présentent on choisit l’ordre alphabétique

Parcours en profondeur à partir du nœud A

×

Parcours en profondeur à partir du nœud C

×

Parcours en profondeur à partir du nœud E

×

 

Algorithme

Afin de mémoriser les sommets visités pendant le parcours, on les marque, en les plaçant dans une liste ou un ensemble par exemple.

  • Initialement, on marque le sommet de départ comme « visité »
  • On choisit ensuite arbitrairement une de ses arêtes sortantes
    • Si le sommet voisin n’a pas déjà été visité :
      • on le marque comme « visité »
      • on relance un nouveau parcours à partir de ce sommet
  • on recommence avec son arête sortante suivante …
  • le parcours s’arrête lorsqu’on n’atteint plus aucun sommet non visité.

Exemple :

 

Méthode récursive

Le parcours en profondeur peut être réalisé par récursivité :

  • l’ensemble des sommets déjà visités est stocké dans un objet Python de type ensemble (set).
  • la visite est relancée récursivement pour chaque voisin du sommet visité
def parcours_prof(self, s, vus = None):
    """ Parcours en profondeur à partir du sommet s
        --> vus contient l'ensemble des sommets visités
    """
    if vus is None:
        vus = set()
    if not s in vus:
        vus.add(s)
        for v in self.voisins(s):
            self.parcours_prof(v, vus)
    return vus

 

 

Méthode itérative

En cas de très grand nombre de sommets, la méthode récursive peut vite atteindre sa limite (rappel : la profondeur maximale de récursion est par défaut égale à 1000 en Python).

On peut alternativement utiliser une méthode itérative, à l’aide d’une pile.

Classe Pile
class Pile:
    """ """
    def __init__(self):
        self._l = []

    def __repr__(self):
        return str(self._l)

    def est_vide(self):
        return len(self._l) == 0

    def empiler(self, v):
        self._l.append(v)

    def depiler(self):
        return self._l.pop()

Module complet : piles_files.py

Parcours en profondeur avec une pile
Écrire pour la classe Graphe une nouvelle méthode parcours_prof_pile(s), qui utilise une pile.

 

Utilisations

Existence d’un chemin

À l’issue du parcours, vus contient l’ensemble des sommets qui ont été visités. On peut ainsi vérifier facilement s’il existe ou pas un chemin menant du sommet de départ vers un autre sommet. En revanche, l’ordre du parcours, donnant le chemin n’est pas mémorisé par ce type de parcours.

Existence d'un chemin : implémentation
Ajouter à la classe Graphe une méthode existe_chemin(x, y), qui renvoie True si un chemin existe entre les sommets x et y.
Correction
def existe_chemin(self, x, y):
    """ Renvoie True si un chemin existe entre les sommets x et y
    """
    return y in parcours_prof(x)

 

Existence d’un cycle

Le parcours en profondeur est particulièrement bien adapté à la recherche de cycles dans un graphe.

Le marquage « simple » (tout ou rien) opéré dans l’algorithme précédent ne permet pas de savoir si, lorsqu’on atteint un sommet « visité », il s’agit de la fin d’un parcours.

On utilise donc un marquage des sommets à trois niveaux (« couleurs ») :

  • BLANC : non visité
  • GRIS : visité une seule fois
  • NOIR : visité deux fois

Algorithme :

  • Tous les sommets sont initialement colorés en BLANC.
  • Lorsqu’on visite un sommet :
    • s’il est BLANC :
      • on le marque en GRIS (ce sommet a été visité une fois)
      • pour chacun de ses voisins :
        • on lance un parcours récursivement
        • si le retour est VRAI (on a déjà découvert un cycle sur un parcours passant par ce sommet)
          → VRAI
      • on le marque en NOIR (le parcours depuis ce sommet n’a pas révélé de cycle)
    • s’il est GRIS (on a découvert un cycle !)
      → VRAI
    • s’il est NOIR (il n’y a pas de cycle à partir de ce sommet)
      → FAUX

 

 

Existence d'un cycle : implémentation
Implémenter une méthode parcours_cycle_r, selon l'algorithme récursif décrit plus haut, en utilisant un dictionnaire coul pour colorer chaque somment en BLANC (1), GRIS (2) ou NOIR (3).
Correction
def parcours_cycle_r(self, s, coul = None):
    if coul is None:
        coul = {s:1 for s in self.A.keys()} # on colore tous les sommets en BLANC
    if coul[s] == 2:  # déjà visité = on vient de découvrir un cycle
        return True
    if coul[s] == 3: 
        return False 
    coul[s] = 2
    for v in self.voisins(s):
        if self.parcours_cycle_r(v, coul):
            return True
    coul[s] = 3 # pas de cycle en partant de ce sommet s
    return False
Écrire alors une méthode existe_cycle pour vérifier s'il existe un cycle dans le graphe.

 

 

 


Parcours en largeur

Dans le parcours en largeur, on visite tous les sommets en « cercles concentriques » autour du sommet de départ : d’abord les sommets à une distance de 1, puis ceux à une distance de 2, … 

 

 

Algorithme

L’algorithme proposé utilise les structures de donnée suivantes :

  • cour : un ensemble (set) des sommets en cours de visite
  • suiv : un ensemble (set) des sommets à visiter à la prochaine étape
  • dist : un dictionnaire {sommet parcouru : distance depuis le départ}, renvoyé par la fonction de parcours

def parcours_larg(self, s):
    # le sommet de départ s ...
    dist = {s : 0}     # ... est à une distance nulle de lui même ...
    cour = {s}         # ... et c'est le 1er somment courant
    suiv = set()
    while len(cour) > 0:
        s = cour.pop()
        for v in self.voisins(s):
            if not v in dist:
                suiv.add(v)
                dist[v] = dist[s] + 1   # v est à une distance +1 de s
        if len(cour) == 0:              # on a visité tous les sommets courants
            cour, suiv = suiv, set()
    return dist
Parcours en largeur
Pour chacun des graphes suivants, déterminer une séquence de lettres correspondant un un parcours en largeur .

Règles :

    • chaîne de caractères au format suivant : séquence de lettres séparées par des espaces ;
    • la première lettre correspond au nœud de départ ;
    • lorsque plusieurs possibilités se présentent on choisit l’ordre alphabétique

Parcours en largeur à partir du nœud A

×

Parcours en largeur à partir du nœud C

×

Parcours en largeur à partir du nœud E

×

 

Utilisation

Recherche de chemins

Le parcours en largeur permet d’obtenir le chemin le plus court entre deux sommets du graphe :

On remplace le dictionnaire dist précédent par un autre dictionnaire vus qui associe à chaque sommet visité le sommet qui a permis de l’atteindre (au sommet de départ, on associera la valeur None).

Exemple :

Le parcours en largeur peut renvoyer le dictionnaire : {'A' : None, 'B' : 'A', 'C' : 'B', 'D' : 'A', 'E' : 'C' : 'F' : 'C'}

Qui peut se lire :

    • On atteint ‘B’ par ‘A’
    • On atteint ‘C’ par ‘B’
    • On atteint ‘D’ par ‘A’
    • On atteint ‘E’ par ‘C’
    • On atteint ‘F’ par ‘C’

 

 

Recherche de chemins
Écrire une méthode parcours_larg_chemin(s) qui renvoie le dictionnaire  vus qui doit permettre de "retracer" le parcours en largeur (la structure de cette méthode est très proche de celle de la méthode parcours_larg(s)).

 

Écrire une méthode chemins(x, y) qui utilise la méthode parcours_larg_chemin(s) et renvoie le plus court chemin depuis le sommet x jusqu'au sommet y.

 

 

 

Coloration

La coloration d’un graphe non orienté consiste à attribuer une « couleur » à chacun de ses sommets de manière que deux sommets adjacents soient de couleurs différentes.

On cherche souvent à utiliser le nombre minimal de couleurs, appelé nombre chromatique.

Si trouver le nombre chromatique est un problème difficile, il est tout de même possible de colorier un graphe à l’aide d’un « simple » algorithme glouton :

  • créer un dictionnaire {sommet : couleur} initialement vide
  • pour chaque sommet du graphe :
    • lui attribuer la plus petite couleur disponible, non déjà affectée à un de ses voisins
Coloriage glouton
Écrire une méthode colorer(s), qui colore le graphe à partir du sommet s et renvoie un dictionnaire {sommet : couleur} (en guise de couleurs, on utilisera des entiers).

 

 

Sources :
https://www.editi0ons-ellipses.fr/accueil/10445-20818-specialite-numerique-et-sciences-informatiques-lecons-avec-exercices-corriges-terminale-nouveaux-programmes-9782340038554.html#/1-format_disponible-broche

Vous aimerez aussi...

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *