Séquence 1 – Parcourir un graphe en profondeur (DFS, Depth-First Search)
Objectifs d’apprentissage ou d’entraînement et pré-requis (acquis antérieurs mobilisés)
- Notions de graphe, graphe non orienté, graphe orienté, sommet, arête, arc, représentation sagittale d’un graphe (Spécialité NSI – Terminale – Thème 1 : structures de données – Module 4)
- Notion de pile (Spécialité NSI – Terminale – Thème 1 : structures de données – Module 2)
Programmation en langage Python : compétences requises ( à acquérir, à mobiliser, à développer, à maîtriser)
- Type construit ‘dictionnaire’ : syntaxe et méthodes (Spécialité NSI – Première et Terminale)
Soit le graphe représenté en langage Python de la façon suivante :
graphe={
'A':['B','D','E'],
'B':['A','C'],
'C':['B','D'],
'D':['A','C','E'],
'E':['A','D','G','F'],
'F':['E','G'],
'G':['E','F','H'],
'H':['G']
}Rédiger – en utilisant le vocabulaire adapté – une courte présentation de cette façon d’implémenter un graphe en langage Python
Construire une représentation sagittale de ce graphe.
Examiner le document qui suit. Il présente une implémentation en langage Python de la fonction qui réalise le parcours en profondeur d’un graphe.
def gpp(graphe, som_depart):
""" Parcours en profondeur de 'graphe' à partir du sommet 'som_depart' """
parcours=[]
pile=[]
pile.append(som_depart)
while pile != []:
sommet=pile.pop()
if sommet not in parcours:
parcours.append(sommet)
for voisin in graphe[sommet]:
if voisin not in parcours:
pile.append(voisin)
return parcoursSans utiliser un éditeur/interpréteur de langage Python, indiquer quel serait le résultat de l’exécution de ces instructions pour le graphe donné plus haut et les sommets de départ suivants : ‘A’, ‘B’, ‘E’ et ‘H’.
Vérifier les réponses données à la questions précédentes en exécutant la fonction ‘gpp()’ dans un éditeur/interpréteur de langage Python.
A partir de ce document, écrire l’algorithme de parcours en profondeur d’un graphe.
Dans la représentation du graphe donnée plus haut, remplacer la ligne « ‘E’:[‘A’,’D’,’G’,’F’], » par « ‘E’:[‘F’,’G’,’D’,’A’], » et ré-exécuter la fonction ‘gpp()’ avec les mêmes sommets de départ. Comparer les parcours obtenus avant et après la modification effectuée : formuler un constat et en tirer une conclusion générale sur le résultat d’un parcours en profondeur.
La fonction précédente est une implémentation selon un mode de programmation itératif.
Écrire une implémentation de l’algorithme de parcours en profondeur d’un graphe selon un mode de programmation récursif.