Objectifs

Consignes

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 :

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.


Parcours d'un graphe

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

On peut parcourir un graphe :

Parcours en largeur

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

  1. On part d'un sommet;
  2. On visite ses voisins directs et on les enfile s'ils ne sont pas déjà présents dans la file;
  3. On défile (c'est-à-dire qu'on enlève la tête de la file);
  4. 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 ?

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


Parcours en profondeur

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

  1. On part d'un sommet que l'on empile;
  2. On dépile et on marque le sommet dépilé comme traité;
  3. 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;
  4. 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 :

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


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

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.


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_cycles(graphe,sommet).

Auteur : Hugues Malherbe