Algorithmes sur les graphes

Principe

Utilité

Comme on l'a déjà fait avec les arbres, on a souvent besoin de parcourir un graphe : 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.

Lors du parcours, les sommets peuvent être alors dans deux "états" :

• soit ils ont été simplement "visités" ( = "découverts" ) lors de l'exploration du graphe.
• 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

Comme pour les arbres, deux manières d'explorer un graphe existent :

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

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.

Différence avec le parcours d'un arbre

Vous vous souvenez de l'algorithme de parcours d'un arbre, en profondeur par exemple :

traiter le nœud courant ( pour un parcours préfixe...)

si le nœud courant a un fils gauche:
    parcourir le fils gauche
si le nœud courant a un fils droit:
    parcourir le fils droit
			

On "descend" donc naturellement dans l'arbre jusqu'aux feuilles, il n'y a aucun moyen de "revenir sur ses pas" dans un arbre ( Rappel : un arbre est un graphe orienté acyclique ).

A l'inverse, dans un graphe, a fortiori dans un graphe non-orienté, il existe toujours une probabilité pour que l'on revienne sur un sommet déjà parcouru, si il existe l'arc/l'arête qui permette ce "retour en arrière"; le parcours "tourne alors en boucle" à l'infini...

Conséquence : dans le cas d'un graphe, pour éviter de parcourir plusieurs fois le même sommet, on va garder la trace des sommets déja visités :

traiter le sommet courant

si le sommet voisin 1 n'a pas encore été visité:
    marquer le voisin 1 comme visité 
    parcourir le graphe à partir de 1
si le sommet voisin 2 n'a pas encore été visité:
    marquer le voisin 2 comme visité
    parcourir le graphe à partir de 2
...
etc.( pour chaque sommet voisin du sommet courant)
			

Pour garder la trace des sommets déjà visités, il y a plusieurs solutions :

• stocker les sommets explorés dans un tableau : la présence ou l'absence d'un sommet dans ce tableau permettra de savoir si il a déjà été visité ou non;
• utiliser un tableau associatif ( dictionnaire ), dans lequel les clés sont les sommets, et les valeurs, soit un booléen True/False pour savoir si le sommet a déjà été visité, soit une autre information ( comme par exemple, le prédécesseur du sommet courant dans le parcours ( cela pourra servir dans certaines applications ).

Parcours en profondeur d'abord

Algorithme

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.

Parcours récursif

fonction parcours_profondeur_récursif: G = graphe, u = sommet ( celui de départ au premier appel )

	traiter le sommet u

	pour chaque sommet v voisins sommet u:
		si v n'a pas encore été visité :
		    marquer v comme visité
			 parcours_profondeur_récursif(G, v)
			

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 ( voir l'implémentation au chapitre suivant ).

Parcours itératif

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

fonction parcours_profondeur: G = graphe, s = sommet de départ

	pile ← pile vide
	 
	marquer s comme visité
	enpiler(s, pile)
	
	tant que pile non vide:
		u = dépiler(pile)
		traiter le sommet u
		pour chaque sommet v adjacent au sommet u :
			si v n'a pas encore été visité:
				marquer v comme visité
				empiler(v, pile)	
			

Travail sur un exemple

( On remarque que l'algorithme semble "revenir en arrière" à chaque intersection : on parle de backtracking, et cela a de nombreuses applications...)

Parcours en largeur d'abord

Algorithme

Pour déterminer l'ordre de parcours des sommets, c'est le premier visité qui sera le premier exploré : 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 = départ du parcours

	file ← file vide
		 	
	enfiler(s,file)
	marquer s comme visité
	
	tant que file non vide:
		u = défiler(file)
		traiter le sommet u
		pour chaque sommet v adjacent au sommet u :
			si v n'a pas encore été visité:
				enfiler(v, file)	
				marquer v comme visité
			

( oh mais dites donc, c'est exactement le même que le parcours en profondeur itératif, avec une file à la place d'une pile 😮 ...)

Travail sur un exemple

Exercices d'entraînement