Algorithme BFS (Breadth First Search)

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

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

Retourner au début du code

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.

Table des matières Haut

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  :

You are on the French version of the site, but your system indicates that you prefer to use the English language.
The entire site is not translated yet, but the menus and buttons on the interface are largely translated.

Would you like to reach the page in English?
Click here to continue in English: Consult the English version of this page

U bevindt zich op de Franse versie van de site, maar uw systeem geeft aan dat u liever de Nederlandse taal gebruikt.
De hele site is nog niet vertaald, maar de menu's en knoppen op de interface zijn grotendeels vertaald.

Wilt u de pagina in het Nederlands bereiken?
Klik hier om door te gaan in het Nederlands: Raadpleeg de Nederlandse versie van deze pagina

Sie befinden sich in der französischen Version der Website, Ihr System gibt jedoch an, dass Sie die deutsche Sprache bevorzugen.
Die gesamte Site ist noch nicht übersetzt, aber die Menüs und Schaltflächen auf der Benutzeroberfläche sind weitgehend übersetzt.

Möchten Sie die Seite auf Deutsch erreichen?
Klicken Sie hier, um fortzufahren: Konsultieren Sie die deutsche Version dieser Seite