En terminale

• Introduction
• Parcours en largeur
• Parcours en profondeur
• Recherche la présence d'un cycle
• Chercher un chemin dans un graphe
• Exercices

Pour pouvoir coder les algorithmes, il va falloir au préalabe arriver à coder un graphe. Dans la suite, on suppose que l'on code les graphes récursivement à partir de sommets liées les uns aux autres par la successeurs, prédécesseurs.

Le travail déjà fait sur les arbres va nous servir ici, pour le parcours en largeur et en profondeur, les principes seront les mêmes.

Le parcours en largeur (BFS Breadth First Search ) d'un graphe est le plus simple.

• On visite le sommet de départ.
• On observe ensuite les sommets successeurs du sommet de départ et on les enfile (on les places dans une liste les uns après les autres) sauf s'ils ont déjà été visités (c'est la différence avec l'arbre, on n'était pas obligé de retenir que l'on avait déjà visité un sommet vu qu'un seul chemin mène au sommet).
• S'ils n'ont jamais été visité, on les rajoute à la liste des visités (oui, on ne veut pas tourner en rond)
• On défile (on prend le premier que l'on a mis FIFO)
• On recommence au point 2 tant que la file n'est pas vide/li>

Il va falloir visiter les noeuds d'un même niveau et se souvenir qu'ensuite on va descendre voir chacun de leurs enfants qui deviendront eux même un souvenir...

Pour garder en mémoire les noeuds visités dont on ira voir plus tard les enfants, on les places dans une liste. Mais attention, il ne faut pas prendre le dernier de la liste pour la lecture mais le premier. On est donc en présence d'une pile de type fifo (first in first out).

fonction parcours_largeur(sommet_depart)
	observe = créer pile fifo
	visite=liste_vide
	ajouter sommet_depart à visite et à observe
	tant que observe n'est pas vide
		sommet recoit le premier élément de observe
			(pop, l'élément est supprimé de la liste)
		afficher(noeud)  #ou toute autre acion
		pour tout les successeurs de noeud
			si successeurs n'est pas dans visite:
				ajouter successeurs à observe
			sinon:
				ajouter successeurs à visite

En pratique, faire un parcours en largeur permet de visiter les sommets les plus proches (en terme d'étapes) en premier. Imaginons le cas de stations de metros, on aurait d'abord les station à la distance 1 arrêt du départ, puis toutes les stations à la distance 2 arrêts etc..

Il s'agit de l'idée inverse de la précédente. Tant que l'on peut trouver un successeur non visité, on va au successeur. Lorsqu'on n'en trouve plus, on l'observe et on remonte. Il va donc falloir se souvenir des noeuds que l'on n'a pas affiché car on veut tous ses successeurs. Dès que l'on remonte à un sommet, on veut afficher ses successeurs. On est donc remonté au sommet juste précédent, donc le DERNIER dont on voulait se souvenir. On est donc en présence d'une pile de type LIFO (last in first of). En changeant la pile FIFO de l'algorihtme de parcours en largeur par une pile LIFO, on obtient l'algorithme de parcours en profondeur!

fonction parcours_profondeur(sommet_depart)
	observe = créer pile Lifo
	visite=liste_vide
	ajouter sommet_depart à visite et à observe
	tant que observe n'est pas vide
		sommet recoit le dernier élément de observe
			(pop, l'élément est supprimé de la liste)
		afficher(noeud)  #ou toute autre acion
		pour tout les successeurs de noeud
			si successeurs n'est pas dans visite:
				ajouter successeurs à observe
			sinon:
				ajouter successeurs à visite

Il existe plusieurs type de parcours en profondeur. L'algorithme itératif précédent donne l'odre préfixe.

Dans le parcours prefixe, on lit la racine puis on parcourt récursivement ses successeurs non visités.

Dans le parcours sufixe, on parcourt récursivement tous ses successeurs, puis on lit le sommet.

Ces parcours peuvent tous être codés en utilisant une fonction récursive. Selon, la méthode désirée, il suffira de changer la position de la ligne qui lit la racine du sous arbre traité (enlever les dièses sur la ligne désirée).

Affichage_XXXfixe(sommet_depart)
	si NON est_vide(sommet_depart):
		visite=liste_vide
		ajouter sommet_depart à visite
		#Afficher valeur de sommet_depart  (pour préfixe)
		pour tous les successeurs de sommet_depart:
			si le successeur n'est pas dans visite:
				Affichage_XXXfixe(successeurs)
		#Afficher valeur de sommet_depart  (pour sufixe)
 

Le parcours en profondeur donne la réponse à la question: "Il y a-t-il un cycle dans mon graphe ?". Il y aura un cycle dès que successeur sera dans déjà visité!

Il suffit donc de faire un parcours en profondeur et d'en sortir dès que successeur est dans visite (dans l'algorithme itératif).

La recherche de l'existence d'un chemin d'un sommet à un autre peut se faire à l'aide d'un des deux algorithmes de parcours précédents. Il suffit de mettre un booléen à vrai lorsque l'on lit le sommet destination.

L'algorithme de Dijkstra permet de trouver le plus court chemin! Il sera donné en exercice.

1. blabla
2. blabla