Représentation d'un graphe en informatique
Plusieurs modes de représentation peuvent être implémentés pour stocker des graphes : matrices d’adjacence (ou sommet-sommet), listes des voisins, des successeurs ou des prédécesseurs. Lors de cette séance nous allons écrire les classes réalisant ces implémentations.
Structure de graphe basée sur une liste d’adjacence
-
Écrire le code de la méthode
__init__de la classeSommetdont la spécification est :Remarque : La classe
Sommetpossède deux attributs :valreprésente la valeur du sommet ou son étiquette. Cet attribut est de type chaîne de caractères (str) ;adjreprésente la liste des sommets adjacents au sommet, instance de la classe. Cet attribut référence une liste de sommets ; lors de l’initialisation d’un sommet il doit référencer une liste vide.
-
Ajouter au code de la classe
Sommetla re-définition de la méthode__repr__donnée ci-dessous :Cette méthode permet de représenter un sommet sous la forme d’une chaîne de caractères.
-
Tester la définition de la classe
Sommeten ajoutant les lignes de code suivantes au fichier : -
Écrire le code de la méthode
__init__de la classeGraphedont la spécification est :Remarque : La classe
Sommetpossède un seul attribut,sommets. Ce dernier référence une liste d’objets de typeSommet. Cette liste est initialement :-
Soit vide,
-
Soit constituée des sommets passés en argument lors de l’initialisation d’un objet de type
Graphe.
-
-
Ajouter au code de la classe
Graphela re-définition de la méthode__repr__donnée ci-dessous :Cette méthode permet de représenter un graphe sous la forme d’une chaîne de caractères.
-
Tester la définition de la classe
Grapheà l’aide du code suivant, sous les lignes de code de la question 3 : -
Écrire le code de la méthode
existe_sommetdont la spécification est :
-
Tester le code précédent en ajoutant les instructions suivantes, à la fin du fichier :
-
Écrire le code de la méthode
ajout_sommetdont la spécification est :
-
Tester le code précédent en ajoutant les instructions suivantes, à la fin du fichier :
-
Écrire le code de la méthode
recuperation_sommetdont la spécification est :
Remarque : Cette méthode simplifie l’écriture des méthodes suivantes.
-
Écrire le code de la fonction
existe_aretedont la spécification est :
-
Écrire le code de la fonction
ajout_aretedont la spécification est :
-
Tester le code précédent en ajoutant les instructions suivantes, à la fin du fichier :
-
Écrire le code de la fonction
est_non_orientedont la spécification est :
-
Tester le code précédent en ajoutant les instructions suivantes, à la fin du fichier :
-
On souhaite maintenant écrire le code de la fonction
construction_matricedont la spécification est :Compléter le code suivant :
-
Tester le code précédent en ajoutant les instructions suivantes, à la fin du fichier :
-
Écrire le code de la méthode
representation_matricedont la spécification est :Tester le code.
Extensions possibles
Il est possible de compléter la classe en définissant les méthodes suivantes :
-
taille, de spécification : -
rend_non_oriente, de spécification : -
suppression_arete, de spécification : -
suppression_sommet, de spécification :