La théorie des graphes


précédentsommaire

II. Parcours de graphes

Avant de voir les différents types de parcours, il convient tout naturellement de préciser ce qu'est un parcours ou plutôt quels sont les parcours possibles d'un graphe.

Tout d'abord, il y a deux parcours d'un graphe qui ne reposent pas sur les mêmes éléments. En effet, un type de parcours consiste à  explorer le graphe en passant par tous les sommets. Ce type de parcours est un parcours dit hamiltonien. L'autre type de parcours est un parcours dit Eulérien et consiste à emprunter toutes les arêtes du graphe.

Les parcours peuvent se faire de deux sortes, on a le parcours en largeur et le parcours en profondeur.

Le parcours en largeur consiste, à partir d'un sommet donné, de visiter tous les sommets successeurs. On répète l'opération tant qu'il existe des sommets non visités. Ce type de parcours est d'une manière imagée, une sorte de propagation. En effet, on explore tous les sommets qui sont directement accessibles puis ceux qui sont accessibles en passant par un sommet, puis deux et ainsi de suite.

Le parcours en profondeur lui ne fonctionne pas de la même manière, en effet, il explore un sommet et essaie d'aller le plus loin possible. Quand ce n'est pas possible, on revient en arrière et on essaie de parcourir en profondeur en prenant un sommet qui n'a pas encore été visité.

Une chose très importante et qu'il faut toujours garder à l'esprit dans les parcours de graphes est que les graphes peuvent contenir des cycles et donc que les algorithmes naïfs peuvent boucler indéfiniment en empruntant ces cycles. Les solutions que nous allons voir ici prennent en compte tout ceci.

II-A. Parcours en largeur

Le parcours en largeur consiste comme nous venons de le dire à parcourir le graphe en passant par les sommets directement voisins puis ceux dont il faut passer par un sommet pour les atteindre, et ainsi de suite.

Les informations à  prendre en compte pour ce type de parcours sont :

  • - Un sommet déjà  visité ne doit pas être revisité.
  • - On explore les sommets successeurs directs.

L'algorithme de base repose sur l'utilisation d'une pile qui va maintenir à jour la liste des sommets à visiter.

Prenons le graphe suivant :

Image non disponible

Imaginons que nous voulions parcourir le graphe en largeur en partant du sommet 1. Le parcours en largeur de ce graphe donnerait la liste suivante : 1 2 3 4 6 5 7 8. Une autre solution serait la suivante : 1 3 2 6 4 5 8 7. Elles sont toutes les deux valables.

Détaillons un peu comment se déroule le parcours. On part du sommet 1, on liste tous les sommets successeurs, il s'agit donc des sommets 2 et 3. Marquons les d'une couleur différente pour ne pas les passer deux fois :

Image non disponible

Il n'y a plus de sommets directement accessibles à partir du sommet 1. Il faut donc maintenant chercher ceux qui sont accessibles en passant par un sommet. Ceci revient en fait à chercher les successeurs des sommets précédemment parcourus. On doit donc parcourir à nouveau en largeur mais en partant des sommets précedemment explorés.

On commence par le sommet 2, le seul successeur est le sommet 4, on l'affiche et on le marque comme étant parcouru. On passe au sommet 3, tout comme le sommet 2, il n'a qu'un seul successeur. On le marque comme déjà  parcouru.

A ce stade, nous en sommes ici :

Image non disponible

On vient donc de parcourir tous les sommets accessibles depuis le sommet 1 en passant par un sommet. Il faut donc maintenant parcourir les commets accessibles en passant par deux sommets.

Il faut donc parcourir en partant des sommets 4 et 6. Le sommet 4 a deux successeurs, le sommet 5 et le sommet 6. Or le sommet 6 a déjà été visité, on ne doit donc pas le mettre dans la file des sommets à parcourir. On ajoutera seulement le sommet 5 à la file des sommets à parcourir.

Concernant le parcours à partir du sommet 6, il n'y a rien à faire, en effet, celui ci n'a pas de successeurs.

On réitère le processus jusqu'à avoir parcouru tous nos sommets.

Essayons maintenant de dégager un algorithme de cet exemple. Il parait assez clair qu'il faut avoir une file pour stocker la liste des sommets à parcourir et qu'il nous faut un moyen d'identifier les sommets déjà parcourus.

Pour identifier les sommets parcourus, habituellement, on utilise le coloriage. Généralement, un sommet est blanc s'il n'a pas été parcouru et est noir dans le cas contraire. Certains mettent les sommets à parcourir en gris mais cela n'a aucun intérêt pour le fonctionnement de l'algorithme, il s'agit juste d'un moyen pour visualiser le parcours.

