Algorithme BFS (Breadth First Search)

Fonctionnalités de l'algorithme BFS

  • BFS est un algorithme de parcours de graphe par recherche en largeur d'abord (Breadth First Search).
  • Fonctionne avec les graphes orientés et non-orientés.
  • Permet la détection de cycle si on considère le graphe non-orienté.
  • Ne permet pas la détection de circuit (la version "stricte" n'utilise pas de tableau des précédents).
  • Permet la détection de Composantes Simplement Connexes si il reste des sommets non traités après un premier passage (plus rapide en pratique que l'algorithme de Warshall si nous avons une seule cfc)

 

Caractéristiques de l'algorithme BFS

L'algorithme de recherche en largeur d'abord parcourt les sommets par "niveaux" dans l'arbre formé par le graphe. Le but est donc ici d'explorer tous les sommets suivants (enfants directs) d'un sommet donné, alors que DFS explore les sommets successeurs (du haut vers le bas, branche par branche). Nous n'avons donc pas de backtracking pour BFS, car nous ne devons jamais considérer le sommet précédent.

 

Exemple de parcours BFS

L'exemple suivant illustre l'algorithme BFS en action. Les sommets sont numérotés dans l'ordre d'exploration BFS.

Légende Graphes : animation BFS

 

Code de l'algorithme BFS

Nous pouvons décomposer notre algorithme en deux phases : une phase d'initialisation des valeurs, et une phase d'exécution qui décrit ce qui se passe lorsque l'algorithme est exécuté.

La phase d'exécution décrit comment traiter un sommet.

Variables

Dans cette approche, nous utilisons des collections indexées (par exemple des tableaux) pour maintenir les différentes informations relatives aux états de chaque objet Sommet. Dans une approche "orienté-objet", nous pouvons maintenir ces informations par exemple dans l'objet Sommet lui même.

  • visitedVertices : collection de booléens (true si nous sommes déjà passés par ce sommet)
  • orderedVertices : collection des indices des sommets. Notre algorithme place directement les sommets dans l'odre d'exploration.
  • Alternative previousVertices : collection qui maintient pour chaque sommet le numéro d'ordre du sommet précédent

Nous utiliserons aussi certaines variables supplémentaires :

  • X est l'ensemble des sommets du graphe
  • A est l'ensemble des arcs du graphe
  • i : indice dans notre collection de départ (X) du sommet parent en cours (sommet depuis lequel nous évaluons les suivants).
  • j : indice dans notre collection de départ (X) d'un des suivants du sommet dont l'index est i
  • parentVertex : indice dans le tableau orderedVertices du prochain sommet parent (sommet depuis lequel nous évaluerons les suivants).
  • vertexOrder : indice dans le tableau orderedVertices du premier emplacement libre.

arrayFirstIndex : indice du premier élément dans un tableau[1].

Phase d'initialisation

Nous devons initialiser les tableaux avec une taille correspondant à n.

Nous emploierons j pour raccourcir la notation (j ≥ arrayFirstIndex) ∧ (j < n+arrayFirstIndex), ce qui signifie pour tout emplacement du tableau.

  • i := arrayFirstIndex //indice du premier sommet (en pratique, peut être initialisé avec n'importe quelle valeur car i prendra sa valeur dans orderedVertices)
  • parentVertex := i //Nous traiterons le premier sommet (racine)
  • vertexOrder := arrayFirstIndex //Nous plaçerons le premier sommet au premier emplacement de libre de vertexOrder.
  • visitedVertices[arrayFirstIndex] := true //Puisque nous sommes positionnés sur le premier sommet, il est déjà visité
  • ∀(j ≠ arrayFirstIndex) : visitedVertices[j] := false //Tous les sommets qui suivent le premier sont non visités
  • orderedVertices[arrayFirstIndex] := i //le sommet courant est le premier
  • ∀(j ≠ arrayFirstIndex) : orderedVertices[j] := -1 //Valeur hors des indices possibles du tableau, ce qui signifie qu'il ne s'agit pas de l'indice d'un sommet existant
  • Alternative j : previousVertices[j] := -1 //Valeur hors des indices possibles du tableau, ce qui signifie l'absence de sommet précédent.

Phase d'exécution


Code (Pseudo-code de BFS) (28 lignes) :
  1. //si parentVertex > vertexOrder, nous avons visité tous les sommets
  2. tant_que vertexOrder &ge; parentVertex faire
  3.  
  4.   /* initialisation du sommet courant, et on sait
  5.   que visitedVertices[i]=true car il est marqué comme visité
  6.   AVANT d'être placé dans orderedVertices */
  7.   i ;:= orderedVertices[parentVertex];
  8.  
  9.   //parentVertex pointe maintenant sur le prochain sommet à évaluer
  10.   parentVertex ;:= parentVertex+1;
  11.  
  12.   /* i est l'indice de x, j est l'indice de y
  13.   ∃ y suivant de x, et non visité
  14.   cette boucle stocke tous les sommets d'un même niveau */
  15.   tant_que ;: (x,y) A visitedVertices[j]=false
  16.  
  17.     //marquer y comme visité
  18.     visitedVertices[j] ;:= true;
  19.  
  20.     //pointer vers l'indice suivant dans orderedVertices
  21.     vertexOrder ;:= vertexOrder+1;
  22.  
  23.     //stocker l'indice du sommet
  24.     orderedVertices[vertexOrder] ;:= j;
  25.  
  26.  
Alternative Version alternative : Ajout de la ligne 21 pour retrouver le précédent.

Code (Pseudo-code de BFS avec mémorisation des précédents) (31 lignes) :
  1. //si parentVertex > vertexOrder, nous avons visité tous les sommets
  2. tant_que vertexOrder &ge; parentVertex faire
  3.  
  4.   /* initialisation du sommet courant, et on sait
  5.   que visitedVertices[i]=true car il est marqué comme visité
  6.   AVANT d'être placé dans orderedVertices */
  7.   i ;:= orderedVertices[parentVertex];
  8.  
  9.   //parentVertex pointe maintenant sur le prochain sommet à évaluer
  10.   parentVertex ;:= parentVertex+1;
  11.  
  12.   /* i est l'indice de x, j est l'indice de y
  13.   ∃ y suivant de x, et non visité
  14.   cette boucle stocke tous les sommets d'un même niveau */
  15.   tant_que ;: (x,y) A visitedVertices[j]=false
  16.  
  17.     //marquer y comme visité
  18.     visitedVertices[j] ;:= true;
  19.  
  20.     //le sommet j a été atteint depuis le sommet i
  21.     previousVertices[j] ;:= i;
  22.  
  23.     //pointer vers l'indice suivant dans orderedVertices
  24.     vertexOrder ;:= vertexOrder+1;
  25.  
  26.     //stocker l'indice du sommet
  27.     orderedVertices[vertexOrder] ;:= j;
  28.  
  29.  

Ordre d'exploration et tableau orderedVertices

Selon notre implémentation, le tableau orderedVertices contient les indices des sommets de X, naturellement trié selon l'ordre de découverte des sommets.

Si nous désirons travailler comme pour notre algorithme DFS, il nous pouvons remplacer orderedVertices[vertexOrder] := j; par orderedVertices[j] := vertexOrder; (ligne 24Alternative 27). Nous devrons ensuite modifier la ligne 10 pour que parentVertex pointe sur le premier des suivants de i au lieu d'une incrémentation.
Dans ce cas, le tableau est trié (comme les autres tableaux) dans l'ordre des indices des sommets dans X, et contient pour chaque indice le numéro d'ordre du sommet correspondant.

Remarques

Dans le cas d'une implémentation avec arrayFirstIndex = 0, nous devons remplacer ≥ par > dans la comparaison entre vertexOrder et parentVertex (ligne 2).

Alternative 

L'instruction de la ligne 21 n'est pas strictement nécessaire car BFS ne nécessite pas de mémoriser quel est le sommet précédent. Dans ce cas, l'initialisation j : previousVertices[j] := -1 n'est pas nécessaire non plus.

 

Comparaison BFS DFS

Nous pouvons observer pour un même graphe les différences entre le parcours DFS et le parcours BFS. Les sommets sont marqués dans l'ordre d'exploration.

Ordre d'exploration

Dans le cas de DFS, les sommets sont explorés dans l'arbre "de haut en bas", alors que pour BFS ils sont explorés "par niveaux"

Graphes : Parcours DFS Graphes : Parcours BFS

Complexité

Au niveau de la complexité, les algorithmes DFS et BFS sont identiques Ordre de grandeur(m) car chaque arc n'est évalué qu'une seule fois. Ils diffèrent seulement par leur mode opératoire.

Implémentation

Les propos suivants s'appliquent aux implémentations que nous avons vu pour les algorithmes DFS et BFS, mais il existe de nombreuses autres implémentations qui respectent les caractéristiques de ces algorithmes.

Dans le cas de notre implémentation DFS, nous devons utiliser un numéro d'ordre pour les sommets. Nous pouvons trouver le numéro d'ordre d'un sommet en consultatnt le tableau verticesOrders à l'indice correspondant au sommet en question.
Notre implémentation de l'algorithme BFS, au contraire utilise un tableau orderedVertices pour lequel les indices correspondent au numéro d'ordre, et les valeurs correspondent aux indices des sommets.

Notre implémentation de DFS utilise un tableau de booléens closedVertices pour signaler qu'un sommet est visité et qu'il ne reste aucun sommet non visité depuis ce dernier. Ceci n'est pas nécessaire dans BFS car nous utilisons une comparaison d'indices.

 

Document créé le 13/12/09 17:22, dernière modification le 28/08/17 14:10
Source du document imprimé : https://www.gaudry.be/graphes-bfs.html

L'infobrol est un site personnel dont le contenu n'engage que moi. Le texte est mis à disposition sous licence CreativeCommons(BY-NC-SA). Plus d'info sur les conditions d'utilisation et sur l'auteur.

Notes

  1.  arrayFirstIndex : Ce n'est pas à proprement parler une variable, mais cela me permet d'éviter d'écrire 0 ou 1 dans le pseudo-code de l'algorithme selon le type de langage utilisé.
    Selon l'implémentation choisie, la collection utilisée peut démarrer son indexation à 0 (ex : tableau en Java) ou à 1 (ex : tableau en Pascal). Par exemple, en Java nous initialisons avec ∀i : previousVertices[i] = 0

 

Références

  1. livre Langue du document: fr Cours de Théorie des Graphes et réseaux de Petri : JP Leclercq, INFOB321 - Théorie des graphes (Septembre 2008)
  2. Consulter le document html Langue du document: fr Parcours en largeur + applet Java : Université Pierre Mendes Françe - Grenoble, Parcours en largeur

Ces références et liens indiquent des documents consultés lors de la rédaction de cette page, ou qui peuvent apporter un complément d'information, mais les auteurs de ces sources ne peuvent être tenus responsables du contenu de cette page.
L'auteur de ce site est seul responsable de la manière dont sont présentés ici les différents concepts, et des libertés qui sont prises avec les ouvrages de référence. N'oubliez pas que vous devez croiser les informations de sources multiples afin de diminuer les risques d'erreurs.