Aller au contenu
Compétences évaluées
Concevoir des solutions algorithmiques
Traduire un algorithme dans un langage de programmation

Tous les TP seront notés (barème indicatif).

  • Tout TP non rendu avant la fin de la séance sera noté zéro.
  • Veuillez mettre clairement vos noms sur votre code source ou noms de fichiers.
  • Coefficient de ce TP : 0.25.
  • Durée de ce TP : 1h.

Implémentation des graphes

Pour ce TP nous allons travailler avec le graphe que nous appellerons graphe 1 :

image

Liste d'ajacence (2 points)

Représenter le graphe graphe 1 sous la forme d'une liste d'ajacence.

Voir le cours si nécessaire : https://snt-nsi.net/nsi_terminale/graphes/cours/#implementation-des-graphes

Matrice d'ajacence (2 points)

Représenter le graphe graphe 1 sous la forme d'une matrice d'ajacence.

Voir le cours si nécessaire : https://snt-nsi.net/nsi_terminale/graphes/cours/#matrice-dadjacence

Classe (16 points)

Sommet (4 points)

  • Créer une classe Sommet d’attribut etiquette.

La méthode __str__ est utile lors d'appel des fonctions str(), print() et format(). Cette méthode renvoie une chaîne de caractère correspondant à la représentation informelle de l’objet.

Ajouter une méthode str qui renvoie l’étiquette du sommet sous forme de chaine de caractère.

Graphe (12 points)

  • Créer une classe Graphe d’attribut sommets (vide au début) et matrice_adjacence (initialisée avec des zéros uniquement).
  • Ajouter une méthode def ajoute_sommet(self, etiquette) qui modifiera la liste sommets.
  • Ajouter une méthode def ajoute_arete(self, index1, index2). Index1 et index2 sont des entiers.
  • Représenter le graphe graphe 1 sous la forme d'une classe Graphe en appelant les méthodes ajoute_arete et ajoute_sommet.