Au tout début de l'algorithme, aucun sommet n'a été visité, il nous faudra donc une fonction d'initialisation qui va mettre tous nos sommets en blanc dès le début. L'algorithme d'initialisation sera donc le suivant :

 
Sélectionnez

Pour tous les sommets S du graphe faire
     S.couleur = blanc;

Rien de très compliqué de cette manière formelle, néanmoins, nous verrons un peu plus loin comment réaliser cela via des listes d'adjacence. Concentrons-nous plutôt pour l'instant sur l'algorithme.

Comme nous l'avons dis, pour parcourir le graphe, nous allons nous servir d'une file qui va stocker la liste des sommets à parcourir. Il faut donc commencer dans notre algorithme par y stoquer le sommet par lequel on va commencer le parcours.

Ensuite l'algorithme est relativement simple, on prend le sommet de la file et on y effectue les choses suivantes :

  • - parcourir la liste des successeurs Si de S :
  • - Si Si est blanc alors Si devient noir et on ajoute Si à la File.

L'algorithme s'arrête donc tout naturellement lorsque la file devient vide. Ceci veut tout simplement dire qu'il n'y a plus de sommet à visiter.

Voici donc l'algorithme :

 
Sélectionnez

ParcoursLargeur(G : Graphe , S : Sommet )
{
     F : File de sommets;

     Initialiser(G);

     S.couleur = Noir;
     Ajouter S à F;

     tant que F n'est pas vide faire
     
          S = Defiler(F);

          pour tous les successeurs Si de S faire

               si Si.couleur == Blanc alors
                    Si.couleur <- Noir;
                    Ajouter Si à F;
               fin si

          fin pour
     fin tant que
}

Voici donc notre premier algorithme de parcours de graphe, ce dernier est l'algorithme le plus simple que l'on peut faire avec un graphe. Il est néanmoins utilisé, tel quel ou sous une forme légèrement modifiée, dans d'autres algorithmes plus évolués. Il convient donc que vous le maîtrisiez avant de vous lancer dans d'autres algorithmes sur les graphes.

II-B. Parcours en profondeur

Le parcours en profondeur est le deuxième type de parcours de graphes que nous verrons ici. Il s'agit d'un parcours où l'on explore un chemin jusqu'a ce que l'on ne puisse plus avancer dans le graphe. Ce cas arrive lorsque l'on a soit parcouru tout le graphe, soit lorsque l'on est arrivé sur un sommet qui n'a pas de successeurs. Dans ce cas, il faut rebrousser chemin dans notre exploration et partir d'un sommet qui n'a pas été visité.

Nous allons donner, dans un premier temps un algorithme récursif pour le parcours en profondeur, celui ci est assez simple. En effet, il se base sur les principes suivants : si un sommet n'a pas été visité alors il faut le parcourir en profondeur. S'il a déjà été visité alors il ne faut rien faire. L'exploration récursive s'arrête tout simplement lorsque l'on a parcouru tous les sommets.

Il est très simple de montrer que l'algorithme se termine puisque le graphe a un nombre fini de sommets et qu'à chaque exploration dans le graphe, on diminue le nombre de sommets qui n'ont pas encore été visités.

Le parcours consiste donc à marquer le sommet courrant puis pour tous les sommets Si successeurs de faire un parcours en profondeur si le sommet n'a pas été marqué.

Voici donc l'algorithme récursif pour parcourir un graphe en profondeur :

 
Sélectionnez

Initialiser(G);

ParcoursProfondeur( Graphe G, Sommet S)
{
	S.couleur <- Noir;
	
	Pour tous les successeurs Si de S faire
		Si Si.couleur == Blanc alors
			ParcoursProfondeur(G,Si);
		Fin si
	Fin Pour		
}

Comme pour l'autre algorithme, vous avez remarquez que l'on fait appel à la fonction Initialiser avant d'appeler l'algorithme en lui même.

Voilà donc deux algorithmes très simples pour le parcours de graphes. Nous verrons dans la suite qu'ils sont utilisés assez fréquemment directement ou en impliquant de petits changements pour réaliser des algorithmes plus évolués.


précédentsommaire

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+   

  

Les sources présentées sur cette page sont libres de droits et vous pouvez les utiliser à votre convenance. Par contre, la page de présentation constitue une œuvre intellectuelle protégée par les droits d'auteur. Copyright © 2006 Romuald Perrot. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc. sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.