In [ ]:
Nom = ""
Prénom = ""

Python 13 - Parcours d'un graphe¶

1 - Représentation du graphe¶

a - Sommets¶

Nous allons représenter chaque sommet par un objet de la classe Sommet. Ces sommets pourront avoir l'une des trois couleurs BLANC, GRIS ou NOIR :

In [ ]:
import affiche_graphe as affiche

BLANC, GRIS, NOIR = 0, 1, 2 

class Sommet:
    
    def __init__(self, etiquette):
        self.arcs = []   # La liste des étiquettes des sommets adjacents
        self.couleur = BLANC
        self.etiq = etiquette
    
    def ajoute_arc(self, etiquette):
        self.arcs.append(etiquette)
    
    def set_couleur(self, couleur):
        self.couleur = couleur
    
    def est_blanc(self):
        return self.couleur == BLANC

    def est_gris(self):
        return self.couleur == GRIS
    
    def est_noir(self):
        return self.couleur == NOIR
    
    def __repr__(self):
        c = 'blanc' if self.est_blanc() else 'gris' if self.est_gris() else 'noir'
        return 'S(' + str(self.etiq) + ', ' + c + ', ' + str(self.arcs) + ')'

b - Dictionnaire¶

Un graphe est représenté par un dictionnaire dont les clés sont les étiquettes des sommets et les valeurs des objets de la classe Sommet.

On veut pouvoir construire un tel graphe à partir d'une matrice d'adjacence.

In [ ]:
def construire_dict(matrice):
    """
    Construit le dictionnaire d'adjacence représentant le graphe dont la matrice
    d'adjacence est donnée. On utilisera des nombres compris entre 0 et len(matrice)-1
    comme étiquettes.
    :param matrice: (list) une liste de listes de booléens
    :return: (dict) le dictionnaire d'adjacence
    """
    # Insérez votre code ici
In [ ]:
mat = [[False, True, False, True],
       [False, False, True, True],
       [True, True, False, False],
       [False, True, True, False]]
d = construire_dict(mat)
assert str(d) == '{0: S(0, blanc, [1, 3]), 1: S(1, blanc, [2, 3]), 2: S(2, blanc, [0, 1]), 3: S(3, blanc, [1, 2])}'

2 - Parcours en profondeur et en largeur¶

Seul deux algorithmes de parcours des graphes sont au programme : le parcours en profondeur, et le parcours en largeur.

Le parcours en largeur est similaire au parcours du même nom des arbres binaires. Le parcours en profondeur correspond aux parcours préfixe, suffixe et infixe des arbres binaires.

Il y a néanmoins deux différences fondamentales entre un graphe et un arbre binaire :

  • la présence de cycles ;
  • le graphe ne peut pas toujours être parcouru en entier à partir d'un seul sommet.

On résoud le problème des cycles en colorant les sommets. De plus, tout parcours dans un graphe est un parcours à partir d'un certain sommet.

Les deux algorithmes sont similaires :

- tous les sommets sont colorés en blanc
- une structure de stockage contient le sommet de départ
- Tant que cette structure n'est pas vide :
    * on retire un sommet S de la structure de stockage
    * pour tout sommet adjacent à S :
        + on le colore en noir
        + on l'ajoute à la structure de stockage
  • Si la structure de stockage est une file, on parcourt le graphe en largeur.
  • Si la structure de stockage est une pile, on parcourt le graphe en profondeur.

a - Pile et file¶

Implémenter des classes Pile et File ayant la même interface :

In [ ]:
# Insérez votre code ici

b - Parcours générique¶

Implémenter une fonction parcours qui renvoie la liste des sommets visités lors du parcours d'un graphe donné en partant d'un sommet donné.

Les sommets seront parcourus dans l'ordre croissant de leurs étiquettes pour le parcours en largeur (ordre décroissant pour le parcours en profondeur).

