• 12 heures
  • Moyenne

Ce cours est visible gratuitement en ligne.

course.header.alt.is_video

course.header.alt.is_certifying

J'ai tout compris !

Mis à jour le 03/02/2020

Parcourez un graphe en largeur

Connectez-vous ou inscrivez-vous gratuitement pour bénéficier de toutes les fonctionnalités de ce cours !

Découvrez l'algorithme de parcours en largeur

Ce chapitre est consacré à la notion de « parcours de graphe ». Nous allons en particulier aborder le parcours en largeur.

La topologie d’un graphe exprime la façon dont on peut passer d’un sommet à un autre. Un parcours de graphe est une façon de partir d’un point de départ puis, en s’appuyant sur cette topologie, de passer en revue tous les sommets.

Plus précisément, le parcours en largeur, consiste à :

  • d’abord les sommets qui sont voisins du point de départ ;

  • puis ceux qui sont voisins des voisins, on va dire à distance 2 ;

  • puis ceux qui sont à distance 3 ;

  • etc., jusqu’à avoir tout parcouru.

Regardons l’algorithme.

On commence par définir un état par sommet :

  • au début il sera « non visité » ;

  • puis deviendra « visité » ;

  • au final, il sera « traité ».

On définit aussi une « file » des sommets à traiter F.

Une file est une structure de donnée qui fonctionne comme une file d’attente : on insère des éléments en fin de file et on les récupère en tête, dans l’ordre d’insertion.

  • La première étape de BFS consiste à insérer le sommet de départ dans F et à mettre son état à « visité ».

  • Ensuite, tant que la file F n’est pas vide, on prend le sommet à sa tête. Disons qu’il s’appelle U. Pour chacun des voisins de U dont l’état est « non visité », on l’insère dans F et on passe son état à « visité ». L’état de U passe alors à « traité » et il sort de F.

  • Ainsi, après la première itération, le point de départ n’est plus dans F et son état est « traité ». Par contre, F contient tous ses voisins et ils sont dans l’état « visité ».

  • À la seconde itération, un des voisins du point de départ (le premier dans l’ordre où on les a insérés) devient « traité » et extrait de F. Dans la file, on retrouve tout d’abord les voisins restants du point de départ. Il y a ensuite les voisins du sommet que l’on vient de traiter qui ne sont pas aussi voisins du point de départ.

  • L’algorithme continue à itérer ainsi, jusqu’à ce que la file soit vide.

Chaque sommet n’est inséré qu’une seule fois dans F : quand son état devient « visité ». À chaque itération de la boucle, un sommet supplémentaire est traité.

L’algorithme termine donc quand tous les sommets sont traités : après une itération par sommet. À la fin, on obtient un ordre de parcours de sommets qui est l’ordre dans lequel ils ont été marqués « traités ».

L'algorithme de parcours en largeur, BFS, donne un ordre sur les sommets. Ce parcours permet aussi de définir des plus courts chemins.

Prouvez que l'algorithme permet de construire des plus courts chemins

Nous avons vu que BFS parcourt les sommets du graphe dans un ordre bien particulier.  Il numérote d’abord les voisins du point de départ, puis ceux qui sont voisins des voisins, etc.
Cela forme des niveaux.

Au cours de l’algorithme BFS, on peut conserver une information supplémentaire : lorsqu’un sommet est inséré dans la file F, on mémorise le sommet qui est en train d’être traité. Appelons-le « prédécesseur ». Le niveau du sommet inséré dans F est celui du prédécesseur + 1.

Le niveau du point de départ est 0. Lorsqu’il est traité, on insère ses voisins dans F. Ceux-ci sont donc de niveau 1 et ont comme prédécesseur le point de départ.

En itérant l’algorithme, on obtient un arbre : chaque sommet a un unique prédécesseur. On appelle cela un « arbre BFS ». Il est enraciné au sommet de départ.

Il est alors très facile de router de l’information d’un sommet vers le point de départ : le sommet transmet à son prédécesseur qui fait de même. Tous les sommets intermédiaires font la même opération, jusqu’à arriver au point de départ.

Les chemins entre les sommets et le point de départ sont des plus courts chemins en nombre de liens traversés : un à chaque niveau. En effet, pour faire plus court, il faudrait un lien entre deux niveaux non successifs. Vu le déroulement de BFS, c’est impossible.

L'algorithme de parcours en largeur, BFS, calcule des plus courts chemins si l’on opère une remontée de gradient. Voyons comment un tel algorithme peut se traduire en protocole distribué.

Appréhendez les applications de l'algorithme dans un réseau, en termes de routage et adressage

Écrire BFS comme un algorithme distribué, c’est décrire la réaction de chaque sommet à des messages transmis.

Tous les sommets qui reçoivent le message vont mémoriser l’identifiant de l’émetteur qui devient leur prédécesseur. À leur tour, ils diffusent un message en indiquant leur identifiant, l’identifiant de leur prédécesseur et leur niveau (0+1).

Parmi tous ceux qui reçoivent ce message, il y a 4 catégories :

  • le prédécesseur : il reçoit un message du niveau suivant et sait donc qu’il a un successeur ;

  • les sommets d'un niveau inférieur ou égal : ils peuvent ignorer le message ;

  • les sommets qui n’ont pas encore de niveau mémorisent l’émetteur du message comme leur prédécesseur, fixent leur niveau au niveau transmis +1 et renvoient un message similaire : identifiant, prédécesseur, niveau ;

  • il est possible qu’un sommet voisin de l’émetteur aie déjà reçu un message d’un autre sommet. Cela arrive si un sommet est plus rapide qu’un autre pour transmettre ses messages. Il faut alors que le sommet qui s’est “trompé” mette à jour son prédécesseur, son niveau et retransmette son message.

L'algorithme BFS peut facilement se traduire en protocole distribué. On le retrouve dans plusieurs algorithmes de routage ou d’adressage des réseaux, par exemple en ZigBee.

Dans le chapitre suivant, nous allons voir comment calculer le plus court chemin dans un graphe.

Exemple de certificat de réussite
Exemple de certificat de réussite