Algorithme BFS (Breadth First Search)

Sommaire du document

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.

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

//si parentVertex > vertexOrder, nous avons visité tous les sommets
tant_que vertexOrder ≥ parentVertex faire
 
	/* initialisation du sommet courant, et on sait
	que visitedVertices[i]=true car il est marqué comme visité
	AVANT d'être placé dans orderedVertices */
	i := orderedVertices[parentVertex];
 
	//parentVertex pointe maintenant sur le prochain sommet à évaluer
	parentVertex := parentVertex+1;
 
	/* i est l'indice de x, j est l'indice de y
	∃ y suivant de x, et non visité
	cette boucle stocke tous les sommets d'un même niveau */
	tant_que ∃ y : (x,y) ∈ A ∧ visitedVertices[j]=false
 
		//marquer y comme visité
		visitedVertices[j] := true;
 
		//pointer vers l'indice suivant dans orderedVertices
		vertexOrder := vertexOrder+1;
 
		//stocker l'indice du sommet
		orderedVertices[vertexOrder] := j;
 
	fin tant_que
 
fin tant_que

 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) :

//si parentVertex > vertexOrder, nous avons visité tous les sommets
tant_que vertexOrder ≥ parentVertex faire
 
	/* initialisation du sommet courant, et on sait
	que visitedVertices[i]=true car il est marqué comme visité
	AVANT d'être placé dans orderedVertices */
	i := orderedVertices[parentVertex];
 
	//parentVertex pointe maintenant sur le prochain sommet à évaluer
	parentVertex := parentVertex+1;
 
	/* i est l'indice de x, j est l'indice de y
	∃ y suivant de x, et non visité
	cette boucle stocke tous les sommets d'un même niveau */
	tant_que ∃ y : (x,y) ∈ A ∧ visitedVertices[j]=false
 
		//marquer y comme visité
		visitedVertices[j] := true;
 
		//le sommet j a été atteint depuis le sommet i
		previousVertices[j] := i;
 
		//pointer vers l'indice suivant dans orderedVertices
		vertexOrder := vertexOrder+1;
 
		//stocker l'indice du sommet
		orderedVertices[vertexOrder] := j;
 
	fin tant_que
 
fin tant_que

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 24 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).

 

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"

Complexité

Au niveau de la complexité, les algorithmes DFS et BFS sont identiques (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.

Afficher une autre alternative (les modifications dans la page seront précédées par  :

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. INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri (Septembre 2008)
2. Wikipedia : Wikipedia, Shortest paths in graphs (version 12/12/09)
3. Parcours en largeur : Université Pierre Mendes Françe - Grenoble, Parcours en largeur + applet Java

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.

Structure du document