Aller au contenu

Interface (Bac 🎯)⚓︎

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.

programme

Sources et crédits pour ce cours

Pour préparer ce cours, j'ai utilisé :

🔖 Synthèse de ce qu'il faut retenir pour le bac

Interface objet⚓︎

Point de cours 3 : une interface pour une classe Graphe

Pour implémenter les algorithmes de graphe au programme, l'interface minimale ci-dessous sera suffisante. Le choix d'une structure de données de représentation du graphe dépend de l'implémentation choisie et sera développé dans la section suivante.

L'interface est donnée pour un graphe orienté, pour un graphe non orienté une petite adaptation sera nécessaire :

  • Dans la méthode ajoute_arc, par symétrie, il faudra penser à ajouter les arcs sommetA -> sommetB et sommetB -> sommetA dans la représentation interne du graphe.
🐍 Script Python
class Graphe:

    def __init__(self, liste_sommets):
        """
        Crée une représentation de  graphe orienté à partir d'une liste de sommets
        """

    def sommets(self):
        """
        Renvoie une liste des sommets
        """

    def ajoute_arc(self, sommetA, sommetB):
        """
        Ajoute dans la représentation de graphe l'arc sommetA -> sommetB
        """

    def voisins(self, sommet):
        """
        Renvoie une liste des voisins du sommet dans la représentation du graphe
        """

    def est_arc(self, sommetA, sommetB):
        """
        Renvoie un booléen indiquant si l'arc sommetA - sommetB appartient au graphe
        """

Application de l'interface objet⚓︎

Exercice 3

Question 1

alt

Compléter la séquence d'instructions ci-dessous pour représenter le graphe orienté ci-dessus comme instance de la classe Graphe :

🐍 Script Python
g1 = Graphe([0, 1, 2, 3, 4])
🐍 Script Python
g1 = Graphe([0, 1, 2, 3, 4])
g1.ajoute_arc(1, 2)
g1.ajoute_arc(1, 4)
g1.ajoute_arc(2, 3)
g1.ajoute_arc(2, 4)
g1.ajoute_arc(3, 4)
g1.ajoute_arc(4, 0)

Question 2

Étendre l'interface de la classe Graphe précédente, dans le cas où elle modélise un graphe orienté, avec une méthode :

  • degre_sortant(self, sommet) qui renvoie le degré sortant d'un sommet
🐍 Script Python
def degre_sortant(self, sommet):
    """
    Renvoie le degré sortant d'un sommet du graphe orienté
    """
    return len(self.voisins(sommet))

Question 3

Étendre l'interface de la classe Graphe précédente, dans le cas où elle modélise un graphe orienté, avec une méthode :

  • degre_entrant(self, sommet) qui renvoie le degré entrant d'un sommet
🐍 Script Python
def degre_entrant(self, sommet):
    """
    Renvoie le degré entrant d'un sommet du graphe orienté
    """
    d = 0
    for s in self.sommets():
        if sommet in self.voisins(s):
            d = d + 1
    return d