TP Terminale NSI : Algorithmes - parcours de graphes

Objectifs

Etre capable de représenter un graphe à partir d'une liste d'adjacences
Implémenter en Python des algorithmes de parcours de graphes et de recherche de chemins dans un graphe.
Utiliser ces fonctions Python pour résoudre un problème utilisant des graphes (labyrinthes,mots voisins ...)

Consignes

Vous devez répondre aux questions indiquées en couleur bleue.
Vous devez m'envoyer (en dépôt sur le cahier de texte d'Ecole Directe ou si ce n'est pas possible par mail à thalesm@free.fr) un fichier nommé NOM1_NOM2_TP_graphes.zip avec NOM1,NOM2 les noms des élèves du groupe qui un document texte avec les réponses aux questions numérotées de Q1 à Q.. et les sources de toutes les fonctions Python demandées.

Chaque fonction doit être documentée en utilisant les docstring et incluant plusieurs jeux de tests utilisant la bibliothèque doctest.

Structures de données pour représenter un graphe

La présentation des graphes en tant que structure données relationnelles a été faite précédemment avec ce contenu.

Nous avons notamment étudié deux manières de représenter un graphe :

par une matrice d'adjacence;
par une liste d'adjacence.

Dans ce TP,nous utiliserons pour représenter les graphes étudiés par leur liste d'adjacence associée.

Proposez une structure de données Python pour représenter le graphe suivant par une liste d'adjacence.

On peut utiliser un dictionnaire dans lequel les clefs sont les sommets et les valeurs la liste des voisins du sommet clef.


graphe = {"A":("B","D","E"),"B":("A","C"),"C":("B","D"),"D":("A","C","E"),"E":("A","D","F","G"),"F":("E","G"),"G":("E","F","H"),"H":("G")}

Parcours d'un graphe

Parcourir un graphe consiste à lister tous ses sommets une seule fois.

On peut parcourir un graphe :

soit pour lister simplement tous ses sommets;
soit pour trouver un chemin pour relier un sommet à un autre.

Parcours en largeur

L'idée du parcours en largeur repose sur l'utilisation d'une file de la manière suivante :

On part d'un sommet;
On visite ses voisins directs et on les enfile s'ils ne sont pas déjà présents dans la file;
On défile (c'est-à-dire qu'on enlève la tête de la file);
On recommence à partir du point 2 tant que la file n'est pas vide.

Voici la traduction en pseudo-code du parcours en largeur d'un graphe décrit ci-dessus.

F est une file vide
On enfile un sommet
Tant que F n'est pas vide
	S = Tête de F
	On enfile les voisins de S qui ne sont pas déjà présents dans la file et qui n'ont pas été déjà défilés
	On défile F
Fin Tant Que

Ecrire le code d'une fonction Python nommée parcours_en_largeur(graphe,sommet) qui parcourt en largeur un graphe à partir du sommet sommet et dont sa liste d'adjacence graphe est representée par un dictionnaire.

Cette fonction retournera la liste des sommets parcourus si le sommet sommet appartient bien au graphe et None sinon.

Testez votre fonction Python avec le graphe de l'exemple ci-dessus et avec "A" comme sommet de départ.

Quelle est la liste retournée par la fonction ?

La liste retournée est ['A','B','D','E','C','F','G','H'].

Quelle remarque peut-on formuler sur l'ordre des sommets affichés ?

On peut remarquer que l'algorithme de parcours en largeur permet de dresser la liste des sommets d'un graphe par distance croissante au sommet d'origine.

A partir du sommet A représenté en bleu,on a par distance croissante :

Les sommets à une distance de 1 du sommet A représentés en vert : B,D,E
Les sommets à une distance de 2 du sommet A représentés en rouge : C,F,G
Le sommet à une distance de 3 du sommet A représenté en jaune : H

On retrouve bien dans la liste retournée par la fonction de parcours en largeur à partir du sommet A les sommets classés par ordre de distance croissante au sommet A : ['A','B','D','E','C','F','G','H'].

On peut se servir de ce parcours pour trouver un chemin de distance minimale entre deux sommets.

Parcours en profondeur

L'idée du parcours en profondeur repose sur l'utilisation d'une pile de la manière suivante :

On part d'un sommet que l'on empile;
On dépile et on marque le sommet dépilé comme traité;
On empile chacun des voisins su sommet dépilé qui ne sont pas déjà dans la pile et qui n'ont pas été déjà été traités;
On recommence à partir du point 2 tant que la pile n'est pas vide.

