Algorithmes sur les graphes

Un graphe a pour "vocation" principale à être parcouru : c'est en effet ainsi que l'on va pouvoir par exemple trouver un chemin d'un sommet à un autre, trouver le plus court chemin entre deux sommets, vérifier qu'il existe un chemin entre deux sommets, etc...

Les applications en sont très nombreuses : trouver le chemin de sortie d'un labyrinthe, déterminer le plus court chemin entre deux routeurs dans un réseau ou entre deux villes sur une carte, déterminer le score PageRank © donné par Google aux pages web qu'il recense, etc...

Parcourir un graphe, c'est "l'explorer" sommet par sommet en partant d'un sommet de départ, le but étant de "découvrir" tous les sommets du graphe en fonction des relations qui existent entre eux.

Deux manières d'explorer un graphe existent :

• en largeur d'abord ( BFS = Breadth First Search ), qui explore le graphe "en cercles concentriques" en s'éloignant progressivement d'un sommet de départ.
• en profondeur d'abord ( DFS = Depth First Search ), qui explore le graphe en suivant la totalité des "descendants" du sommet de départ ( les "voisins des voisins" ) avant de passer au sommet suivant.

On a donc besoin de connaître les voisins de chaque sommet : l'implémentation sous forme de listes d'adjacence semble donc bien adaptée.

Parcours en largeur d'abord

Algorithme

On part d'un sommet initial du graphe appelé la racine de l'exploration.

Les sommets peuvent être dans deux "états" :

• soit ils ont été simplement "découverts" lors de l'exploration du graphe.
  On garde la trace des sommets déjà découverts de façon à ne pas traiter deux fois le même sommet ( sinon on pourrait rentrer dans un cycle de parcours sans fin...).
• soit ils ont été "explorés", c'est à dire qu'ils auront été entièrement traités par l'algorithme, et rentrent ainsi dans la liste des sommets parcourus

L'idée ici est qu'un sommet aura été "entièrement exploré" quand tous ses voisins directs ont été "découverts", puis on passe à l'exploration du sommet suivant.

Pour déterminer l'ordre de parcours des sommets, c'est le premier marqué qui sera le premier traité : on utilise donc une structure FIFO ( une file ) pour stocker les sommets à explorer une fois qu'ils ont été découverts.

fonction parcours_largeur: G = graphe, s = racine

	file ← file vide
	marque ← dictionnaire associant à chaque sommet un booléen, initialisé à Faux ( Faux = "non découvert" )
	parcours ← liste vide qui stockera les sommets successivement parcourus
	 
	marque[s] = Vrai
	enfiler(s,file)
	
	tant que file non vide:
		u = défiler(file)
		pour chaque sommet v adjacent au sommet u :
			si marque[v] est Faux alors
				marque[v] = Vrai
				enfiler(v, file)	
		stocker u dans parcours
		
	renvoyer parcours
			

Travail sur un exemple

Parcours en profondeur d'abord

Algorithme

On part là aussi d'un sommet initial du graphe appelé la racine de l'exploration, et on garde la trace des sommets déjà visités.

Un sommet a été totalement exploré quand tous ses voisins, puis les voisins de ses voisins, etc... ont été "découverts", puis on passe à l'exploration du sommet suivant.

Pour déterminer l'ordre de parcours des sommets, c'est donc ici le dernier marqué qui sera le premier traité : on utilise donc une structure LIFO ( une pile ) pour stocker les sommets à explorer.

fonction parcours_profondeur: G = graphe, s = racine

	pile ← pile vide
	marque ← dictionnaire associant à chaque sommet un booléen, initialisé à Faux ( Faux = "non découvert" )
	parcours ← liste vide qui stockera les sommets successivement parcourus
	 
	marque[s] = Vrai
	enpiler(s,pile)
	
	tant que pile non vide:
		u = dépiler(pile)
		pour chaque sommet v adjacent au sommet u :
			si marque[v] est Faux alors
				marque[v] = Vrai
				empiler(v, pile)	
		stocker u dans parcours
		
	renvoyer parcours
			

Travail sur un exemple

Parcours récursif

Vous le savez, dès qu'on utilise la récursivité, on met en jeu une pile qui stocke les résultats des appels récursifs de fonctions; ici, l'empilage et le dépilage des sommets à explorer peuvent être remplacés par des appels récursifs à la fonction de parcours :

fonction parcours_profondeur_récursif: G = graphe, u = sommet, marque, parcours

	marque[u] = Vrai
	stocker u dans parcours	
	
	pour chaque sommet v adjacent au sommet u:
		si marque[v] est faux alors :
			parcours_profondeur_récursif(G, v, marque, parcours)
			
	renvoyer parcours
			

Simple, non ? Et si, il y a bien un cas de base qui fait que la récursion se termine : quand il n'y a plus de sommets non marqués, il n'y a plus d'appels récursif !

L'inconvénient est de passer à chaque récursion de nombreux arguments...

On peut remarquer que :

• dans le cas de l'algorithme itératif, les voisins sont explorés du dernier au premier de la liste d'adjacence
• dans l'algorithme récursif, ils sont explorés du premier au dernier

Cela n'a dans la pratique aucune importante, il n'y a pas d'ordre particulier sur les sommets !

Exercices d'entraînement