In [ ]:
def parcours(graphe, depart, ile):
    """
    Renvoie un parcours du graphe en partant du sommet 'depart'
    Pour chaque sommet, on parcourera les sommmets adjacents dans l'ordre de leurs étiquettes
    :param graphe: (dict) le dictionnaire d'adjacence tel que décrit au paragraphe 1
    :param depart: (str) l'étiquette d'un sommet du graphe
    :param ile: (objet File ou Pile) la structure de stockage des sommets non-visités
    :return: (list) une liste d'étiquettes
    """
    # Insérez votre code ici
In [ ]:
mat = [[False, True, False, True],
       [False, False, True, True],
       [True, True, False, False],
       [False, True, True, False]]
g = construire_dict(mat)
assert parcours(g, 0, Pile()) == [0, 3, 2, 1] # profondeur
assert parcours(g, 0, File()) == [0, 1, 3, 2] # largeur
assert parcours(g, 1, Pile()) == [1, 3, 2, 0] # profondeur
assert parcours(g, 1, File()) == [1, 2, 3, 0] # largeur
# affiche.matrice(mat)

3 - Applications¶

a - Chemin entre deux sommets¶

En utilisant la fonction parcours, définir une fonction chemin_existe qui indique si un sommet est relié à un autre sommet dans un graphe.

In [ ]:
def chemin_existe(graphe, depart, arrivee):
    """
    Indique si un chemin existe entre le départ et l'arrivée dans le graphe
    :param graphe: (dict) le dictionnaire d'adjacence
    :param depart: (str) l'étiquette du sommet de départ
    :param arrivee: (str) l'étiquette du sommet d'arrivée
    :return: (bool)
    """
    # Insérez votre code ici
In [ ]:
mat = [[False, True, False, False, False],
       [False, False, True, False, False],
       [False, False, False, True, False],
       [False, False, False, False, False],
       [True, False, False, True, False]]
g = construire_dict(mat)
assert chemin_existe(g, 0, 3)
assert not chemin_existe(g, 0, 4)
assert chemin_existe(g, 4, 1)
affiche.matrice(mat)

b - Présence d'un cycle dans un graphe orienté¶

On va modifier l'algorithme de parcours en profondeur pour lui faire repérer les cycles. En effet, lorsque, en parcourant une cycle en profondeur, on tombe sur un sommet coloré en noir, on a trouvé un cycle. Sauf si ce sommet est un cul de sac.

On va donc colorer les sommets visités en deux couleurs :

  • en noir pour les culs de sac ;
  • en gris les autres.

Tomber sur un sommet gris signifiera donc avoir trouvé un cycle.

Définir une fonction contient_cycle qui indique si un graphe contient un cycle ou pas, en utilisant une version modifiée de l'algotithme de parcours en profondeur.

In [ ]:
def contient_cycle(graphe):
    """
    Indique si le graphe contient un cycle
    :param graphe: (dict) le dictionnaire d'adjacence d'un graphe
    :return: (bool) le graphe contient un cycle ou pas
    """
    # Insérez votre code ici
In [ ]:
m1 = [[False, True], [True, False]]
g1 = construire_dict(m1)
assert contient_cycle(g1)

m2 = [[False, True, False], [False, False, True], [True, False, False]]
g2 = construire_dict(m2)
assert contient_cycle(g2)

m3 = [[False, True, False], [False, False, True], [False, False, False]]
g3 = construire_dict(m3)
assert not contient_cycle(g3)

m4 = [[False, True, False, False, False],
      [False, False, True, False, False],
      [False, False, False, True, False],
      [False, False, False, False, False],
      [True, False, False, True, False]]
g4 = construire_dict(m4)
assert not contient_cycle(g4)

m5 = [[False, True, False, False, False],
      [False, False, True, False, False],
      [False, False, False, True, False],
      [True, False, False, False, False],
      [True, False, False, True, False]]
g5 = construire_dict(m5)
assert contient_cycle(g5)