Parcours d’un graphe

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

Parcours en profondeur

Le parcours en profondeur d’un graphe à partir d’un sommet consiste à suivre les arêtes arbitrairement, en marquant les sommets déjà visités pour ne pas les visiter à nouveau.

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 !

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 (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.

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.

def existe_chemin(self, x, y):
    """ Renvoie True si un chemin existe entre les sommets x et y
    """
    vus = set()
    self.parcours(x, vus)
    return y in vus

Présence 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 à trois niveaux (couleurs) :

• « blanc » : non visité
• « gris » : visité une seule fois
• « noir » : visité deux fois

def existe_cycle(self):
    if len(self.A) == 0:
        return False
    s = self.A.keys()[0]
    vus = set()
    p = Pile()
    p.push((s, 0)) # 0 = 'gris'
    while not p.est_vide():
        s = p.pop()
        if not s in vus:
            vus.add(s)
            # print(s)
            for v in self.voisins(s):
                p.push((v, 0))
        else:
            p.push((s, 1))
    return vus

Parcours en largeur

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

Algorithme

def parcours_larg(self, s):
    dist = {s : 0}
    cour = {s}
    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
        if len(cour) == 0:
            cour, suiv = suiv, set()
    return dist

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 vusqui associe à chaque sommet visité le sommet qui a permis de l’atteindre (au sommet de départ, on associera la valeur None).

def parcours_larg_chemin(self, s):
    """ Parcours en largeur du graphe, à partir du sommet s
        Renvoie un dictionnaire {sommet: précédent}
        qui doit permettre de construire des chemins depuis s
    """
    vus = {s : None}
    cour = {s}
    suiv = set()
    while len(cour) > 0:
        s = cour.pop()
        for v in self.voisins(s):
            if not v in vus:
                suiv.add(v)
                vus[v] = s
        if len(cour) == 0:
            cour, suiv = suiv, set()
    return vus

def chemins(self, x, y):
    """ Parcours en profondeur à partir du sommet s
        Renvoie la liste des chemins parcourus
    """
    vus = self.parcours_larg_ch(x)
    c = []
    if y in vus:
        s = y
        while s is not None:
            c.append(s)
            s = vus[s]

    return c[::-1]

Coloration

La coloration d’un graphe consiste à attribuer une « couleur » à chacun de ses sommets de manière que deux sommets reliés par une arête soient de couleur différente.

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

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