Aller au contenu

Actvité 3

Tous les TP seront notés.

  • 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.

Exercice 1 (6 points)

Votre camarade John mcnugget est pressé, il doit s'échapper car il est lassé de sa vie à Paris. Il désire se rendre à Tokyo en utilisant différents moyens de transports, mais il ne sait pas s'il existe un chemin qui lui permettra de se rendre à destination. Aidez votre ami.

image

  • Créer la liste d'adjacence correspondant à ce graphe.
  • Déterminer si un chemin existe entre Paris et Tokyo en complétant la fonction (ci-dessous) qui permet d'effectuer un parcours en profondeur du graphe (les tests d'assertions ne doivent pas retourner d'erreurs).
def chemin_existe # TODO: COMPLETER_ICI (ajouter les paramètres)
   """
   Auteur : 'Monsieur NSI'


   Args:
    graphe (dict): une liste d'ajacence
    sommet_depart (str): le sommet de départ
    sommet_arrivee (str): le ssommet d'arrivée (destination)
   """
   # On initialise la liste des sommets déjà visitée
   deja_visite = []
   # On initialise la pile
   pile = []
   # On empile le premier sommet
   pile.append(sommet_depart)
   # Tant que la pile n'est pas vide
   while pile:
        # Dépiler le sommet se trouvant en haut de la pile
        sommet = pile.pop()
        if sommet not in deja_visite:
            # TODO: COMPLETER ICI (il manque deux lignes)
            deja_visite.append(sommet)
            for voisin in graphe[sommet]:
                    pile.append(voisin)
   COMPLETER ICI (il manque une ligne)

# Ces tests ne doivent pas retourner d'erreur
assert chemin_existe(graphe, 'Paris', 'Tokyo')
assert chemin_existe(graphe, 'Paris', 'Chicago')
assert chemin_existe(graphe, 'Helsinki', 'Chicago')
assert not chemin_existe(graphe, 'Paris', 'CoinPerdu')
assert not chemin_existe(graphe, 'Brest', 'Chicago')
assert not chemin_existe(graphe, 'São Paulo', 'Abidjan')
assert  chemin_existe(graphe, 'Abidjan', 'São Paulo')

Exercice 2 (14 points)

Refaire les exercices (faits sur feuille et non terminés) de cette activité : https://snt-nsi.net/nsi_terminale/graphes/activite_1_graphes/