Voici la traduction en pseudo-code du parcours en profondeur d'un graphe décrit ci-dessus.

P est une pile vide
On empile un sommet
Tant que P n'est pas vide
	S = dépile(P)
	On empile les voisins de P qui ne sont pas déjà présents dans la pile et qui n'ont pas été déjà dépilés
Fin Tant Que

Proposer le code d'une fonction Python nommée parcours_en_profondeur(graphe,sommet) qui implémente l'algorithme décrit ci-dessus

Recherche de chemins dans un graphe

Le loup,la chèvre,un chou et un passeur ....

Sur la rive d'un fleuve se trouvent un loup,une chèvre,un chou et un passeur. Le problème consiste à tous les faire passer sur l'autre rive à l'aide d'une barque,menée par le passeur,en respectant les règles suivantes :

la chèvre et le chou ne peuvent pas rester sur la même rive sans le passeur;
la chèvre et le loup ne peuvent pas rester sur la même rive sans le passeur;
le passeur ne peut mettre qu'un seul "passager" avec lui.

On décide de représenter le passeur par la lettre P,la chèvre par la lettre C,le loup par L et le chou par X.

Représenter ce problème à l'aide d'un graphe où les sommets sont tous les états possibles sur la rive de départ (par exemple,"PLCX" est un sommet représentant le fait que tous sont sur la rive de départ.)

Trouver une solution au problème en indiquant chacun des déplacements (si possible une solution avec le moins de déplacements possibles).

Le graphe doit traduire les différents déplacements possibles entre chaque état. On peut alors utilser une représentation comme suit :

Résoudre le problème consiste à trouver un chemin du sommet PLCX au sommet vide.

Une solution possible est donc :

PLCX -> LX -> PLX -> X -> PCX -> C -> PC -> vide

Ce qui se traduit par les déplacements suivants :

au départ,le passeur amène la chèvre sur la rive de destination,laissant le loup et le chou sur la rive de départ;
le passeur revient seul et se retrouve avec le loup et le chou;
il amène le loup sur la rive de destination,laissant le chou;
il ramène la chèvre sur la rive de départ (elle ne peut pas rester avec le loup sur la rive de destination);
il amène le chou sur la rive de destination,laissant la chèvre seule;
il revient seul (le chou et le chou pouvant rester ensemble sur la rive de destination);
il se retrouve avec la chèvre sur la rive de départ et l'amène sur l'autre rive.

Si vous êtes intéressé par ce type de jeu,je vous propose une autre version développée autour d'une animation codée en JavaScript et dont l'énoncé du jeu m'avait été proposé par un élève de troisième il y a quelques années.

Question facultative : Proposer une modélisation avec un graphe pour résoudre ce jeu.

Si vous n'arrivez pas à résoudre le jeu à partir de l'animation graphique,répondez à cette question et vous aurez accès au "cheat code" qui donne la solution au jeu.

Quel est le nom du célèbre savant suisse (surnommé le prince des mathématiciens) qui est connu pour être à l'origine de la théorie des graphes à travers du célèbre problème des sept ponts de Königsberg ?

Algorithmes de recherche d'un chemin entre deux sommets

