Application

Question

En utilisant les quatre méthodes vues dans le cours, représenter le graphe ci-dessus en Python.

Question

Créez une classe, Graphe, en utilisant la méthode de votre choix, qui permet d’interagir avec un graphe orienté.

La fonction __init__ doit créer un graphe vide.

Question

Ajoutez une méthode ajout_sommet, telle que :

  • Entrée :

    • sommet - un sommet, de type quelconque

  • Sortie : Aucune

  • Effet : Ajoute le sommet

Question

Ajoutez une méthode suppr_sommet, telle que :

  • Entrée :

    • sommet - un sommet, de type quelconque

  • Sortie : Aucune

  • Effet : Supprime le sommet et les arêtes associées

Question

Ajoutez une méthode ajout_arete, telle que :

  • Entrées :

    • src - un sommet, de type quelconque, source

    • dst - un sommet, de type quelconque, destination

  • Sortie : Aucune

  • Effet : Ajoute l'arête si les deux sommets existent

Question

Ajoutez une méthode suppr_erete, telle que :

  • Entrées :

    • src - un sommet, de type quelconque, source

    • dst - un sommet, de type quelconque, destination

  • Sortie : Aucune

  • Effet : Supprime l'arêtes

Question

Ajoutez une méthode arete, telle que :

  • Entrées :

    • src - un sommet, de type quelconque, source d'une potentielle arête

    • dst - un sommet, de type quelconque, destination d'une potentielle arête

  • Sortie : Un booléen qui vaut True si l'arête existe, False sinon

  • Effet : Aucun

Question

Ajoutez une méthode voisins, telle que :

  • Entrée :

    • sommet - un sommet, de type quelconque

  • Sortie : Une liste des voisins de sommet

  • Effet : Aucun

Question

Pour les plus rapides : En utilisant l'héritage (hors-programme), créer une classe dédiée aux graphes non orientés ayant les mêmes fonctionnalités.

On souhaite ensuite représenter un chemin dans un graphe (cela nous sera très utile pour les futurs algorithmes).

Question

Comment représenter un chemin dans un graphe ? Quels sont les limites de votre choix ?

Implémentez ensuite une méthode dans la classe Graphe qui permet de vérifier qu'un chemin donné est bien un chemin dans le graphe.