Exercices : Parcours de graphes

Exercice 1

Voici quatre animations qui représentent 4 parcours différents sur le même graphe à partir du sommet ‘A’.

Repérer le parcours qui correspond bien à un parcours en profondeur du graphe à partir du sommet ‘A’.

Expliquer pourquoi les autres parcours ne sont pas un parcours en profondeur du graphe à partir du sommet ‘A’.

Parcours 1 :

Parcours 1

Parcours 1

Parcours 2 :

Parcours 2

Parcours 2

Parcours 3 :

Parcours 3

Parcours 3

Parcours 4 :

Parcours 4

Parcours 4
# Votre réponse ici

Exercice 2

Devant tant d’efforts pour comprendre les parcours, vous rêvez de partir en voyage sur le continent sud-américiain. Mais quel parcours effectuer pour visiter tous les pays de l’Amérique du Sud ?

Vous allez dans cet exercice :

  • utiliser un graphe implémenté comme dictionnaire avec la liste des successeurs, représentant les pays frontaliers d’Amérique du Sud,
  • programmer un parcours en profondeur,
  • l’appliquer au voyage de votre rêve !

Voici la carte des pays du continent sud-américain :

On considère le dictionnaire suivant qui permet d’associer à chaque pays d’Amérique du Sud la liste des pays partageant une frontière terrestre.

G = {}
G["France"] = ["Brésil","Suriname"]
G["Argentine"] = ["Bolivie","Brésil","Chili","Paraguay","Uruguay"]
G["Bolivie"] = ["Argentine","Brésil","Chili","Paraguay","Pérou","Uruguay"]
G["Brésil"] = ["Argentine","Bolivie","Colombie","France","Guyana","Paraguay","Pérou","Suriname","Uruguay","Venezuela"]
G["Chili"]=["Argentine","Bolivie","Pérou"]
G["Colombie"] = ["Brésil","Équateur","Pérou","Venezuela"]
G["Équateur"] = ["Colombie","Pérou"]
G["Guyana"] = ["Brésil","Suriname","Venezuela"]
G["Paraguay"] = ["Argentine","Bolivie","Brésil"]
G["Pérou"] = ["Bolivie","Brésil","Chili","Colombie","Équateur"]
G["Suriname"] = ["Brésil","France","Guyana"]
G["Uruguay"] = ["Argentine","Bolivie","Brésil"]
G["Venezuela"] = ["Brésil","Colombie","Guyana"]

Pour savoir quels sommets ont déjà été visités ou non, vous allez utiliser un dictionnaire dont les clés seront les sommets du graphe et les valeurs associées seront les chaînes de caractères soit “inconnu”, soit “visite”

  1. Créer une fonction initialiser qui prend comme paramètre un graphe et renvoie un dictionnaire dont les clés sont les sommets du graphe et la valeur est toujours “inconnu”.
# Votre code ci-dessous
  1. Créer une fonction visiter qui prend comme paramètre le dictionnaire associant à chaque sommet son état de connaissance et un sommet du graphe, fonction qui renvoie le dictionnaire de connaissance où la valeur associée au sommet entré est mise à ‘visite’
# Votre code ci-dessous
  1. Écrire en langage Python la procédure récursive parcours_longueur_rec correspondant à un parcours en profondeur en faisant aussi en sorte que chaque sommet qui vient d’être marqué soit affiché.

Cette procédure prend en argument un graphe et un sommet de ce graphe, sommet servant de point de départ au parcours.

Gérer l’affichage à l’aide de l’instruction print.

# Votre code ci-dessous
  1. Appliquer cette procédure au graphe modélisant les pays d’Amérique du Sud en prenant comme racine, c’est-à-dire sommet de départ la France (pour la Guyane Française). À la lecture de tous les pays que vous allez visiter, vous allez être profondément heureux.ses.
# Votre code ci-dessous

Exercice 3

Dans cet exercice, nous reprenons la situation de l’exercice précédent, mais nous allons utiliser un parcours en largeur. De plus, le graphe sera maintenant implémenté avec le module Networkx.

Vous prendrez une liste Python en guise de file en considérant que la tête de la file correspond au premier élément de la liste.

Le graphe sera supposé être un objet de la classe Graph() de la bibliothèque Networkx ; ceci permettra d’utiliser les méthodes de cette bibliothèque, comme :

  • graphe.neighbors(v) qui permet d’obtenir les voisins d’un sommet v du graphe graphe,

  • vous pourrez transtyper en liste l’itérable les voisins d’un sommet donné grâce à list (comme fait dans le cours : list(graphe.neighbors(v))).

  1. Écrire en langage Python une fonction parcours_largeur qui met en œuvre l’algorithme de parcours en largeur d’un graphe à partir d’un sommet donné.
# Votre code ci-dessous
  1. Tester cet algorithme de parcours en profondeur en prenant le graphe sur les pays d’Amérique du Sud.
# Votre code ci-dessous
  1. En vous aidant de la carte de l’Amérique du Sud ci-dessus, vérifier que la liste renvoyée correspond bien à un parcours en largeur.
# Votre réponse ci-dessous