Implémentez en Python une fonction Python nommée cherche_chemin(graphe,depart,arrivee) qui recherche et retourne un chemin (s'il existe) entre les sommets depart et arrivee dans le graphe graphe à partir de l'algorithme suivant :

Fonction cherche_chemin(graphe,depart,arrivee)
	P ← pile vide
	empiler le couple (depart,[depart]) dans P
	Tant que P n'est pas vide faire
		(sommet,chemin) ← tête de P
		listes_nouveaux_sommets_voisins ← liste des sommets adjacents à sommet qui ne sont pas dans chemin
		Pour un_sommet dans listes_nouveaux_sommets_voisins
			Si un_sommet = arrivee alors
				retourner chemin + [un_sommet]
			sinon
				empiler (un_sommet,chemin + [un_sommet])
			FinSi
		FinPour
	FinTantQue
FinFonction

On testera la fonction Python cherche_chemin(graphe,depart,arrivee) avec le graphe du début :

représenté par sa liste d'adjacence : graphe = {"A":("B","D","E"),"B":("A","C"),"C":("B","D"),"D":("A","C","E"),"E":("A","D","F","G"),"F":("E","G"),"G":("E","F","H"),"H":("G")} et avec tous les couples possibles (depart,arrivee).

Comme le graphe possède 8 sommets,il y a 8 × 7 = 56 couples de sommets (depart,arrivee) possibles (avec depart ≠ arrivee)

					
						A B ['A','B']
						A C ['A','E','D','C']
						A D ['A','D']
						A E ['A','E']
						A F ['A','E','F']
						A G ['A','E','G']
						A H ['A','E','G','H']
						B A ['B','A']
						B C ['B','C']
						B D ['B','C','D']
						B E ['B','C','D','E']
						B F ['B','C','D','E','F']
						B G ['B','C','D','E','G']
						B H ['B','C','D','E','G','H']
						C A ['C','D','A']
						C B ['C','B']
						C D ['C','D']
						C E ['C','D','E']
						C F ['C','D','E','F']
						C G ['C','D','E','G']
						C H ['C','D','E','G','H']
						D A ['D','A']
						D B ['D','E','A','B']
						D C ['D','C']
						D E ['D','E']
						D F ['D','E','F']
						D G ['D','E','G']
						D H ['D','E','G','H']
						E A ['E','A']
						E B ['E','D','C','B']
						E C ['E','D','C']
						E D ['E','D']
						E F ['E','F']
						E G ['E','G']
						E H ['E','G','H']
						F A ['F','G','E','A']
						F B ['F','G','E','D','C','B']
						F C ['F','G','E','D','C']
						F D ['F','G','E','D']
						F E ['F','E']
						F G ['F','G']
						F H ['F','G','H']
						G A ['G','F','E','A']
						G B ['G','F','E','D','C','B']
						G C ['G','F','E','D','C']
						G D ['G','F','E','D']
						G E ['G','E']
						G F ['G','F']
						G H ['G','H']
						H A ['H','G','F','E','A']
						H B ['H','G','F','E','D','C','B']
						H C ['H','G','F','E','D','C']
						H D ['H','G','F','E','D']
						H E ['H','G','E']
						H F ['H','G','F']
						H G ['H','G']

Vérifiez si les chemins proposés sont de plus courte distance. Si ce n'est pas le cas,citez des chemins donnés par la fonction Python qui ne sont pas de plus courte distance.

Dans le tableau suivant,sont affichés les chemins qui ne sont pas de plus courte distance.

Sommet Départ

Sommet Arrivée

Chemin proposé par la fonction Python

Chemin plus court

['A','E','D','C']

['A','D','C']

['B','C','D','E']

['B','A','E']

['B','C','D','E','F']

['B','A','E','F']

['B','C','D','E','G']

['B','A','E','G']

['B','C','D','E','G','H']

['B','A','E','G','H']

['D','E','A','B']

['D','C','B']

['E','D','C','B']

['E','A','B']

['F','G','E','A']

['F','E','A']

['F','G','E','D','C','B']

['F','E','A','B']

['F','G','E','D','C']

['F','E','D','C']

['F','G','E','D']

['F','E','D']

['G','F','E','A']

['G','E','A']

['G','F','E','D','C','B']

['G','E','A','B']

['G','F','E','D']

['G','E','D']

['H','G','F','E','A']

['H','G','E','A']

['H','G','F','E','D','C','B']

['H','G','E','A','B']

['H','G','F','E','D','C']

['H','G','E','D','C']

['H','G','F','E','D']

['H','G','E','D']

A partir de la fonction précédente, proposez une autre fonction cherche_tous_chemins(graphe,depart,arrivee) qui retourne la liste de tous les chemins entre deux sommets.

Complétez la fonction qui retourne la liste de tous les chemins entre deux sommets pour créer une fonction nommée cherche_chemin_plus_court(graphe,depart,arrivee) qui retourne le plus court chemin entre deux sommets.

Cycle d'un graphe

Dans un graphe non orienté, un cycle est une suite d'arêtes consécutives dont les deux sommets extrémités sont identiques.

Dans le graphe :

A - B - C - D - E - A est un cycle.

Proposez le code d'une fonction nommée cherche_cycles(graphe,sommet) qui retourne la liste de tous les cycles de sommet sommet du graphe graphe. Il serait judicieux que cette fonction appelle la fonction cherche_tous_chemins(graphe, depart,arrivee).

Proposez le code d'une fonction nommée cherche_tous_cycles(graphe) qui retourne la liste de tous les cycles du graphe graphe. Il serait judicieux que cette fonction appelle la fonction cherche_tous_chemins(graphe, depart,arrivee).

Auteur : Hugues Malherbe