Aller au contenu

Graphes et POO

Tout comme les arbres, il nous est possible de représenter les graphes sous la forme d'une classe Python.

Nous souhaitons représenter le graphe ci-dessous sous la forme d'une classe Graphe.

Graphe_POO

On pourra créer celui-ci de cette manière 

g = Graphe(['A', 'B', 'C', 'D', 'E'])
g.ajoute_arete('A', 'B')
g.ajoute_arete('A', 'C')
g.ajoute_arete('A', 'D')
g.ajoute_arete('A', 'E')
g.ajoute_arete('B', 'C')
g.ajoute_arete('C', 'D')
g.ajoute_arete('D', 'E')

Nous souhaitons aussi pouvoir tester si deux sommets sont voisins avec la méthode sont_voisins :

>>> g.sont_voisins('E', 'A')
True
>>> g.sont_voisins('E', 'B')
False

Enfin, nous voulons pouvoir obtenir facilement la liste de tous les voisins d'un sommet avec la méthode voisins:

>>> g.voisins('C')
['A', 'B', 'D']

L'objet de type Graphe aura comme attributs :

  • une liste liste_sommets (donnée en paramètre dans la liste liste_sommets)
  • un dictionnaire adjacents, où chaque sommet se verra attribuer une liste vide [].

Implémentation

class Graphe:
    def __init__(self, liste_sommets):
        self.liste_sommets = liste_sommets
        self.adjacents = {sommet : [] for sommet in liste_sommets}

    def ajoute_arete(self, sommetA, sommetB):
        self.adjacents[sommetA].append(sommetB)
        self.adjacents[sommetB].append(sommetA)

    def voisins(self, sommet):
        return self.adjacents[sommet]

    def sont_voisins(self, sommetA, sommetB):
        return sommetB in self.adjacents[sommetA]

Merci à Gilles Lassus pour la source.

Auteur : Florian Mathieu

Licence CC BY NC

Licence Creative Commons
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.